WITCH-NG: efficient and accurate alignment of datasets with sequence length heterogeneity

Baqiao Liu, Tandy Warnow

Research output: Contribution to journalArticlepeer-review


Multiple sequence alignment 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 in the evolutionary history of the sequences and the inclusion of unassembled 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 one of the first methods to achieve good accuracy, and WITCH a recent improvement on UPP for accuracy. In this article, 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') achieves the same accuracy but is substantially faster. WITCH-NG is available at https://github.com/RuneBlaze/WITCH-NG. Availability and implementation: The datasets used in this study are from prior publications and are freely available in public repositories, as indicated in the Supplementary Materials.

Original languageEnglish (US)
Article numbervbad024
JournalBioinformatics Advances
Issue number1
StatePublished - 2023
Externally publishedYes

ASJC Scopus subject areas

  • Genetics
  • Molecular Biology
  • Structural Biology
  • Computer Science Applications


Dive into the research topics of 'WITCH-NG: efficient and accurate alignment of datasets with sequence length heterogeneity'. Together they form a unique fingerprint.

Cite this