title: Optimizing multiple seeds for protein homology search.
abstract: We present a framework for improving local protein alignment algorithms. Specifically, we discuss how to extend local protein aligners to use a collection of vector seeds or ungapped alignment seeds to reduce noise hits. We model picking a set of seed models as an integer programming problem and give algorithms to choose such a set of seeds. While the problem is NP-hard, and Quasi-NP-hard to approximate to within a logarithmic factor, it can be solved easily in practice. A good set of seeds we have chosen allows four to five times fewer false positive hits, while preserving essentially identical sensitivity as BLASTP.
authors.affiliation: School of Computer Science, University of Waterloo, 200 University Ave., West, Waterloo, ON N2L 3G1, Canada. browndg@uwaterloo.ca
authors.forename: Daniel G
authors.initials: DG
authors.lastname: Brown
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D030562:Databases, Protein; D016247:Information Storage and Retrieval / Q000379:methods*; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
chemical_list: D011506:Proteins