TY - GEN
T1 - Duplication in DNA sequences
AU - Ito, Masami
AU - Kari, Lila
AU - Kincaid, Zachary
AU - Seki, Shinnosuke
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
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 -