[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Duplication in DNA Sequences

  • Conference paper
Developments in Language Theory (DLT 2008)

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

Included in the following conference series:

Abstract

Duplication and repeat-deletion are the basic models of errors occurring during DNA replication from the viewpoint of formal languages. During DNA replication, subsequences of a strand of DNA may be copied several times (duplication) or skipped (repeat-deletion). Iterated duplication and repeat-deletion have been well-studied, but little is known about single-step duplication and repeat-deletion. In this paper, we investigate properties of these operations, such as closure properties of language families in the Chomsky hierarchy, language equations involving these operations. We also make progress towards a characterization of regular languages that are generated by duplicating a regular language.

This research was supported by Grant-in-Aid for Scientific Research No. 19-07810 by Japan Society for the Promotion of Sciences and Research Grant No. 015 by Kyoto Sangyo University to M. I., and The Natural Sciences and Engineering Council of Canada Discovery Grant and Canada Research Chair Award to L.K.

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. Dassow, J., Mitrana, V., Păun, G.: On the regularity of duplication closure. Bull. EATCS 69, 133–136 (1999)

    MATH  Google Scholar 

  2. Dassow, J., Mitrana, V., Salomaa, A.: Operations and language generating devices suggested by the genome evolution. Theoretical Computer Science 270, 701–738 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Garcia-Diaz, M., Kunkel, T.A.: Mechanism of a genetic glissando: structural biology of indel mutations. Trends in Biochemical Sciences 31(4), 206–214 (2006)

    Article  Google Scholar 

  4. Ito, M.: Algebraic Theory of Automata and Languages. World Scientific Pub. Co. Inc., Singapore (2004)

    MATH  Google Scholar 

  5. Ito, M., Leupold, P., S-Tsuji, K.: Closure of language classes under bounded duplication. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol. 4036, pp. 238–247. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  6. Leupold, P.: Duplication roots. In: Harju, T., Karhumäki, J., Lepistö, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 290–299. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  7. Leupold, P.: Languages generated by iterated idempotencies and the special case of duplication. Ph.D. thesis, Department de Filologies Romaniques, Facultat de Lletres, Universitat Rovira i Virgili, Tarragona, Spain (2006)

    Google Scholar 

  8. Leupold, P., Mitrana, V., Sempere, J.: Formal languages arising from gene repeated duplication. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 297–308. Springer, Heidelberg (2003)

    Google Scholar 

  9. Leupold, P., M-Vide, C., Mitrana, V.: Uniformly bounded duplication languages. Discrete Applied Mathematics 146(3), 301–310 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  10. Lothaire, M.: Combinatorics on Words, Encyclopedia of Mathematics and its Applications 17. Addison-Wesley Publishing Co., Reading (1983)

    Google Scholar 

  11. Lyndon, R.C., Schützenberger, M.P.: On the equation a M = b N c P in a free group. Michigan Mathematical Journal 9, 289–298 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  12. M-Vide, C., Păun, G.: Duplication grammars. Acta Cybernetica 14, 151–164 (1999)

    MathSciNet  Google Scholar 

  13. Mitrana, V., Rozenberg, G.: Some properties of duplication grammars. Acta Cybernetica 14, 165–177 (1999)

    MATH  MathSciNet  Google Scholar 

  14. Reis, C.M., Shyr, H.J.: Some properties of disjunctive languages on a free monoid. Information and Control 37, 334–344 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  15. Ross, R., Winklmann, K.: Repetitive strings are not context-free. R.A.I.R.O informatique théorique / Theoretical Informatics 16(3), 191–199 (1982)

    MATH  MathSciNet  Google Scholar 

  16. Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer, Heidelberg (1997)

    MATH  Google Scholar 

  17. Searls, D.B.: The computational linguistics of biological sequences. In: Hunter, L. (ed.) Artificial Intelligence and Molecular Biology, pp. 47–120. AAAI Press, The MIT Press (1993)

    Google Scholar 

  18. Yu, S.S.: Languages and Codes. Lecture Notes, Department of Computer Science, p. 402. National Chung-Hsing University, Taichung (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Faculty of Science, Kyoto Sangyo University, Kyoto, Japan, 603-8555

    Masami Ito

  2. Department of Computer Science, University of Western Ontario, London, Ontario, Canada, N6A 5B7

    Lila Kari, Zachary Kincaid & Shinnosuke Seki

Authors
  1. Masami Ito
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lila Kari
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zachary Kincaid
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shinnosuke Seki
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Masami Ito Masafumi Toyama

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ito, M., Kari, L., Kincaid, Z., Seki, S. (2008). Duplication in DNA Sequences. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2008. Lecture Notes in Computer Science, vol 5257. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85780-8_33

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-85780-8_33

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-85779-2

  • Online ISBN: 978-3-540-85780-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation