A1 Refereed original research article in a scientific journal
Graph theoretic approach to parallel gene assembly
Authors: Harju T, Li C, Petre I
Publisher: ELSEVIER SCIENCE BV
Publication year: 2008
Journal:Discrete Applied Mathematics
Journal name in sourceDISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Volume: 156
Issue: 18
First page : 3416
Last page: 3429
Number of pages: 14
ISSN: 0166-218X
DOI: https://doi.org/10.1016/j.dam.2008.01.022
Abstract
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.
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.
UTU Research Portal