Abstract
Abstract Background Exhaustive methods of sequence alignment are accurate but slow, whereas heuristic approaches run quickly, but their complexity makes them more difficult to implement. We introduce bounded sparse dynamic programming (BSDP) to allow rapid approximation to exhaustive alignment. This is used within a framework whereby the alignment algorithms are described in terms of their underlying model, to allow automated development of efficient heuristic implementations which may be applied to a general set of sequence comparison problems. Results The speed and accuracy of this approach compares favourably with existing methods. Examples of its use in the context of genome annotation are given. Conclusions This system allows rapid implementation of heuristics approximating to many complex alignment models, and has been incorporated into the freely available sequence alignment program, exonerate.
Keywords
HeuristicsComputational biologyDNA microarrayComputer scienceSequence (biology)BiologyGeneticsGene
Affiliated Institutions
Related Publications
VSEARCH: a versatile open source tool for metagenomics
Background VSEARCH is an open source and free of charge multithreaded 64-bit tool for processing and preparing metagenomics, genomics and population genomics nucleotide sequence...
A Rapid Bootstrap Algorithm for the RAxML Web Servers
Despite recent advances achieved by application of high-performance computing methods and novel algorithmic techniques to maximum likelihood (ML)-based inference programs, the m...
Fast and accurate short read alignment with Burrows–Wheeler transform
Abstract Motivation: The enormous amount of short reads generated by the new DNA sequencing technologies call for the development of fast and accurate read alignment programs. A...
Protein homology detection by HMM–HMM comparison
Abstract Motivation: Protein homology detection and sequence alignment are at the basis of protein structure prediction, function prediction and evolution. Results: We have gene...
Phylogenetic information and experimental design in molecular systematics
Despite the widespread perception that evolutionary inference from molecular sequences is a statistical problem, there has been very little attention paid to questions of experi...
Publication Info
- Year
- 2005
- Type
- article
- Volume
- 6
- Issue
- 1
- Pages
- 31-31
- Citations
- 2984
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
2984
OpenAlex
Cite This
Guy Slater,
Ewan Birney
(2005).
Automated generation of heuristics for biological sequence comparison.
BMC Bioinformatics
, 6
(1)
, 31-31.
https://doi.org/10.1186/1471-2105-6-31
Identifiers
- DOI
- 10.1186/1471-2105-6-31