Accelerated Profile HMM Searches
- PMID: 22039361
- PMCID: PMC3197634
- DOI: 10.1371/journal.pcbi.1002195
Accelerated Profile HMM Searches
Abstract
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.
Conflict of interest statement
The author has declared that no competing interests exist.
Figures
![Figure 1](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g001.gif)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e001.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e002.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e003.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e004.jpg)
![Figure 2](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g002.gif)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e067.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e068.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e069.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e070.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e071.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e072.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e073.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e074.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e075.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e076.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e077.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e078.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e079.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e080.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e081.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e082.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e083.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e084.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e085.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e086.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e087.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e088.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e089.jpg)
![Figure 3](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g003.gif)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e197.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e198.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e199.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e200.jpg)
![Figure 4](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g004.gif)
![Figure 5](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g005.gif)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e257.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e258.jpg)
![formula image](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.e259.jpg)
![Figure 6](https://www.ncbi.nlm.nih.gov/pmc/articles/instance/3197634/bin/pcbi.1002195.g006.gif)
Similar articles
-
Hidden Markov model speed heuristic and iterative HMM search procedure.BMC Bioinformatics. 2010 Aug 18;11:431. doi: 10.1186/1471-2105-11-431. BMC Bioinformatics. 2010. PMID: 20718988 Free PMC article.
-
ParAlign: a parallel sequence alignment algorithm for rapid and sensitive database searches.Nucleic Acids Res. 2001 Apr 1;29(7):1647-52. doi: 10.1093/nar/29.7.1647. Nucleic Acids Res. 2001. PMID: 11266569 Free PMC article.
-
A new generation of homology search tools based on probabilistic inference.Genome Inform. 2009 Oct;23(1):205-11. Genome Inform. 2009. PMID: 20180275
-
Profile hidden Markov models.Bioinformatics. 1998;14(9):755-63. doi: 10.1093/bioinformatics/14.9.755. Bioinformatics. 1998. PMID: 9918945 Review.
-
A Review of Parallel Implementations for the Smith-Waterman Algorithm.Interdiscip Sci. 2022 Mar;14(1):1-14. doi: 10.1007/s12539-021-00473-0. Epub 2021 Sep 6. Interdiscip Sci. 2022. PMID: 34487327 Free PMC article. Review.
Cited by
-
Sticking together: independent evolution of biofilm formation in different species of staphylococci has occurred multiple times via different pathways.BMC Genomics. 2024 Aug 28;25(1):812. doi: 10.1186/s12864-024-10719-y. BMC Genomics. 2024. PMID: 39198733
-
Aspergillus brasiliensis E_15.1: A Novel Thermophilic Endophyte from a Volcanic Crater Unveiled through Comprehensive Genome-Wide, Phenotypic Analysis, and Plant Growth-Promoting Trails.J Fungi (Basel). 2024 Jul 25;10(8):517. doi: 10.3390/jof10080517. J Fungi (Basel). 2024. PMID: 39194843 Free PMC article.
-
Seqrutinator: scrutiny of large protein superfamily sequence datasets for the identification and elimination of non-functional homologues.Genome Biol. 2024 Aug 26;25(1):230. doi: 10.1186/s13059-024-03371-y. Genome Biol. 2024. PMID: 39187866 Free PMC article.
-
Structure and rational engineering of the PglX methyltransferase and specificity factor for BREX phage defence.Nat Commun. 2024 Aug 22;15(1):7236. doi: 10.1038/s41467-024-51629-7. Nat Commun. 2024. PMID: 39174540 Free PMC article.
-
Navigating the human-monkeypox virus interactome: HuPoxNET atlas reveals functional insights.Front Microbiol. 2024 Aug 2;15:1399555. doi: 10.3389/fmicb.2024.1399555. eCollection 2024. Front Microbiol. 2024. PMID: 39155985 Free PMC article.
References
-
- Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990;215:403–410. - PubMed
-
- Krogh A, Brown M, Mian IS, Sjölander K, Haussler D. Hidden Markov models in computational biology: Applications to protein modeling. J Mol Biol. 1994;235:1501–1531. - PubMed
-
- Durbin R, Eddy SR, Krogh A, Mitchison GJ. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge UK: Cambridge University Press; 1998.
Publication types
MeSH terms
Grants and funding
LinkOut - more resources
Full Text Sources
Other Literature Sources
Research Materials
Miscellaneous