• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Computing the Graph-Based Parallel Complexity of Gene Assembly

Artiom Alhazov, Chang Li, Ion Petre, Computing the Graph-Based Parallel Complexity of Gene Assembly. Theoretical Computer Science 411(25), 2359–2367, 2010.

Abstract:

We consider a graph-theoretical formalization of the process of gene assembly in ciliates introduced in Ehrenfeucht et al. (2003), where a gene is modeled as a signed graph. The gene assembly, based on three types of operations only, is then modeled as a graph reduction process (to the empty graph). Motivated by the robustness of the gene assembly process, the notions of parallel reduction and parallel complexity of signed graphs have been considered in Harju et al. (2006). We describe in this paper an exact algorithm for computing the parallel complexity of a given signed graph and for finding an optimal parallel reduction for it. Checking the parallel applicability of a given set of operations and scanning all possible selections amount to a high computational complexity. We also briefly discuss a faster approximate algorithm that however, cannot guarantee finding the optimal reduction.

BibTeX entry:

@ARTICLE{jAlLiPe09a,
  title = {Computing the Graph-Based Parallel Complexity of Gene Assembly},
  author = {Alhazov, Artiom and Li, Chang and Petre, Ion},
  journal = {Theoretical Computer Science},
  volume = {411},
  number = {25},
  pages = {2359–2367},
  year = {2010},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 2

Edit publication