WITCH: Improved Multiple Sequence Alignment Through Weighted Consensus Hidden Markov Model Alignment
Authors:
- 1 August 2022
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 29 (8) , 782-801
Abstract
Accurate multiple sequence alignment is challenging on many data sets, including those that are large, evolve under high rates of evolution, or have sequence length heterogeneity. While substantial progress has been made over the last decade in addressing the first two challenges, sequence length heterogeneity remains a significant issue for many data sets. Sequence length heterogeneity occurs for biological and technological reasons, including large insertions or deletions (indels) that occurred in the evolutionary history relating the sequences, or the inclusion of sequences that are not fully assembled. Ultra-large alignments using Phylogeny-Aware Profiles (UPP) (Nguyen et al. 2015 ) is one of the most accurate approaches for aligning data sets that exhibit sequence length heterogeneity: it constructs an alignment on the subset of sequences it considers “full-length,” represents this “backbone alignment” using an ensemble of hidden Markov models (HMMs), and then adds each remaining sequence into the backbone alignment based on an HMM selected for that sequence from the ensemble. Our new method, WeIghTed Consensus Hmm alignment (WITCH), improves on UPP in three important ways: first, it uses a statistically principled technique to weight and rank the HMMs; second, it uses k > 1 HMMs from the ensemble rather than a single HMM; and third, it combines the alignments for each of the selected HMMs using a consensus algorithm that takes the weights into account. We show that this approach provides improved alignment accuracy compared with UPP and other leading alignment methods, as well as improved accuracy for maximum likelihood trees based on these alignments.Keywords
This publication has 33 references indexed in Scilit:
- MAFFT Multiple Sequence Alignment Software Version 7: Improvements in Performance and UsabilityMolecular Biology and Evolution, 2013
- MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignmentsBMC Bioinformatics, 2012
- RAxML and FastTree: Comparing Two Methods for Large-Scale Maximum Likelihood Phylogeny EstimationPLOS ONE, 2011
- The Effects of Alignment Error and Alignment Filtering on the Sitewise Detection of Positive SelectionMolecular Biology and Evolution, 2011
- FASTSP: linear time calculation of alignment accuracyBioinformatics, 2011
- FastTree 2 – Approximately Maximum-Likelihood Trees for Large AlignmentsPLOS ONE, 2010
- Rapid and Accurate Large-Scale Coestimation of Sequence Alignments and Phylogenetic TreesScience, 2009
- Recent developments in the MAFFT multiple sequence alignment programBriefings in Bioinformatics, 2008
- MUSCLE: multiple sequence alignment with high accuracy and high throughputNucleic Acids Research, 2004
- Hidden Markov Models in Computational BiologyJournal of Molecular Biology, 1994