Abstract
We consider formal recombination operations presented in terms of string, graphs and permutations. These operations are faithful to the molecular operations of gene assembly introduced by Prescott, Ehrenfeucht, and Rozenberg [17]. The results mentioned here on the formal operations are mostly stated in the recent book [8], where one also finds the original references.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderson, E., Chrobak, M., Noga, J., Sgall, J., Woeginger, G.: Solution of a problem in DNA computing. Theoret. Comput. Sci. 287, 387–391 (2002)
Arratia, R., Bollobáas, B., Sorkin, G.B.: The interlace polynomial: a new graph polynomial. In: Proc. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 237–245. ACM, New York (2000)
Birman, J.S., Trapp, R.: Braided chord diagrams. J. Knot Theory and its Ramifications 7, 1–22 (1998)
Bouchet, A.: Circle graphs. Combinatorica 7, 243–254 (1987)
Bouchet, A.: Transforming trees by successive local complementations. J. Graph Theory 12, 195–207 (1988)
Bouchet, A.: Circle graph obstructions. J. Combin. Theory Ser B 60, 107–144 (1994)
Caprara, A.: Sorting by reversals is difficult. In: Istrail, S., Pevzner, P., Waterman, M. (eds.) 1st Annual Int. Conf. on Comput. Molecular Biology, pp. 75–83 (1997)
Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D.M., Rozenberg, G.: Computation in Living Cells. Gene Assembly in Ciliates. Springer, Heidelberg (2003)
Fon-der-Flaas, D.: On local complementations of graphs. In: Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, pp. 257–266. North-Holland, Amsterdam (1988)
de Fraysseix, H.: A characterization of circle graphs. European J. Combin. 5, 223–238 (1984)
Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip. In: Proc. 27th ACM Symp. on Theory of Computing, pp. 178–189 (1995)
Jahn, C.L., Klobutcher, L.A.: Genome remodeling in ciliated protozoa. Ann. Rev. Microbiol. 56, 489–520 (2000)
Landweber, L.F., Kari, L.: The evolution of cellular computing: nature’s solution to a computational problem. In: Proc. 4th DIMACS meeting on DNA based computers, Philadelphia, PA, pp. 3–15 (1998)
Prescott, D.M.: The evolutionary scrambling and developmental unscambling of germline genes in hypotrichous ciliates. Nucleic Acids Res. 27(5), 1243–1250 (1999)
Prescott, D.M.: Genome gymnastics: unique modes of DNA evolution and processing in ciliates. Nat Rev Genet. 1(3), 191–198 (2000)
Prescott, D.M., Bostock, C.J., Murti, K.G., Lauth, M.R., Gamow, E.: DNA in ciliated protozoa. I. Electron microscopy and sedimentation analysis of macronuclear and micronuclear DNA of Stylonychia mytilus. Chromosoma 34, 355–366 (1971)
Prescott, D.M., Ehrenfeucht, A., Rozenberg, G.: Molecular operations for DNA processing in hypotrichous ciliates. European J Protistology 37, 241–260 (2001)
Zaslavsky, T.: Bibliography of Signed and Gain Graphs. Electronic J. Combin., Dynamic Surveys (1999), http://www.combinatorics.org/Surveys/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Harju, T. (2005). Combinatorial Models of Gene Assembly. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds) New Computational Paradigms. CiE 2005. Lecture Notes in Computer Science, vol 3526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494645_23
Download citation
DOI: https://doi.org/10.1007/11494645_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26179-7
Online ISBN: 978-3-540-32266-5
eBook Packages: Computer ScienceComputer Science (R0)