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.
|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|
|Number of pages||12|
|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
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2016|
|Period||16/1/23 → 16/1/28|
Bibliographical notePublisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)