Duplication in DNA sequences

Masami Ito; Lila Kari; Zachary Kincaid; Shinnosuke Seki

doi:10.1007/978-3-540-88869-7_4

Duplication in DNA sequences

Masami Ito, Lila Kari, Zachary Kincaid, Shinnosuke Seki

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	43-61
Number of pages	19
Journal	Natural Computing Series
Issue number	9783540888680
DOIs	https://doi.org/10.1007/978-3-540-88869-7_4
State	Published - 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science

Access to Document

10.1007/978-3-540-88869-7_4

Cite this

@article{2886831ca38845b596d964fe684c32aa,

title = "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 and equations involving these operations. We also make progress toward a characterization of regular languages that are generated by duplicating a regular language.",

author = "Masami Ito and Lila Kari and Zachary Kincaid and Shinnosuke Seki",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2009.",

year = "2009",

doi = "10.1007/978-3-540-88869-7_4",

language = "English (US)",

pages = "43--61",

journal = "Natural Computing Series",

issn = "1619-7127",

publisher = "Springer Verlag",

number = "9783540888680",

}

TY - JOUR

T1 - Duplication in DNA sequences

AU - Ito, Masami

AU - Kari, Lila

AU - Kincaid, Zachary

AU - Seki, Shinnosuke

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2009.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85019995105&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85019995105&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-88869-7_4

DO - 10.1007/978-3-540-88869-7_4

M3 - Article

AN - SCOPUS:85019995105

SN - 1619-7127

SP - 43

EP - 61

JO - Natural Computing Series

JF - Natural Computing Series

IS - 9783540888680

ER -

Duplication in DNA sequences

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this