On Computational Properties of Template-Guided DNA Recombination | SpringerLink
Skip to main content
Springer Nature Link
Log in

On Computational Properties of Template-Guided DNA Recombination

  • Conference paper
DNA Computing (DNA 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3892))

Included in the following conference series:

Abstract

The stichotrichous ciliates have attracted the attention of both biologists and computer scientists due to the unique genetic mechanism of gene descrambling. It has been suggested that it would perhaps be possible to co-opt this genetic process and use it to perform arbitrary computations in vivo. Motivated by this idea, we study here some basic properties and the computational power of a formalization inspired by the template-guided recombination model of gene descrambling proposed by Ehrenfeucht, Prescott and Rozenberg. We demonstrate that the computational power of a system based on template-guided recombination is quite limited. We then extend template-guided recombination systems with the addition of “deletion contexts” and show that such systems have strictly greater computational power than splicing systems [1, 2].

This research was funded in part by institutional grants of the University of Saskatchewan and the University of Western Ontario, the SHARCNET Research Chairs programme, the Natural Sciences and Engineering Research Council of Canada and the National Science Foundation of the United States.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Head, T.: Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology 49 (1987)

    Google Scholar 

  2. Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New computing paradigms. Springer, Berlin (1998)

    Book  MATH  Google Scholar 

  3. Prescott, D.: Genome gymnastics: Unique modes of DNA evolution and processing in ciliates. Nature Reviews Genetics 1, 191–198 (2000)

    Article  Google Scholar 

  4. Kari, L., Landweber, L.: Computational power of gene rearrangement. In: Winfree, E., Gifford, D. (eds.) DNA5. DIMACS series in Discrete Mathematics and Theoretical Computer Science, vol. 54, pp. 207–216. American Mathematical Society (2000)

    Google Scholar 

  5. Landweber, L., Kari, L.: The evolution of cellular computing: Nature’s solution to a computational problem. In: Kari, L., Rubin, H., Wood, D. (eds.) DNA4, BioSystems, vol. 52, pp. 3–13. Elsevier, Amsterdam (1999)

    Google Scholar 

  6. Ehrenfeucht, A., Prescott, D., Rozenberg, G.: Computational aspects of gene (un)scrambling in ciliates. In: Landweber, L., Winfree, E. (eds.) Evolution as Computation, pp. 45–86. Springer, Heidelberg (2001)

    Google Scholar 

  7. Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Computation in Living Cells, Gene Assembly in Ciliates. Springer, Berlin (2004)

    Book  MATH  Google Scholar 

  8. Ehrenfeucht, A., Prescott, D., Rozenberg, G.: Molecular operations for DNA processing in hypotrichous ciliates. European Journal of Protistology 37, 241–260 (2001)

    Article  Google Scholar 

  9. Prescott, D., Ehrenfeucht, A., Rozenberg, G.: Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates. Journal of Theoretical Biology 222, 323–330 (2003)

    Article  MathSciNet  Google Scholar 

  10. Salomaa, A.: Formal Languages. Academic Press, New York (1973)

    MATH  Google Scholar 

  11. Berstel, J.: Transductions and Context-Free Languages. B.B. Teubner, Stuttgart (1979)

    Google Scholar 

  12. Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland Publishing Company, Amsterdam (1975)

    MATH  Google Scholar 

  13. Daley, M., McQuillan, I.: Template-guided DNA recombination. Theoretical Computer Science 330, 237–250 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Daley, M., McQuillan, I.: Useful templates and template-guided DNA recombination. Theory of Computing Systems (to appear)

    Google Scholar 

  15. Doak, T.: Personal communication

    Google Scholar 

  16. Landweber, L., Kuo, T., Curtis, E.: Evolution and assembly of an extremely scrambled gene. PNAS 97, 3298–3303 (2000)

    Article  Google Scholar 

  17. Păun, G.: Regular extended H systems are computationally universal. Journal of Automata, Languages and Combinatorics 1, 27–36 (1996)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Department of Biology, University of Western Ontario, London, Ontario, N6A 5B7, Canada

    Mark Daley

  2. Department of Computer Science, University of Saskatchewan, Saskatoon, Saskatchewan, S7N 5A9, Canada

    Mark Daley & Ian McQuillan

Authors
  1. Mark Daley
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ian McQuillan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Université Pierre et Marie Curie, INSERM U511,, 91 Boulevard de L’Hôpital, 75013, Paris, France

    Alessandra Carbone

  2. California Institute of Technology, Applied and Computational Mathematics, Bioengineering,, MC 114-96, 91125, Pasadena, CA, USA

    Niles A. Pierce

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Daley, M., McQuillan, I. (2006). On Computational Properties of Template-Guided DNA Recombination. In: Carbone, A., Pierce, N.A. (eds) DNA Computing. DNA 2005. Lecture Notes in Computer Science, vol 3892. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11753681_3

Download citation

  • DOI: https://doi.org/10.1007/11753681_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-34161-1

  • Online ISBN: 978-3-540-34165-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation