SALMA: Scalable ALignment using MAFFT-Add

Multiple sequence alignment is essential for many biological downstream analyses, but accurate alignment of large datasets, especially those exhibiting high rates of evolution or sequence length heterogeneity, is still unsolved. We present SALMA, a new multiple sequence alignment that provides high accuracy and scalability, even for datasets exhibiting high rates of evolution and great sequence length heterogeneity that arises from evolutionary processes. Like some prior methods (e.g., UPP, WITCH, and MAFFT-sparsecore), SALMA operates in two distinct stages: the first stage computes a "backbone alignment" for a subset of the sequences, and the second stage adds the remaining sequences into the backbone alignment. The main novelty in SALMA is how it adds the remaining ("query") sequences into the backbone alignment. For this step, which we refer to as SALMA-add, we use divide-and-conquer to scale MAFFT-linsi--add to enable it to add sequences into large backbone alignments. We show that SALMA-add has an advantage over other sequence-adding techniques for many realistic conditions and can scale to very large datasets with high accuracy (hundreds of thousands of sequences). We also show that SALMA is one of the most accurate compared to standard alignment methods. Our open source software for SALMA is available at https://github.com/c5shen/SALMA.