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 ).
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 , which is shown to be orders of magnitude 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 ).