Skip Navigation



Bioinformatics Advance Access published online on December 18, 2008
Bioinformatics, doi:10.1093/bioinformatics/btn643
This Article
Right arrow Advance Access manuscript (PDF)
Right arrow All Versions of this Article:
25/3/302    most recent
btn643v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Mak, D. Y.F.
Right arrow Articles by Benson, G.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Mak, D. Y.F.
Right arrow Articles by Benson, G.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2008). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

All Hits All The Time: Parameter Free Calculation of Spaced Seed Sensitivity

Denise Y.F. Mak 1 and Gary Benson 2,*

1Graduate Program in Bioinformatics, Boston University, Boston, MA 02215, 2Dept. of Computer Science, Dept. of Biology, Boston University, Boston, MA 02215

*To whom correspondence should be addressed. Ms. Denise Mak, E-mail: dyfmak{at}bu.edu


  Abstract

Motivation: Standard search techniques for DNA repeats start by identifying small matching words, or seeds, that may inhabit larger repeats. Recent innovations in seed structure include spaced seeds (Ma et al. (2002)) and indel seeds (Mak et al. (2006)) which are more sensitive than contiguous seeds. Evaluating seed sensitivity requires 1) specifying a homology model for alignments and 2) assigning probabilities to those alignments. Optimal seed selection is resource intensive because all alternative seeds must be tested (Li et al. (2006)). Current methods require that the model and its probability parameters be specified in advance. When the parameters change, the entire calculation has to be rerun.

Results: We show how to eliminate the need for prior parameter specification by exploiting a simple observation: given a homology model, the alignments hit by a particular seed remain the same regardless of the probability parameters. Only the weights assigned to those alignments change. Therefore, if we know all the hits, we can easily (and quickly) find optimal seeds. We describe an efficient preprocessing step, which is computed once per seed. Then we show several increasingly efficient methods to find the optimal seed when given specific probability parameters. Indeed, we show how to determine exactly which seeds can never be optimal under any set of probability parameters. This leads to the startling observation that out of thousands of seeds, only a handful have any chance of being optimal. We then show how to identify optimal seeds and the boundaries within probability space where they are optimal.

Contact: dyfmak{at}bu.edu

Associate Editor: Dr. Limsoon Wong

Received on September 10, 2008; revised on December 5, 2008; accepted on December 10, 2008

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.