RNA secondary structure prediction is widely used to understand RNA function. Recently, there has been a shift away from the classical minimum free energy (MFE) methods to partition function-based methods that account for folding ensembles and can therefore estimate structure and base pair probabilities. However, the classical partition function algorithm scales cubically with sequence length, and is therefore a slow calculation for long sequences. This slowness is even more severe than cubic-time MFE-based methods due to a larger constant factor in runtime. Inspired by the success of our recently proposed LinearFold algorithm that computes the MFE structure in linear time, we propose a similar linear-time heuristic algorithm, LinearPartition, to approximate the partition function and base pairing probabilities . LinearPartition is 256x faster than Vienna RNAfold for a sequence with length 15,780, and 2,771x faster than CONTRAfold for a sequence with length 32,753 ( 2.5 days vs. 1.3 minutes ). Interestingly, although LinearPartition is approximate, the resulting base pairing probabilities are  better correlated with the ground truth structures and lead to a small accuracy improvement  on families with the longest length sequences (16S and 23S rRNA) when used for downstream structure prediction , as well as a substantial improvement on long-distance base pairs (500+ nt apart).
RNA secondary structure prediction is widely used to understand RNA function. Recently, there has been a shift away from the classical minimum free energy (MFE) methods to partition function-based methods that account for folding ensembles and can therefore estimate structure and base pair probabilities. However, the classical partition function algorithm scales cubically with sequence length, and is therefore a slow calculation for long sequences. This slowness is even more severe than cubic-time MFE-based methods due to a larger constant factor in runtime. Inspired by the success of our recently proposed LinearFold algorithm that predicts the approximate MFE structure in linear time, we design a similar linear-time heuristic algorithm, LinearPartition, to approximate the partition function and base pairing probabilities , which is shown to be orders of magnitude faster than Vienna RNAfold and CONTRAfold (e.g., 2.5 days vs. 1.3 minutes on a sequence with length 32,753 nt). More interestingly, the resulting base pairing probabilities are even better correlated with the ground truth structures . LinearPartition also leads to a small accuracy improvement when used for downstream structure prediction on families with the longest length sequences (16S and 23S rRNA) , as well as a substantial improvement on long-distance base pairs (500+ nt apart).
R
computes the
predicts the approximate
R
propose
design
R
. LinearPartition is 256x
, which is shown to be orders of magnitude
R
for a sequence with length 15,780, and 2,771x faster than CONTRAfold for a sequence with length 32,753 (
and CONTRAfold (e.g.,
R
). Interestingly, although LinearPartition is approximate,
on a sequence with length 32,753 nt). More interestingly,
A
even
R
and lead
. LinearPartition also leads
A
when used for downstream structure prediction
D
when used for downstream structure prediction