Abstract
The duplication and repeat-deletion operations are the basis of a formal language theoretic model of errors that can occur during DNA replication. During DNA replication, subsequences of a strand of DNA may be copied several times (resulting in duplications) or skipped (resulting in repeat-deletions). As formal language operations, iterated duplication and repeat-deletion of words and languages have been well studied in the literature. However, little is known about single-step duplications and repeat-deletions. In this paper, we investigate several properties of these operations, including closure properties of language families in the Chomsky hierarchy and equations involving these operations. We also make progress toward 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 the 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
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
Bichara M, Wagner J, Lambert IB (2006) Mechanisms of tandem repeat instability in bacteria. Mut Res 598(1–2):144–163
Dassow J, Mitrana V, Păun Gh (1999) On the regularity of duplication closure. Bull EATCS 69:133–136
Dassow J, Mitrana V, Salomaa A (2002) Operations and language generating devices suggested by the genome evolution. Theor Comput Sci 270:701–738
Garcia-Diaz M, Kunkel TA (2006) Mechanism of a genetic glissando: structural biology of indel mutations. Trends Biochem Sci 31(4):206–214
Gu Z, Steinmetz LM, Gu X, Scharfe G, Davis RW, Li W-H (2003) Role of duplicate genes in genetic robustness against null mutations. Nature 421:63–66
Harrison MA (1978) Introduction to formal language theory. Addison–Wesley, Reading
Ito M (2004) Algebraic theory of automata and languages. World Scientific, Singapore
Ito M, Kari L, Kincaid Z, Seki S (2008) Duplication in DNA sequences. In: Ito M, Toyama M (eds) DLT 2008. Lecture notes in computer science, vol 5257. Springer, Berlin, pp 419–430
Ito M, Leupold P, S-Tsuji K (2006) Closure of language classes under bounded duplication. In: Ibarra OH, Dang Z (eds) DLT 2006. Lecture notes in computer science, vol 4036. Springer, Berlin, pp 238–247
Leupold P (2007) Duplication roots. In: Harju T, Karhumäki J, Lepistö A (eds) DLT 2007. Lecture notes in computer science, vol 4588. Springer, Berlin, pp 290–299
Leupold P (2006) Languages generated by iterated idempotencies and the special case of duplication. PhD thesis, Department de Filologies Romaniques, Facultat de Lletres, Universitat Rovira i Virgili, Tarragona, Spain
Leupold P, M-Vide C, Mitrana V (2005) Uniformly bounded duplication languages. Discrete Appl Math 146(3):301–310
Leupold P, Mitrana V, Sempere J (2004) Formal languages arising from gene repeated duplication. In: Aspects of molecular computing. Essays in honour of Tom Head on his 70th birthday. Lecture notes in computer science, vol 2950. Springer, Berlin, pp 297–308
Lothaire M (1983) Combinatorics on words. Encyclopedia of mathematics and its applications, vol 17. Addison–Wesley, Reading
Lyndon RC, Schützenberger MP (1962) On the equation a M=b N c P in a free group. Mich Math J 9:289–298
M-Vide C, Păun Gh (1999) Duplication grammars. Acta Cybern 14:151–164
Mitrana V, Rozenberg G (1999) Some properties of duplication grammars. Acta Cybern 14:165–177
Reis CM, Shyr HJ (1978) Some properties of disjunctive languages on a free monoid. Inf Control 37:334–344
Ross R, Winklmann K (1982) Repetitive strings are not context-free. RAIRO Inform Theor 16(3):191–199
Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages. Springer, Berlin
Searls DB (1993) The computational linguistics of biological sequences. In: Hunter L (ed) Artificial intelligence and molecular biology. AAAI Press/MIT Press, Menlo Park, pp 47–120
Yu SS (2005) Languages and codes. Lecture notes. Department of Computer Science, National Chung-Hsing University, Taichung, Taiwan 402
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Ito, M., Kari, L., Kincaid, Z., Seki, S. (2009). Duplication in DNA Sequences. In: Condon, A., Harel, D., Kok, J., Salomaa, A., Winfree, E. (eds) Algorithmic Bioprocesses. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88869-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-88869-7_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88868-0
Online ISBN: 978-3-540-88869-7
eBook Packages: Computer ScienceComputer Science (R0)