title: Optimizing multiple spaced seeds for homology search.
abstract: Optimized spaced seeds improve sensitivity and specificity in local homology search. Several authors have shown that multiple seeds can have better sensitivity and specificity than single seeds. We describe a linear programming (LP)-based algorithm to optimize a set of seeds. Theoretically, our algorithm offers a performance guarantee: the sensitivity of a chosen seed set is at least 70% of what can be achieved, in most reasonable models of homologous sequences. In practice, our algorithm generates a solution which is at least 90% of the optimal. Our method not only achieves performance better than or comparable to that of a greedy algorithm, but also gives this area a mathematical foundation.
authors.affiliation: School of Computer Science, University of Waterloo, Waterloo, ON, Canada. j3xu@tti-c.org
authors.forename: Jinbo
authors.initials: J
authors.lastname: Xu
authors.forename: Daniel
authors.initials: D
authors.lastname: Brown
authors.forename: Ming
authors.initials: M
authors.lastname: Li
authors.forename: Bin
authors.initials: B
authors.lastname: Ma
mesh_terms: D000465:Algorithms; D000818:Animals; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D016678:Genome / Q000235:genetics; D006801:Humans; D008390:Markov Chains; D017385:Sequence Homology