[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Combinatorial Models of Gene Assembly

  • Conference paper
New Computational Paradigms (CiE 2005)

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

Included in the following conference series:

  • 1174 Accesses

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.

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

Access this chapter

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. Anderson, E., Chrobak, M., Noga, J., Sgall, J., Woeginger, G.: Solution of a problem in DNA computing. Theoret. Comput. Sci. 287, 387–391 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. 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)

    Google Scholar 

  3. Birman, J.S., Trapp, R.: Braided chord diagrams. J. Knot Theory and its Ramifications 7, 1–22 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bouchet, A.: Circle graphs. Combinatorica 7, 243–254 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bouchet, A.: Transforming trees by successive local complementations. J. Graph Theory 12, 195–207 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bouchet, A.: Circle graph obstructions. J. Combin. Theory Ser B 60, 107–144 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  7. 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)

    Google Scholar 

  8. Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D.M., Rozenberg, G.: Computation in Living Cells. Gene Assembly in Ciliates. Springer, Heidelberg (2003)

    Google Scholar 

  9. 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)

    Google Scholar 

  10. de Fraysseix, H.: A characterization of circle graphs. European J. Combin. 5, 223–238 (1984)

    MATH  MathSciNet  Google Scholar 

  11. Hannenhalli, S., Pevzner, P.A.: Transforming cabbage into turnip. In: Proc. 27th ACM Symp. on Theory of Computing, pp. 178–189 (1995)

    Google Scholar 

  12. Jahn, C.L., Klobutcher, L.A.: Genome remodeling in ciliated protozoa. Ann. Rev. Microbiol. 56, 489–520 (2000)

    Article  Google Scholar 

  13. 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)

    Google Scholar 

  14. Prescott, D.M.: The evolutionary scrambling and developmental unscambling of germline genes in hypotrichous ciliates. Nucleic Acids Res. 27(5), 1243–1250 (1999)

    Article  Google Scholar 

  15. Prescott, D.M.: Genome gymnastics: unique modes of DNA evolution and processing in ciliates. Nat Rev Genet. 1(3), 191–198 (2000)

    Article  Google Scholar 

  16. 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)

    Article  Google Scholar 

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

    Article  Google Scholar 

  18. Zaslavsky, T.: Bibliography of Signed and Gain Graphs. Electronic J. Combin., Dynamic Surveys (1999), http://www.combinatorics.org/Surveys/

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics