Before revision:  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).
After revision:  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 on a sequence with length 32,753 nt). More interestingly, 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).