Estimating seed sensitivity on homogeneous alignments

Gregory Kucherov, Laurent Noé, Yann Ponty

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationProceedings - Fourth IEEE Symposium on Bioinformatics and Bioengineering, BIBE 2004
PublisherIEEE Computer Society
Pages387-394
Number of pages8
ISBN (Print)0769521738, 9780769521732
DOIs
Publication statusPublished - 2004
Externally publishedYes
EventProceedings - Fourth IEEE Symposium on Bioinformatics and Bioengineering, BIBE 2004 - Taichung, Taiwan, Province of China
Duration: 19 May 200421 May 2004

Publication series

NameProceedings - Fourth IEEE Symposium on Bioinformatics and Bioengineering, BIBE 2004

Conference

ConferenceProceedings - Fourth IEEE Symposium on Bioinformatics and Bioengineering, BIBE 2004
Country/TerritoryTaiwan, Province of China
CityTaichung
Period19/05/0421/05/04

Fingerprint

Dive into the research topics of 'Estimating seed sensitivity on homogeneous alignments'. Together they form a unique fingerprint.

Cite this