Skip to Main content Skip to Navigation
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 metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00001163
Contributor : Laurent Noé <>
Submitted on : Friday, March 24, 2006 - 10:42:41 AM
Last modification on : Tuesday, April 21, 2020 - 1:04:38 AM
Document(s) archivé(s) le : Saturday, April 3, 2010 - 8:45:07 PM

Files

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

380

Files downloads

325