Significant speedup of database searches with HMMs by search space reduction with PSSM family models.
BACKGROUND
Profile hidden Markov models (pHMMs) are currently the most popular modeling concept for protein families. They provide sensitive family descriptors, and sequence database searching with pHMMs has become a standard task in today's genome annotation pipelines. On the downside, searching with pHMMs is computationally expensive.


RESULTS
We propose a new method for efficient protein family classification and for speeding up database searches with pHMMs as is necessary for large-scale analysis scenarios. We employ simpler models of protein families called position-specific scoring matrices family models (PSSM-FMs). For fast database search, we combine full-text indexing, efficient exact p-value computation of PSSM match scores and fast fragment chaining. The resulting method is well suited to prefilter the set of sequences to be searched for subsequent database searches with pHMMs. We achieved a classification performance only marginally inferior to hmmsearch, yet, results could be obtained in a fraction of runtime with a speedup of >64-fold. In experiments addressing the method's ability to prefilter the sequence space for subsequent database searches with pHMMs, our method reduces the number of sequences to be searched with hmmsearch to only 0.80% of all sequences. The filter is very fast and leads to a total speedup of factor 43 over the unfiltered search, while retaining >99.5% of the original results. In a lossless filter setup for hmmsearch on UniProtKB/Swiss-Prot, we observed a speedup of factor 92.


BACKGROUND
The presented algorithms are implemented in the program PoSSuMsearch2, available for download at http://bibiserv.techfak.uni-bielefeld.de/possumsearch2/.


BACKGROUND
beckstette@zbh.uni-hamburg.de


BACKGROUND
Supplementary data are available at Bioinformatics online.
Beckstette
Michael
M
Center for Bioinformatics, University of Hamburg, Bundesstrasse 43, 20146 Hamburg, Germany. beckstette@zbh.uni-hamburg.de
Homann
Robert
R
Giegerich
Robert
R
Kurtz
Stefan
S
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D008390:Markov Chains; D010363:Pattern Recognition, Automated / Q000379:methods; D056510:Position-Specific Scoring Matrices; D011506:Proteins / Q000145:classification*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software
D011506:Proteins