Pseudoknot-generating operation

Da Jung Cho; Yo Sub Han; Timothy Ng; Kai Salomaa

doi:10.1007/978-3-662-49192-8_20

Pseudoknot-generating operation

Da Jung Cho, Yo Sub Han, Timothy Ng, Kai Salomaa

College of Computing

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

1 Citation (Scopus)

Abstract

A pseudoknot is an intra-molecular structure formed primarily in RNA strands and much research has been done to predict efficiently pseudoknot structures in RNA. We define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation.We give an efficient algorithm to decide whether a given string is a pseudoknot of a regular language L—the runtime is linear if L is given by a deterministic finite automaton. We consider closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms to decide whether a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

Original language	English
Title of host publication	SOFSEM 2016
Subtitle of host publication	Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Editors	Rūsiņš Mārtiņš Freivalds, Gregor Engels, Barbara Catania
Publisher	Springer Verlag
Pages	241-252
Number of pages	12
ISBN (Print)	9783662491911
DOIs	https://doi.org/10.1007/978-3-662-49192-8_20
Publication status	Published - 2016
Event	42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016 - Harrachov, Czech Republic Duration: 2016 Jan 23 → 2016 Jan 28

Publication series

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

Other

Other	42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016
Country/Territory	Czech Republic
City	Harrachov
Period	16/1/23 → 16/1/28

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-49192-8_20

Cite this

Cho, D. J., Han, Y. S., Ng, T., & Salomaa, K. (2016). Pseudoknot-generating operation. In R. M. Freivalds, G. Engels, & B. Catania (Eds.), SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings (pp. 241-252). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587). Springer Verlag. https://doi.org/10.1007/978-3-662-49192-8_20

Cho, Da Jung ; Han, Yo Sub ; Ng, Timothy et al. / Pseudoknot-generating operation. SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. editor / Rūsiņš Mārtiņš Freivalds ; Gregor Engels ; Barbara Catania. Springer Verlag, 2016. pp. 241-252 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{000db1f474224c58b15bd990bf9b9816,

title = "Pseudoknot-generating operation",

abstract = "A pseudoknot is an intra-molecular structure formed primarily in RNA strands and much research has been done to predict efficiently pseudoknot structures in RNA. We define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation.We give an efficient algorithm to decide whether a given string is a pseudoknot of a regular language L—the runtime is linear if L is given by a deterministic finite automaton. We consider closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms to decide whether a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.",

author = "Cho, {Da Jung} and Han, {Yo Sub} and Timothy Ng and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016 ; Conference date: 23-01-2016 Through 28-01-2016",

year = "2016",

doi = "10.1007/978-3-662-49192-8_20",

language = "English",

isbn = "9783662491911",

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

publisher = "Springer Verlag",

pages = "241--252",

editor = "Freivalds, {Rūsiņ{\v s} Mārtiņ{\v s}} and Gregor Engels and Barbara Catania",

booktitle = "SOFSEM 2016",

address = "Germany",

}

Cho, DJ, Han, YS, Ng, T & Salomaa, K 2016, Pseudoknot-generating operation. in RM Freivalds, G Engels & B Catania (eds), SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9587, Springer Verlag, pp. 241-252, 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016, Harrachov, Czech Republic, 16/1/23. https://doi.org/10.1007/978-3-662-49192-8_20

Pseudoknot-generating operation. / Cho, Da Jung; Han, Yo Sub; Ng, Timothy et al.
SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. ed. / Rūsiņš Mārtiņš Freivalds; Gregor Engels; Barbara Catania. Springer Verlag, 2016. p. 241-252 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9587).

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

TY - GEN

T1 - Pseudoknot-generating operation

AU - Cho, Da Jung

AU - Han, Yo Sub

AU - Ng, Timothy

AU - Salomaa, Kai

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

PY - 2016

Y1 - 2016

N2 - A pseudoknot is an intra-molecular structure formed primarily in RNA strands and much research has been done to predict efficiently pseudoknot structures in RNA. We define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation.We give an efficient algorithm to decide whether a given string is a pseudoknot of a regular language L—the runtime is linear if L is given by a deterministic finite automaton. We consider closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms to decide whether a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

AB - A pseudoknot is an intra-molecular structure formed primarily in RNA strands and much research has been done to predict efficiently pseudoknot structures in RNA. We define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation.We give an efficient algorithm to decide whether a given string is a pseudoknot of a regular language L—the runtime is linear if L is given by a deterministic finite automaton. We consider closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms to decide whether a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

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

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

U2 - 10.1007/978-3-662-49192-8_20

DO - 10.1007/978-3-662-49192-8_20

M3 - Conference contribution

AN - SCOPUS:84956627442

SN - 9783662491911

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

SP - 241

EP - 252

BT - SOFSEM 2016

A2 - Freivalds, Rūsiņš Mārtiņš

A2 - Engels, Gregor

A2 - Catania, Barbara

PB - Springer Verlag

T2 - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016

Y2 - 23 January 2016 through 28 January 2016

ER -

Cho DJ, Han YS, Ng T, Salomaa K. Pseudoknot-generating operation. In Freivalds RM, Engels G, Catania B, editors, SOFSEM 2016: Theory and Practice of Computer Science - 42nd International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer Verlag. 2016. p. 241-252. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49192-8_20

Pseudoknot-generating operation

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this