title: Significant speedup of database searches with HMMs by search space reduction with PSSM family models.
abstract: 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.
authors.affiliation: Center for Bioinformatics, University of Hamburg, Bundesstrasse 43, 20146 Hamburg, Germany. beckstette@zbh.uni-hamburg.de
authors.forename: Michael
authors.initials: M
authors.lastname: Beckstette
authors.forename: Robert
authors.initials: R
authors.lastname: Homann
authors.forename: Robert
authors.initials: R
authors.lastname: Giegerich
authors.forename: Stefan
authors.initials: S
authors.lastname: Kurtz
mesh_terms: 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
chemical_list: D011506:Proteins