Computing the graph-based parallel complexity of gene assembly |
| |
Authors: | Artiom Alhazov Chang Li Ion Petre |
| |
Affiliation: | a Department of Information Technologies, Åbo Akademi University, Finland b Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Str. Academiei 5, Chi?in?u, MD-2028, Republic of Moldova c Turku Centre for Computer Science, FIN-20520 Turku, Finland d Academy of Finland, Finland |
| |
Abstract: | We consider a graph-theoretical formalization of the process of gene assembly in ciliates introduced in Ehrenfeucht et al. (2003) [3], 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) [7]. 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. |
| |
Keywords: | Gene assembly Parallelism Signed graphs Parallel complexity Algorithmics |
本文献已被 ScienceDirect 等数据库收录! |
|