Skip to Main content Skip to Navigation
Journal articles

Knotty: efficient and accurate prediction of complex RNA pseudoknot structures

Hosna Jabbari Ian Wark Carlo Montemagno Sebastian Will 1
1 AMIBIO - Algorithms and Models for Integrative BIOlogy
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : The computational prediction of RNA secondary structure by free energy minimization has become an important tool in RNA research. However in practice, energy minimization is mostly limited to pseudoknot-free structures or rather simple pseudoknots, not covering many biologically important structures such as kissing hairpins. Algorithms capable of predicting sufficiently complex pseudoknots (for sequences of length n) used to have extreme complexities, e.g. Pknots has O(n6) time and O(n4) space complexity. The algorithm CCJ dramatically improves the asymptotic run time for predicting complex pseudoknots (handling almost all relevant pseudoknots, while being slightly less general than Pknots), but this came at the cost of large constant factors in space and time, which strongly limited its practical application (∼200 bases already require 256 GB space).
Document type :
Journal articles
Complete list of metadata
Contributor : Sebastian Will <>
Submitted on : Wednesday, July 29, 2020 - 5:11:19 PM
Last modification on : Wednesday, October 14, 2020 - 4:15:36 AM

Links full text




Hosna Jabbari, Ian Wark, Carlo Montemagno, Sebastian Will. Knotty: efficient and accurate prediction of complex RNA pseudoknot structures. Bioinformatics, Oxford University Press (OUP), 2018, 34 (22), pp.3849-3856. ⟨10.1093/bioinformatics/bty420⟩. ⟨hal-02908990⟩



Record views