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.