TY - GEN
T1 - Duplication in DNA sequences
AU - Ito, Masami
AU - Kari, Lila
AU - Kincaid, Zachary
AU - Seki, Shinnosuke
N1 - Funding Information:
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.
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=54249109046&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=54249109046&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-85780-8_33
DO - 10.1007/978-3-540-85780-8_33
M3 - Conference contribution
AN - SCOPUS:54249109046
SN - 3540857796
SN - 9783540857792
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 419
EP - 430
BT - Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings
T2 - 12th International Conference on Developments in Language Theory, DLT 2008
Y2 - 16 September 2008 through 19 September 2008
ER -