Graph theoretic approach to parallel gene assembly



: Harju T, Li C, Petre I

Publisher: ELSEVIER SCIENCE BV

: 2008

Discrete Applied Mathematics

DISCRETE APPLIED MATHEMATICS

: DISCRETE APPL MATH

: 156

: 18

: 3416

: 3429

: 14

: 0166-218X

DOI: https://doi.org/10.1016/j.dam.2008.01.022


We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or - In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs call be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic. (C) 2008 Elsevier B.V. All rights reserved.



Last updated on 2025-14-10 at 10:10