Uri Keich (University of California, San Diego):
On designing seeds for similarity search in genomic DNA
Large-scale similarity searches of genomic DNA are of fundamental
importance in annotating functional elements in genomes. To perform
large comparisons efficiently, BLAST and other widely used tools use
seeded alignment, which compares only sequences that can be shown to
share a common pattern or "seed" of matching bases. The choice of seed
substantially affects the sensitivity of seeded alignment, but designing
and evaluating optimal seeds is computationally challenging. In this
talk I will address some of the computational problems arising in seed
design.