  The classical Sankoff algorithm for the simultaneous folding and alignment of
homologous RNA sequences is highly influential, but it suffers from two major
limitations in efficiency and modeling power. First, it takes $O(n^6)$ for two
sequences where n is the average sequence length. Most implementations and
variations reduce the runtime to $O(n^3)$ by restricting the alignment search
space, but this is still too slow for long sequences such as full-length viral
genomes. On the other hand, the Sankoff algorithm and all its existing
implementations use a rather simplistic alignment model, which can result in
poor alignment accuracy. To address these problems, we propose LinearSankoff,
which seamlessly integrates the original Sankoff algorithm with a powerful
Hidden Markov Model-based alignment module. This extension substantially
improves alignment quality, which in turn benefits secondary structure
prediction quality, confirmed over a diverse set of RNA families. LinearSankoff
also applies beam search heuristics and the A$^\star$-like algorithm to achieve
that runtime scales linearly with sequence length. LinearSankoff is the first
linear-time algorithm for simultaneous folding and alignment, and the first
such algorithm to scale to coronavirus genomes (n $\approx$ 30,000nt). It only
takes 10 minutes for a pair of SARS-CoV-2 and SARS-related genomes, and
outperforms previous work at identifying crucial conserved structures between
the two genomes.
