Abstract
The concept of breakpoint graph, known from the theory of sorting by reversal, has been successfully applied in the theory of gene assembly in ciliates. We further investigate its usage for gene assembly, and show that the graph allows for an efficient characterization of the possible orders of loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) for a given gene during gene assembly. The characterization is based on spanning trees within a graph built upon the connected components in the breakpoint graph. We work in the abstract and more general setting of so-called legal strings.
This research was supported by the Netherlands Organization for Scientific Research (NWO) project 635.100.006 ‘VIEWS’.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ehrenfeucht, A., Petre, I., Prescott, D., Rozenberg, G.: Circularity and other invariants of gene assembly in ciliates. In: Ito, M., et al. (eds.) Words, Semigroups, and Transductions, pp. 81–97. World Scientific, Singapore (2001)
Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Computation in Living Cells – Gene Assembly in Ciliates. Springer, Heidelberg (2004)
Brijder, R., Hoogeboom, H., Rozenberg, G.: Reducibility of gene patterns in ciliates using the breakpoint graph. Theor. Comput. Sci. 356, 26–45 (2006)
Brijder, R., Hoogeboom, H., Rozenberg, G.: The breakpoint graph in ciliates. In: Berthold, M.R., Glen, R.C., Diederichs, K., Kohlbacher, O., Fischer, I. (eds.) CompLife 2005. LNCS (LNBI), vol. 3695, pp. 128–139. Springer, Heidelberg (2005)
Pevzner, P.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000)
Setubal, J., Meidanis, J.: Introduction to Computional Molecular Biology. PWS Publishing Company (1997)
Bergeron, A., Mixtacki, J., Stoye, J.: On sorting by translocations. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol. 3500, pp. 615–629. Springer, Heidelberg (2005)
Brijder, R., Hoogeboom, H., Muskulus, M.: Strategies of loop recombination in ciliates. LIACS Technical Report 2006-01, [arXiv:cs.LO/0601135] (2006)
Ehrenfeucht, A., Petre, I., Prescott, D., Rozenberg, G.: String and graph reduction systems for gene assembly in ciliates. Math. Struct. in Comput. Sci. 12, 113–134 (2002)
Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Formal systems for gene assembly in ciliates. Theor. Comput. Sci. 292, 199–219 (2003)
Prescott, D., DuBois, M.: Internal eliminated segments (IESs) of oxytrichidae. J. Euk. Microbiol. 43, 432–441 (1996)
Ciliates IES MDS database, http://oxytricha.princeton.edu/dimorphism/
Harju, T., Li, C., Petre, I., Rozenberg, G.: Parallelism in gene assembly. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 138–148. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brijder, R., Hoogeboom, H.J., Muskulus, M. (2006). Applicability of Loop Recombination in Ciliates Using the Breakpoint Graph. In: R. Berthold, M., Glen, R.C., Fischer, I. (eds) Computational Life Sciences II. CompLife 2006. Lecture Notes in Computer Science(), vol 4216. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11875741_10
Download citation
DOI: https://doi.org/10.1007/11875741_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45767-1
Online ISBN: 978-3-540-45768-8
eBook Packages: Computer ScienceComputer Science (R0)