Designing patterns for profile HMM search.
BACKGROUND
Profile HMMs are a powerful tool for modeling conserved motifs in proteins. These models are widely used by search tools to classify new protein sequences into families based on domain architecture. However, the proliferation of known motifs and new proteomic sequence data poses a computational challenge for search, requiring days of CPU time to annotate an organism's proteome.


RESULTS
We use PROSITE-like patterns as a filter to speed up the comparison between protein sequence and profile HMM. A set of patterns is designed starting from the HMM, and only sequences matching one of these patterns are compared to the HMM by full dynamic programming. We give an algorithm to design patterns with maximal sensitivity subject to a bound on the false positive rate. Experiments show that our patterns typically retain at least 90% of the sensitivity of the source HMM while accelerating search by an order of magnitude.


BACKGROUND
Contact the first author at the address below.
Sun
Yanni
Y
Department of Computer Science and Engineering, Washington University, St Louis, MO 63130, USA. yanni@cse.wustl.edu
Buhler
Jeremy
J
D000465:Algorithms; D020816:Amino Acid Motifs; D000595:Amino Acid Sequence; D001185:Artificial Intelligence; D003198:Computer Simulation; D017124:Conserved Sequence; D008390:Markov Chains; D008956:Models, Chemical; D015233:Models, Statistical; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid