Duplications and pseudo-duplications

Da Jung Cho; Yo Sub Han; Hwee Kim; Alexandros Palioudakis; Kai Salomaa

doi:10.1007/978-3-319-21819-9_11

Duplications and pseudo-duplications

Da Jung Cho, Yo Sub Han, Hwee Kim, Alexandros Palioudakis, Kai Salomaa

College of Computing

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

2 Citations (Scopus)

Abstract

A duplication is basic phenomenon that occurs through molecular evolution on a biological sequence. A duplication on a string copies any substring of the string. We define k-pseudo-duplication of a string w that consists, roughly speaking, of all strings obtained from w by inserting after a substring u another substring obtained from u by at most k edit operations. We consider three variants of duplication operations, duplication, k-pseudo-duplication and reverse-duplication. First, we give the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize duplications on a string. Then, we show that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Furthermore, we show that the class of context-sensitive languages is closed under duplication, pseudo-duplication and reverse-duplication.

Original language	English
Title of host publication	Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings
Editors	Cristian S. Calude, Michael J. Dinneen
Publisher	Springer Verlag
Pages	157-168
Number of pages	12
ISBN (Print)	9783319218182
DOIs	https://doi.org/10.1007/978-3-319-21819-9_11
Publication status	Published - 2015
Event	14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015 - Auckland, New Zealand Duration: 2015 Aug 30 → 2015 Sept 3

Publication series

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

Other

Other	14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015
Country/Territory	New Zealand
City	Auckland
Period	15/8/30 → 15/9/3

Bibliographical note

Funding Information:
This research was supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512), the Yonsei University Future-leading Research Initiative of 2014 and the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

Publisher Copyright:
© Springer International Publishing Switzerland 2015

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-21819-9_11

Cite this

Cho, D. J., Han, Y. S., Kim, H., Palioudakis, A., & Salomaa, K. (2015). Duplications and pseudo-duplications. In C. S. Calude, & M. J. Dinneen (Eds.), Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings (pp. 157-168). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9252). Springer Verlag. https://doi.org/10.1007/978-3-319-21819-9_11

Cho, Da Jung ; Han, Yo Sub ; Kim, Hwee et al. / Duplications and pseudo-duplications. Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings. editor / Cristian S. Calude ; Michael J. Dinneen. Springer Verlag, 2015. pp. 157-168 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f36279693f90406e93b81d9c811a11c6,

title = "Duplications and pseudo-duplications",

abstract = "A duplication is basic phenomenon that occurs through molecular evolution on a biological sequence. A duplication on a string copies any substring of the string. We define k-pseudo-duplication of a string w that consists, roughly speaking, of all strings obtained from w by inserting after a substring u another substring obtained from u by at most k edit operations. We consider three variants of duplication operations, duplication, k-pseudo-duplication and reverse-duplication. First, we give the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize duplications on a string. Then, we show that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Furthermore, we show that the class of context-sensitive languages is closed under duplication, pseudo-duplication and reverse-duplication.",

author = "Cho, {Da Jung} and Han, {Yo Sub} and Hwee Kim and Alexandros Palioudakis and Kai Salomaa",

note = "Funding Information: This research was supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512), the Yonsei University Future-leading Research Initiative of 2014 and the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015; 14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015 ; Conference date: 30-08-2015 Through 03-09-2015",

year = "2015",

doi = "10.1007/978-3-319-21819-9_11",

language = "English",

isbn = "9783319218182",

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

publisher = "Springer Verlag",

pages = "157--168",

editor = "Calude, {Cristian S.} and Dinneen, {Michael J.}",

booktitle = "Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings",

address = "Germany",

}

Cho, DJ, Han, YS, Kim, H, Palioudakis, A & Salomaa, K 2015, Duplications and pseudo-duplications. in CS Calude & MJ Dinneen (eds), Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9252, Springer Verlag, pp. 157-168, 14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015, Auckland, New Zealand, 15/8/30. https://doi.org/10.1007/978-3-319-21819-9_11

Duplications and pseudo-duplications. / Cho, Da Jung; Han, Yo Sub; Kim, Hwee et al.
Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings. ed. / Cristian S. Calude; Michael J. Dinneen. Springer Verlag, 2015. p. 157-168 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9252).

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

TY - GEN

T1 - Duplications and pseudo-duplications

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Kim, Hwee

AU - Palioudakis, Alexandros

AU - Salomaa, Kai

N1 - Funding Information: This research was supported by the Basic Science Research Program through NRF funded by MEST (2012R1A1A2044562), the International Cooperation Program managed by NRF of Korea (2014K2A1A2048512), the Yonsei University Future-leading Research Initiative of 2014 and the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224. Publisher Copyright: © Springer International Publishing Switzerland 2015

PY - 2015

Y1 - 2015

N2 - A duplication is basic phenomenon that occurs through molecular evolution on a biological sequence. A duplication on a string copies any substring of the string. We define k-pseudo-duplication of a string w that consists, roughly speaking, of all strings obtained from w by inserting after a substring u another substring obtained from u by at most k edit operations. We consider three variants of duplication operations, duplication, k-pseudo-duplication and reverse-duplication. First, we give the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize duplications on a string. Then, we show that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Furthermore, we show that the class of context-sensitive languages is closed under duplication, pseudo-duplication and reverse-duplication.

AB - A duplication is basic phenomenon that occurs through molecular evolution on a biological sequence. A duplication on a string copies any substring of the string. We define k-pseudo-duplication of a string w that consists, roughly speaking, of all strings obtained from w by inserting after a substring u another substring obtained from u by at most k edit operations. We consider three variants of duplication operations, duplication, k-pseudo-duplication and reverse-duplication. First, we give the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize duplications on a string. Then, we show that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Furthermore, we show that the class of context-sensitive languages is closed under duplication, pseudo-duplication and reverse-duplication.

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

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

U2 - 10.1007/978-3-319-21819-9_11

DO - 10.1007/978-3-319-21819-9_11

M3 - Conference contribution

AN - SCOPUS:84943646846

SN - 9783319218182

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 168

BT - Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings

A2 - Calude, Cristian S.

A2 - Dinneen, Michael J.

PB - Springer Verlag

T2 - 14th International Conference on Unconventional Computation and Natural Computation, UCNC 2015

Y2 - 30 August 2015 through 3 September 2015

ER -

Cho DJ, Han YS, Kim H, Palioudakis A, Salomaa K. Duplications and pseudo-duplications. In Calude CS, Dinneen MJ, editors, Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Proceedings. Springer Verlag. 2015. p. 157-168. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-21819-9_11

Duplications and pseudo-duplications

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this