Hidden Markov model speed heuristic and iterative HMM search procedure

By Steve L. Johnson, Sean R. Eddy, Elon Portugaly. 2010

1,249 citations recorded by the source corpus.

BackgroundProfile hidden Markov models (profile-HMMs) are sensitive tools for remote protein homology detection, but the main scoring algorithms, Viterbi or Forward, require considerable time to search large sequence databases.ResultsWe have designed a series of database filtering steps, HMMERHEAD, that are applied prior to the scoring algorithms, as implemented in the HMMER package, in an effort to reduce search time. Using this heuristic, we obtain a 20-fold decrease in Forward and a 6-fold decrease in Viterbi search time with a minimal loss in sensitivity relative to the unfiltered approaches. We then implemented an iterative profile-HMM search method, JackHMMER, which employs the HMMERHEAD heuristic. Due to our search heuristic, we eliminated the subdatabase creation that is common in current iterative profile-HMM approaches. On our benchmark, JackHMMER detects 14% more remote protein homologs than SAM's iterative method T2K.ConclusionsOur search heuristic, HMMERHEAD, significantly reduces the time needed to score a profile-HMM against large sequence databases. This search heuristic allowed us to implement an iterative profile-HMM search method, JackHMMER, which detects significantly more remote protein homologs than SAM's T2K and NCBI's PSI-BLAST.

Subfields: Molecular Biology, Spectroscopy, Probabilistic & Bayesian Methods

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 Spectroscopy

In Probabilistic & Bayesian Methods

Citations in the corpus

High-resolution de novo structure prediction from primary sequence (2022, methodology): “Both these methods need as input evolutionary data in the form of multiple sequence alignments (MSAs) of homologous sequences aligned to the primary one, a technique which has been a staple of structure prediction methods ( 1 , 2 , 4 – 15 ).”
The Pfam protein families database (2011, methodology): “Another important development has been the adoption of the iterative sequence-search program jackhmmer (6) as our principal tool for generating new families.”
Sequence co-evolution gives 3D contacts and structures of protein complexes (2014, methodology): “Each protein from all pairs in our data set was used to generate a multiple sequence alignment (MSA) using jackhmmer (Johnson et al., 2010) to search the UniProt database (UniProt Consortium, 2014)”
Prediction of interresidue contacts with DeepMetaPSICOV in CASP13 (2019, methodology): “For targets for which fewer than 10L sequences were obtained, the query sequence was scanned against a custom sequence database using jackHMMER.(27,28) This custom database is the set union of UniRef100 and the EBI MGnify(29) protein sequences at a sequence identity threshold of 100%.”
Improved Contact Predictions Using the Recognition of Protein Like Contact Patterns (2014, methodology): “For accurate prediction these global contact prediction methods depend on accurate multiple sequence alignments of thousand or even more homologous protein sequences, using alignments from methods such as HHblits [17] and jackhmmer [18].”
Transformer protein language models are unsupervised structure learners (2020, neutral): “Tools like Jackhmmer and HHblits can increase the number and diversity of sequences returned by iteratively performing the search and alignment steps (Johnson et al., 2010; Remmert et al., 2012).”
HMMER web server: 2015 update (2015, background): “Iterative sequence searching is often able to identify similarities to functionally characterised proteins that are not detected with single sequence searching (25), as the residue conservation from a set of related sequences is used to determine position specific amino acid, insert and delete proba”
Recent developments in the CCP-EM software suite (2017, methodology): “ConKit (Simkovic et al., 2017), developed at the University of Liverpool, is a Python interface for the analysis, manipulation and visualization of evolutionary contact predictions from several alternative algorithms: HHblits (Remmert et al., 2012), JackHMMER (Johnson et al., 2010), HHfilter (Remmer”
An Introduction to Sequence Similarity (“Homology”) Searching (2013, background): “Widely used similarity searching programs, like BLAST (Altschul et al., 1997; UNIT 3.3 & 3.4 ), PSI-BLAST (Altschul et al., 1997), SSEARCH (Smith and Waterman, 1981; Pearson, 1991; UNIT 3.10 ), FASTA (Pearson and Lipman, 1988; UNIT 3.9 ), and the HMMER3 (Johnson et al., 2010) programs produce accura”