Abstract
Large-scale comparison of genomic DNA is of fundamental importance in annotating functional elements of 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 literature suggests that the choice of seed substantially affects the sensitivity of seeded alignment, but designing and evaluating seeds is computationally challenging. This work addresses problems arising in seed design. We give the fastest known algorithm for evaluating the sensitivity of a seed in a Markov model of ungapped alignments, as well as theoretical results on which seeds are good choices. We also describe Mandala, a software tool for seed design, and show that it can be used to improve the sensitivity of alignment in practice.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB |
| Pages | 67-75 |
| DOIs | |
| Publication status | Published - 2003 |
| Externally published | Yes |
| Event | Seventh Annual International Conference on Research in Computational Molecular Biology - Berlin, Germany Duration: 10 Apr 2003 → 13 Apr 2003 |
Conference
| Conference | Seventh Annual International Conference on Research in Computational Molecular Biology |
|---|---|
| Place | Germany |
| City | Berlin |
| Period | 10/04/03 → 13/04/03 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- Biosequence comparison
- Genomic DNA
- Mandala
- Seed design
- Similarity search