Skip to Main content Skip to Navigation
New interface
Conference papers

Estimating seed sensitivity on homogeneous alignments

Gregory Kucherov 1 Laurent Noé 1 Yann Ponty 2 
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Laurent Noé Connect in order to contact the contributor
Submitted on : Friday, March 24, 2006 - 10:42:41 AM
Last modification on : Tuesday, October 25, 2022 - 4:18:03 PM
Long-term archiving on: : Saturday, April 3, 2010 - 8:45:07 PM




Gregory Kucherov, Laurent Noé, Yann Ponty. Estimating seed sensitivity on homogeneous alignments. 4th Symposium on Bioinformatics and bioengineering - BIBE'2004, May 2004, Taichung, Taiwan. pp.387-394, ⟨10.1109/BIBE.2004.1317369⟩. ⟨inria-00001163⟩



Record views


Files downloads