A1 Refereed original research article in a scientific journal
Gene assembly through cyclic graph decomposition
Authors: Ehrenfeucht A, Harju T, Rozenberg G
Publisher: ELSEVIER SCIENCE BV
Publication year: 2002
Journal:: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Article number: PII S0304-3975(02)00019-1
Volume: 281
Issue: 1-2
First page : 325
Last page: 349
Number of pages: 25
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(02)00019-1
Abstract
We present in this paper a graph theoretical model of gene assembly, where (segments of) genes are distributed over a set of circular molecules. This model is motivated by the process of gene assembly in ciliates, but it is more general. In this model a set of circular DNA molecules is represented by a bicoloured and labelled graph gamma consisting of cyclic graphs, and the recombination takes place in two stages: first, by folding gamma * P with respect to a set P of pairs of vertices of the graph (representing pointers in the micronuclear genes of the ciliate), and secondly, by unfolding the so obtained graph to gamma circle * P with respect to vertices of higher valency. The final graph gamma circle * P is again a set of bicoloured cyclic graphs, where the genes are present as maximal monochromatic paths. Thus, the process of gene assembly corresponds to the dynamic process of changing cyclic graph decompositions. We show that the operation () is well behaved in many respects, and that there is a sequence of pointer sets P-1,...,P-m consisting of one or two pairs such that gamma circle * P = (...((gamma circle * P-1) circle * P-2)...circle * P-m) and each intermediate step gamma(i) = (...((y circle * P-1) circle * P-2)... circle * P-i) is intracyclic, that is, the segments of a gene that lie in the same connected component of gamma(i), will lie in the same connected component of the successor graph gamma(i+1). (C) 2002 Published by Elsevier Science B.V.
We present in this paper a graph theoretical model of gene assembly, where (segments of) genes are distributed over a set of circular molecules. This model is motivated by the process of gene assembly in ciliates, but it is more general. In this model a set of circular DNA molecules is represented by a bicoloured and labelled graph gamma consisting of cyclic graphs, and the recombination takes place in two stages: first, by folding gamma * P with respect to a set P of pairs of vertices of the graph (representing pointers in the micronuclear genes of the ciliate), and secondly, by unfolding the so obtained graph to gamma circle * P with respect to vertices of higher valency. The final graph gamma circle * P is again a set of bicoloured cyclic graphs, where the genes are present as maximal monochromatic paths. Thus, the process of gene assembly corresponds to the dynamic process of changing cyclic graph decompositions. We show that the operation () is well behaved in many respects, and that there is a sequence of pointer sets P-1,...,P-m consisting of one or two pairs such that gamma circle * P = (...((gamma circle * P-1) circle * P-2)...circle * P-m) and each intermediate step gamma(i) = (...((y circle * P-1) circle * P-2)... circle * P-i) is intracyclic, that is, the segments of a gene that lie in the same connected component of gamma(i), will lie in the same connected component of the successor graph gamma(i+1). (C) 2002 Published by Elsevier Science B.V.
UTU Research Portal