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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333–340 (1975)
Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Appl. Math. 104(1), 45–62 (2000)
Brierley, I., Digard, P., Inglis, S.C.: Characterization of an efficient coronavirus ribosomal frameshifting signal: requirement for an RNA pseudoknot. Cell 57(4), 537–547 (1989)
Condon, A., Davy, B., Rastegari, B., Zhao, S., Tarrant, F.: Classifying RNA pseudoknotted structures. Theor. Comput. Sci. 320(1), 35–50 (2004)
Dirks, R.M., Lin, M., Winfree, E., Pierce, N.A.: Paradigms for computational nucleic acid design. Nucleic Acids Res. 32(4), 1392–1403 (2004)
Doose, G., Metzler, D.: Bayesian sampling of evolutionarily conserved RNA secondary structures with pseudoknots. Bioinformatics 28(17), 2242–2248 (2012)
Du, Z., Hoffman, D.W.: An NMR and mutational study of the pseudoknot within the gene 32 mRNA of bacteriophage T2: insights into a family of structurally related RNA pseudoknots. Nucleic Acids Res. 25(6), 1130–1135 (1997)
Evans, P.A.: Finding common RNA pseudoknot structures in polynomial time. J. Discrete Algorithms 9(4), 335–343 (2011)
Giedroc, D.P., Theimer, C.A., Nixon, P.L.: Structure, stability and function of RNA pseudoknots involved in stimulating ribosomal frameshifting. J. Mol. Biol. 298(2), 167–185 (2000)
Jabbari, H., Condon, A.: A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures. BMC Bioinform. 15(1), 147 (2014)
Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. J. Comput. Biol. 9(2), 371–388 (2002)
Jürgensen, H., Konstantinidis, S.: Codes. In: Word, Language, Grammar. Handbook of Formal Languages, vol. 1, pp. 511–607 (1997)
Kari, L., Konstantinidis, S., Kopecki, S.: Transducer Descriptions of DNA Code Properties and Undecidability of Antimorphic Problems. arXiv:1503.00035 (2015)
Kari, L., Mahalingam, K.: Watson-Crick palindromes in DNA computing. Nat. Comput. 9(2), 297–316 (2010)
Kari, L., Seki, S.: On pseudoknot-bordered words and their properties. J. Comput. Syst. Sci. 75(2), 113–121 (2009)
Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323–350 (1977)
Möhl, M., Will, S., Backofen, R.: Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 69–81. Springer, Heidelberg (2008)
Rinaudo, P., Ponty, Y., Barth, D., Denise, A.: Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol. 7534, pp. 149–164. Springer, Heidelberg (2012)
Saraiya, A.A., Lamichhane, T.N., Chow, C.S., SantaLucia Jr., J., Cunningham, P.R.: Identification and role of functionally important motifs in the 970 loop of Escherichia coli 16S ribosomal RNA. J. Mol. Biol. 376(3), 645–657 (2008)
Shallit, J.: A Second Course in Formal Languages and Automata Theory, vol. 179. Cambridge University Press, Cambridge (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cho, DJ., Han, YS., Ng, T., Salomaa, K. (2016). Pseudoknot-Generating Operation. In: Freivalds, R., Engels, G., Catania, B. (eds) SOFSEM 2016: Theory and Practice of Computer Science. SOFSEM 2016. Lecture Notes in Computer Science(), vol 9587. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49192-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-662-49192-8_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49191-1
Online ISBN: 978-3-662-49192-8
eBook Packages: Computer ScienceComputer Science (R0)