Name
Title | ||
|---|---|---|
Significant speedup of database searches with HMMs by search space reduction with PSSM family models. |
Abstract | ||
|---|---|---|
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.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.The presented algorithms are implemented in the program PoSSuMsearch2, available for download at http://bibiserv.techfak.uni-bielefeld.de/possumsearch2/.beckstette@zbh.uni-hamburg.deSupplementary data are available at Bioinformatics online. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1093/bioinformatics/btp593 | Bioinformatics |
Keywords | Field | DocType |
protein family,fast database search,subsequent database search,matrices family model,fast fragment chaining,efficient protein family classification,pssm family model,significant speedup,resulting method,sequence database,search space reduction,database search,new method,proteins,sequence alignment,markov chains,computational biology,search space,algorithms | Data mining,Computer science,UniProt,Search engine indexing,Artificial intelligence,Speedup,Position-Specific Scoring Matrices,Chaining,Sequence database,Database search engine,Bioinformatics,Hidden Markov model,Database,Machine learning | Journal |
Volume | Issue | ISSN |
25 | 24 | 1367-4811 |
Citations | PageRank | References |
3 | 0.39 | 34 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Beckstette | 1 | 116 | 5.51 |
| Robert Homann | 2 | 84 | 3.02 |
| Robert Giegerich | 3 | 1616 | 130.26 |
| Stefan Kurtz | 4 | 1301 | 108.50 |