Duplication in DNA Sequences
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, equations involving these operations, and steps towards a characterization of regular duplication languages, i.e. languages that are the result of the duplication operation applied to a given set.
BibTeX
@inproceedings{Ito2008, author = {Masami Ito and Lila Kari and Zachary Kincaid and Shinnosuke Seki}, title = {Duplication in {DNA} Sequences}, booktitle = {Developments in Language Theory}, year = {2008}, pages = {419-430}, ee = {http://dx.doi.org/10.1007/978-3-540-85780-8_33}, bibsource = {DBLP, http://dblp.uni-trier.de} }
Extended version
An extended version of this paper appeared in Algorithmic Bioprocesses.
BibTeX
@incollection {Ito2009, author = {Masami Ito and Lila Kari and Zachary Kincaid and Shinnosuke Seki}, title = {Duplication in {DNA} Sequences}, booktitle = {Algorithmic Bioprocesses}, series = {Natural Computing Series}, publisher = {Springer}, pages = {43–61}, editor = {A. Condon and D. Harel and J. N. Kok and A. Salomaa and E. Winfree}, year = {2009}, }