Name
Abstract | ||
|---|---|---|
Homology search is a key tool for understanding the role, structure, and biochemical function of genomic sequences. The most popular technique for rapid homology search is blast, which has been in widespread use within universities, research centers, and commercial enterprises since the early 1990s. In this paper, we propose a new step in the blast algorithm to reduce the computational cost of searching with negligible effect on accuracy. This new step驴semigapped alignment驴compromises between the efficiency of ungapped alignment and the accuracy of gapped alignment, allowing blast to accurately filter sequences with lower computational cost. In addition, we propose a heuristic驴restricted insertion alignment驴that avoids unlikely evolutionary paths with the aim of reducing gapped alignment cost with negligible effect on accuracy. Together, after including an optimization of the local alignment recursion, our two techniques more than double the speed of the gapped alignment stages in blast. We conclude that our techniques are an important improvement to the blast algorithm. Source code for the alignment algorithms is available for download at http://www.bsg.rmit.edu.au/iga/. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/TCBB.2004.32 | IEEE/ACM Trans. Comput. Biology Bioinform. |
Keywords | Field | DocType |
sequence alignment,dynamic programming,molecular biophysics,blast,local alignment,indexing terms,genetics,genome sequence,source code | Sequence alignment,Dynamic programming,Computer science,Source code,Smith–Waterman algorithm,Artificial intelligence,Bioinformatics,Machine learning,Recursion | Journal |
Volume | Issue | ISSN |
1 | 3 | 1545-5963 |
Citations | PageRank | References |
25 | 1.39 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Cameron | 1 | 33 | 2.66 |
| Hugh E. Williams | 2 | 1048 | 93.45 |
| Adam Cannane | 3 | 88 | 7.88 |