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

Reeder J, Giegerich R (2004)
BMC Bioinformatics 5(1): 104.

Download
OA
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
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.
Erscheinungsjahr
Zeitschriftentitel
BMC Bioinformatics
Band
5
Zeitschriftennummer
1
Seite
104
ISSN
PUB-ID

Zitieren

Reeder J, Giegerich R. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 2004;5(1):104.
Reeder, J., & Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1), 104. doi:10.1186/1471-2105-5-104
Reeder, J., and Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5, 104.
Reeder, J., & Giegerich, R., 2004. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1), p 104.
J. Reeder and R. Giegerich, “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”, BMC Bioinformatics, vol. 5, 2004, pp. 104.
Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 5, 104 (2004).
Reeder, Jens, and Giegerich, Robert. “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”. BMC Bioinformatics 5.1 (2004): 104.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
1970-01-01T00:00:00Z

101 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Prediction of consensus RNA secondary structures including pseudoknots.
Witwer C, Hofacker IL, Stadler PF., IEEE/ACM Trans Comput Biol Bioinform 1(2), 2004
PMID: 17048382

36 References

Daten bereitgestellt von Europe PubMed Central.

An approximation of loop free energy values of RNA H-pseudoknots.
Gultyaev AP, van Batenburg FH, Pleij CW., RNA 5(5), 1999
PMID: 10334330
Linguistic approaches to biological sequences.
Searls DB., Comput. Appl. Biosci. 13(4), 1997
PMID: 9283748
A grammar-based unification of several alignment and folding algorithms
Lefebvre F., 1996
Reducing the conformation space in RNA structure prediction
Evers D, Giegerich R., 2001
Bielefeld Bioinformatics Server
AUTHOR UNKNOWN, 0
Crystal structure of a hepatitis delta virus ribozyme.
Ferre-D'Amare AR, Zhou K, Doudna JA., Nature 395(6702), 1998
PMID: 9783582
RnaViz 2: an improved representation of RNA secondary structure.
De Rijk P, Wuyts J, De Wachter R., Bioinformatics 19(2), 2003
PMID: 12538259
RNA pseudoknots that inhibit human immunodeficiency virus type 1 reverse transcriptase.
Tuerk C, MacDougal S, Gold L., Proc. Natl. Acad. Sci. U.S.A. 89(15), 1992
PMID: 1379730
Five pseudoknots are present at the 204 nucleotides long 3' noncoding region of tobacco mosaic virus RNA
van A, Abrahams JP, Pleij CW, Bosch L., 1985

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 15294028
PubMed | Europe PMC

Suchen in

Google Scholar