Parallel Complexity of Signed Graphs for Gene Assembly in Ciliates (bibtex)
by Harju, Tero, Li, Chang and Petre, Ion
Abstract:
We consider a graph-based model for the study of parallelism in ciliate gene assembly, where a signed graph is associated to each micronuclear gene and the gene assembly is modeled as a graph rewriting process. A natural measure of complexity for gene assembly counts the minimal number of parallel steps needed to reduce the associated signed graph. We investigate the complexity of several classes of the graphs, so far found graphs of parallel complexity up to six. The general problem of whether there exists a finite upper bound for the graph parallel complexity still remains open.
Reference:
Parallel Complexity of Signed Graphs for Gene Assembly in Ciliates (Harju, Tero, Li, Chang and Petre, Ion), In Soft Computing - A Fusion of Foundations, Methodologies and Applications, Springer Berlin/Heidenberg, volume 12, 2008.
Bibtex Entry:
@Article{j150,
author    = {Harju, Tero AND Li, Chang AND Petre, Ion},
title     = {Parallel Complexity of Signed Graphs for Gene Assembly in Ciliates},
journal   = {Soft Computing - A Fusion of Foundations, Methodologies and Applications},
year      = {2008},
volume    = {12},
number    = {8},
pages     = {731-737},
abstract  = {We consider a graph-based model for the study of parallelism in ciliate gene assembly, where a signed graph is associated to each micronuclear gene and the gene assembly is modeled as a graph rewriting process. A natural measure of complexity for gene assembly counts the minimal number of parallel steps needed to reduce the associated signed graph. We investigate the complexity of several classes of the graphs, so far found graphs of parallel complexity up to six. The general problem of whether there exists a finite upper bound for the graph parallel complexity still remains open.},
file      = {TCI2008a.pdf:pdfs/TCI2008a.pdf:PDF},
keywords  = {Gene assembly, Parallel complexity},
publisher = {Springer Berlin/Heidenberg},
}