Linearknot predicts rna pseudoknots fast and accurately

LinearKnot: Linear-Time Approximation of the Pseudoknot Partition Function

Data Structures and Algorithms

Summary

Predicting RNA shapes that include special knots called pseudoknots is very slow with current exact methods. The authors developed LinearKnot, a new way to approximate these complex shapes much faster and using less computer memory. Their method runs in nearly linear time and uses a three-step process to estimate the pseudoknot probabilities almost exactly. This allows scientists to analyze very long RNA sequences that were previously impossible to handle with exact methods.

What this means in practice

  • For biotech software developers: Enable fast prediction of RNA with pseudoknots in genome-length sequences to aid RNA-based drug and design pipelines.
  • For viral genome analysts: Provide timely pseudoknot structure estimates for long viral RNAs to support research into viral functions and therapies.

Authors

Milan Gautam, David H. Mathews, Liang Huang

Abstract

Pseudoknots, where two or more helices cross, are central to many functional RNAs, including frameshifting signals, telomerase RNA, riboswitches and viral genomes. With arbitrary pseudoknots, finding the minimum free energy structure is NP-hard, so most RNA secondary structure prediction tools only consider pseudoknot-free structures. Dirks and Pierce (DP03) pioneered the first pseudoknot partition function, which underlies NUPACK's pseudoknot model, but it takes $O(n^5)$ time and $O(n^4)$ memory, making it practical only for very short sequences. Linear-time approximate dynamic programming, as in LinearFold and LinearPartition, does not transfer easily to DP03: a partial pseudoknot leaves a gap filled by its crossing partner, whose complementary sequence may still lie ahead of the scan, so it cannot be ranked by its inside weight. We present LinearKnot, a linear-time approximation of DP03 in three passes: (a) LinearPartition gives pseudoknot-free weights; (b) a second pass builds tables that estimate each partial stem's crossing partner; and (c) a third scans a left-to-right reformulation of DP03 that reserves the 5' nucleotides in the pseudoknot helix for subsequent pairing, keeping the states with the largest estimated contribution. Without pruning, this reformulation computes DP03's pseudoknot recursion exactly, so the only approximation is which states the beam keeps. End-to-end, time grows linearly ($n^{1.01}$) and memory marginally above linear ($n^{1.15}$) from 1,000 to 9,392 nt. LinearKnot folds the 9,392 nt Rous sarcoma virus genome in 2.4 hours and 90.5 GB, where exact DP03 would need an estimated 40,000 years and 54 million GB, and matches exact DP03 base-pair probabilities on 418 PseudoBase RNAs with a median RMSD of $9.2\times10^{-7}$. Our code is available at https://github.com/gautammilan/LinearKnot.