Description:
Homology search is a key tool for understanding the role, structure, and biochemical function of genomic sequences. BLAST is the most popular homology search tool and is used to run millions of queries each day.
However, evaluating such queries is slow and can take minutes on a modern workstation. Therefore, continuing evolution of BLAST - by improving its algorithms and optimisations - is essential to improve search times in the face of exponentially-increasing collection sizes.
In this talk I will describe the algorithm used by BLAST to efficiently search large genomic collections, and propose a new step in the BLAST algorithm to reduce the computational cost of searching with negligible effect on accuracy. After including an optimisation of the local alignment recursion, this new step roughly doubles the speed of the gapped alignment stages in BLAST.
This work was conducted by myself, Dr Hugh E. Williams and Dr Adam Cannane at RMIT University, Australia. Dr Hugh E. Williams is now a Senior Software Design Engineer at Microsoft MSN Search.
Speaker(s):
Michael Cameron, Ph.D. candidate, School of Computer Science and IT, RMIT University
|
