WITCH-NG: Efficient and Accurate Alignment of Datasets with Sequence Length Heterogeneity

Multiple sequence alignment (MSA) is a basic part of many bioinformatics pipelines, including in phylogeny estimation, prediction of structure for both RNAs and proteins, and metagenomic sequence analysis. Yet many sequence datasets exhibit substantial sequence length heterogeneity, both because of large insertions and deletions (indels) in the evolutionary history of the sequences and the inclusion of sequencing reads or incompletely assembled sequences in the input. A few methods have been developed that can be highly accurate in aligning datasets with sequence length heterogeneity, with UPP (Nguyen et al., 2015) one of the first methods to achieve good accuracy, and WITCH (Shen et al., Bioinformatics 2021) an improvement on UPP for accuracy, In this paper, we show how we can speed up WITCH. Our improvement includes replacing a critical step in WITCH (currently performed using a heuristic search) by a polynomial time exact algorithm using Smith-Waterman. Our new method, WITCH-NG (i.e., "next generation WITCH", pronounced "witching") achieves the same accuracy but is substantially faster. WITCH-NG is available in open source form at https://github.com/RuneBlaze/WITCH-NG.