  Predicting the consensus structure of a set of aligned RNA homologs is a
convenient method to find conserved structures in an RNA genome, which has many
applications including viral diagnostics and therapeutics. However, the most
commonly used tool for this task, RNAalifold, is prohibitively slow for long
sequences, due to a cubic scaling with the sequence length, taking over a day
on 400 SARS-CoV-2 and SARS-related genomes (~30,000nt). We present
LinearAlifold, a much faster alternative that scales linearly with both the
sequence length and the number of sequences, based on our work LinearFold that
folds a single RNA in linear time. Our work is orders of magnitude faster than
RNAalifold (0.7 hours on the above 400 genomes, or ~36$\times$ speedup) and
achieves higher accuracies when compared to a database of known structures.
More interestingly, LinearAlifold's prediction on SARS-CoV-2 correlates well
with experimentally determined structures, substantially outperforming
RNAalifold. Finally, LinearAlifold supports two energy models (Vienna and BL*)
and four modes: minimum free energy (MFE), maximum expected accuracy (MEA),
ThreshKnot, and stochastic sampling, each of which takes under an hour for
hundreds of SARS-CoV variants. Our resource is at:
https://github.com/LinearFold/LinearAlifold (code) and
http://linearfold.org/linear-alifold (server).
