  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).
