Efficient computation of spaced seeds
Open Access
- 28 February 2012
- journal article
- Published by Springer Science and Business Media LLC in BMC Research Notes
- Vol. 5 (1), 123
- https://doi.org/10.1186/1756-0500-5-123
Abstract
The most frequently used tools in bioinformatics are those searching for similarities, or local alignments, between biological sequences. Since the exact dynamic programming algorithm is quadratic, linear-time heuristics such as BLAST are used. Spaced seeds are much more sensitive than the consecutive seed of BLAST and using several seeds represents the current state of the art in approximate search for biological sequences. The most important aspect is computing highly sensitive seeds. Since the problem seems hard, heuristic algorithms are used. The leading software in the common Bernoulli model is the SpEED program.Keywords
Other Versions
This publication has 19 references indexed in Scilit:
- SpEED: fast computation of sensitive spaced seedsBioinformatics, 2011
- BFAST: An Alignment Tool for Large Scale Genome ResequencingPLOS ONE, 2009
- SHRiMP: Accurate Mapping of Short Color-space ReadsPLoS Computational Biology, 2009
- Multiple spaced seeds for homology searchBioinformatics, 2007
- A fast and flexible approach to oligonucleotide probe design for genomes and gene familiesBioinformatics, 2007
- PatternHunter: faster and more sensitive homology searchBioinformatics, 2002
- Efficient large-scale sequence comparison by locality-sensitive hashingBioinformatics, 2001
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programsNucleic Acids Research, 1997
- Basic local alignment search toolJournal of Molecular Biology, 1990
- Rapid and Sensitive Protein Similarity SearchesScience, 1985