A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Gene assembly through cyclic graph decomposition
Tekijät: Ehrenfeucht A, Harju T, Rozenberg G
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2002
Lehti:: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Artikkelin numero: PII S0304-3975(02)00019-1
Vuosikerta: 281
Numero: 1-2
Aloitussivu: 325
Lopetussivu: 349
Sivujen määrä: 25
ISSN: 0304-3975
DOI: https://doi.org/10.1016/S0304-3975(02)00019-1
Tiivistelmä
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.