Estimating seed sensitivity on homogeneous alignments
<|reference_start|>Estimating seed sensitivity on homogeneous alignments: 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.<|reference_end|>
@article{kucherov2006estimating,
    title={Estimating seed sensitivity on homogeneous alignments},
    author={Gregory Kucherov (LIFL), Laurent Noe (LIFL), Yann Ponty (LRI)},
    journal={Proceedings of the Fourth IEEE Symposium on Bioinformatics and
  Bioengineering (BIBE), 387-394, 2004},
    year={2006},
    doi={10.1109/BIBE.2004.1317369},
    archivePrefix={arXiv},
    eprint={cs/0603106},
    primaryClass={cs.OH}
}