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 languageEnglish (US)
Title of host publicationDevelopments in Language Theory - 12th International Conference, DLT 2008, Proceedings
Pages419-430
Number of pages12
DOIs
StatePublished - 2008
Externally publishedYes
Event12th International Conference on Developments in Language Theory, DLT 2008 - Kyoto, Japan
Duration: Sep 16 2008 → Sep 19 2008

Publication series

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

Other

Other12th International Conference on Developments in Language Theory, DLT 2008
CountryJapan
CityKyoto
Period9/16/08 → 9/19/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Access to Document

Other files and links

Fingerprint Dive into the research topics of 'Duplication in DNA sequences'. Together they form a unique fingerprint.

Cite this