Accurate Multiple Sequence Alignment of Ultramassive Genome Sets

With ever increasing sequencing efficiency, there is a pressing need to tackle a presently intractable task of accurate multiple sequence alignment (MSA) for ultramassive genome sets of millions and beyond. Additionally, efficient graph and probabilistic representations for downstream analysis are in dire lack. In light of these challenges, we develop a set of linearly scalable algorithms, including that for constructing directed acyclic graphs, for training profile hidden Markov models and for conducting alignment on such graphs. The astounding power of these algorithms is demonstrated by both significantly improved accuracy and tremendous acceleration of SAR-CoV-2 MSA by three observed to five projected orders of magnitude for genome set sizes ranging from 40,000 to more than 4 million when compared with widely utilized MAFFT. Future application to other viral species and extension to more complex genomes will prove this algorithm set as a cornerstone for the coming era of ultramassive genome sets.