Accelerated Profile HMM Searches
By Sean R. Eddy. 2011
6,198 citations recorded by the source corpus.
Profile hidden Markov models (profile HMMs) and probabilistic inference methods have made important contributions to the theory of sequence database homology search. However, practical use of profile HMM methods has been hindered by the computational expense of existing software implementations. Here I describe an acceleration heuristic for profile HMMs, the “multiple segment Viterbi” (MSV) algorithm. The MSV algorithm computes an optimal sum of multiple ungapped local alignment segments using a striped vector-parallel approach previously described for fast Smith/Waterman alignment. MSV scores follow the same statistical distribution as gapped optimal local alignment scores, allowing rapid evaluation of significance of an MSV score and thus facilitating its use as a heuristic filter. I also describe a 20-fold acceleration of the standard profile HMM Forward/Backward algorithms using a method I call “sparse rescaling”. These methods are assembled in a pipeline in which high-scoring MSV hits are passed on for reanalysis with the full HMM Forward/Backward algorithm. This accelerated pipeline is implemented in the freely available HMMER3 software package. Performance benchmarks show that the use of the heuristic MSV filter sacrifices negligible sensitivity compared to unaccelerated profile HMM searches. HMMER3 is substantially more sensitive and 100- to 1000-fold faster than HMMER2. HMMER3 is now about as fast as BLAST for protein searches.
Subfields: Molecular Biology, Computational Biology & Bioinformatics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Molecular Biology
In Computational Biology & Bioinformatics
- Jinbo Xu
- David T. Jones
- Sheng Wang
- Mohammed Alquraishi
- Yang Zhang
- Sergey Ovchinnikov
- Joe G. Greener
- David Baker
Citations in the corpus
- MRFalign: Protein Homology Detection through Alignment of Markov Random Fields (2014, methodology): “At the superfamily level, our method outperforms HHalign and HMMER by ,6% and ,18%, respectively.”
- MGnify: the microbiome analysis resource in 2020 (2019, methodology): “…as IMG / M. Additional functional analyses are also provided in the form of KEGG orthologue (KO) (23) annotations, which are calculated using HMMER (40) and the KOfam library (using a slightly modified form of the profile hidden Markov model (HMM) database of KEGG ortho-logues (41)) on the…”
- Folding membrane proteins by deep transfer learning (2017, background): “The most structurally similar proteins in PDB70 found by DeepSearch (Eddy, 2011) for 5h35E are 5egiA and 5eikA, which have TMscore 0.677 and 0.653 with the native structure of this target, respectively.”
- ProteinNet: a standardized data set for machine learning of protein structure (2019, methodology): “nsortium, 2018) with metagenomic sequences from the Joint Genome Institute (Ovchinnikov et al., 2017) and filtering to include only sequences available prior to CASP start dates (Table 1). JackHMMER (Eddy, 2011) was then used to construct MSAs for every structure by searching the appropriate sequenc”
- HMMER web server: 2018 update (2018, methodology): “The accelerated profile HMM search algorithm in the third generation of the HMMER suite has significantly reduced this computation overhead (3).”