Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333038 | Journal of Computer and System Sciences | 2005 | 22 Pages |
Abstract
This work addresses the problem of designing a seed to optimize performance of seeded alignment. We give a fast, simple algorithm based on finite automata for evaluating the sensitivity of a seed in a Markov model of ungapped alignments, along with extensions to mixtures and inhomogeneous Markov models. We give intuition and theoretical results on which seeds are good choices. Finally, we describe Mandala, a software tool for seed design, and show that it can be used to improve the sensitivity of alignment in practice.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jeremy Buhler, Uri Keich, Yanni Sun,