LinAliFold and CentroidLinAliFold: Fast RNA consensus secondary structure prediction for aligned sequences using beam search methods

RNA consensus secondary structure prediction from aligned sequences is a pow- erful approach for improving the secondary structure prediction accuracy. How- ever, because the computational complexities of conventional prediction tools scale with the cube of the alignment lengths, their application to long RNA se- quences, such as viral RNAs or long non-coding RNAs, requires significant com- putational time. In this study, we developed LinAliFold and CentroidLinAli- Fold, fast RNA consensus secondary structure prediction tools based on mini- mum free energy and maximum expected accuracy principles, respectively. We achieved software acceleration using beam search methods that were success- fully used for fast secondary structure prediction from a single RNA sequence. Benchmark analyses showed that LinAliFold and CentroidLinAliFold were much faster than the existing methods while preserving the prediction accuracy. As an empirical application, we predicted the consensus secondary structure of coro- naviruses with approximately 30,000 nt in 5 and 76 minutes by LinAliFold and CentroidLinAliFold, respectively. We confirmed that the predicted consensus sec- ondary structure of coronaviruses was consistent with the experimental results. The source code is freely available at https://github.com/fukunagatsu/LinAliFold-CentroidLinAliFold.