Duplication in DNA sequences

Masami Ito; Lila Kari; Zachary Kincaid; Shinnosuke Seki

doi:10.1007/978-3-540-85780-8_33

Duplication in DNA sequences

Masami Ito, Lila Kari, Zachary Kincaid, Shinnosuke Seki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings
Pages	419-430
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-540-85780-8_33
State	Published - 2008
Externally published	Yes
Event	12th International Conference on Developments in Language Theory, DLT 2008 - Kyoto, Japan Duration: Sep 16 2008 → Sep 19 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5257 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Conference on Developments in Language Theory, DLT 2008
Country/Territory	Japan
City	Kyoto
Period	9/16/08 → 9/19/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-85780-8_33

Cite this

Ito, M., Kari, L., Kincaid, Z., & Seki, S. (2008). Duplication in DNA sequences. In Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings (pp. 419-430). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5257 LNCS). https://doi.org/10.1007/978-3-540-85780-8_33

@inproceedings{5d50327404674f6081ef9501353c9697,

title = "Duplication in DNA sequences",

abstract = "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.",

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

year = "2008",

doi = "10.1007/978-3-540-85780-8_33",

language = "English (US)",

isbn = "3540857796",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "419--430",

booktitle = "Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings",

}

Ito, M, Kari, L, Kincaid, Z & Seki, S 2008, Duplication in DNA sequences. in Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5257 LNCS, pp. 419-430, 12th International Conference on Developments in Language Theory, DLT 2008, Kyoto, Japan, 9/16/08. https://doi.org/10.1007/978-3-540-85780-8_33

Duplication in DNA sequences. / Ito, Masami; Kari, Lila; Kincaid, Zachary; Seki, Shinnosuke.

Developments in Language Theory - 12th International Conference, DLT 2008, Proceedings. 2008. p. 419-430 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5257 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Duplication in DNA sequences

AU - Ito, Masami

AU - Kari, Lila

AU - Kincaid, Zachary

AU - Seki, Shinnosuke

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 -

Duplication in DNA sequences

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this