HMMerge: an Ensemble Method for Improving Multiple Sequence Alignment

Abstract

Despite advances in method development for multiple sequence alignment over the last several decades, the alignment of datasets exhibiting substantial sequence length heterogeneity, especially when the input sequences include very short sequences (either as a result of sequencing technologies or of large deletions during evolution) remains an inadequately solved problem. We present HMMerge, a method to compute an alignment of datasets exhibiting high sequence length heterogeneity, or to add short sequences into a given "backbone" alignment. HMMerge builds on the technique from its predecessor alignment methods, UPP and WITCH, which build an ensemble of HMMs for the backbone alignment and add the remaining sequences into the backbone alignment using the ensemble. HMMerge differs from UPP and WITCH by building a new HMM for each query sequence: it uses a novel ensemble approach to combine the HMMs, each weighted by the probability of generating the query sequence, into a single HMM. Then it applies the Viterbi algorithm to add the query sequence into the backbone alignment. We show that using this "merged" HMM provides better accuracy than the current approach in UPP and matches or improves on WITCH for adding short sequences into backbone alignments. HMMerge is freely available at https://github.com/MinhyukPark/HMMerge.