Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. Export

@article{reeder, abstract = {BACKGROUND: The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n6)time and O(n4) space algorithm by Rivas and Eddy is currently the best available program. RESULTS: We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n4) time and O(n2) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm. CONCLUSIONS: RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.}, address = {Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany. jreeder@techfak.uni-bielefeld.de}, author = {Reeder, J. and Giegerich, R.}, citeulike-article-id = {437763}, citeulike-linkout-0 = {http://dx.doi.org/10.1186/1471-2105-5-104}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/15294028}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=15294028}, day = {4}, doi = {10.1186/1471-2105-5-104}, issn = {1471-2105}, journal = {BMC bioinformatics}, month = {August}, posted-at = {2009-01-17 03:21:08}, priority = {2}, title = {Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.}, url = {http://dx.doi.org/10.1186/1471-2105-5-104}, volume = {5}, year = {2004} }

TY - JOUR ID - reeder L3 - citeulike-article-id:437763 N2 - BACKGROUND: The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n6)time and O(n4) space algorithm by Rivas and Eddy is currently the best available program. RESULTS: We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n4) time and O(n2) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm. CONCLUSIONS: RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm. JF - BMC bioinformatics SN - 1471-2105 AD - Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany. jreeder@techfak.uni-bielefeld.de TI - Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. VL - 5 AU - Reeder, J AU - Giegerich, R PY - 2004/08/04/ UR - http://dx.doi.org/10.1186/1471-2105-5-104 ER -