Improved gapped alignment in BLAST genomic search

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 Bios

Michael Cameron is a PhD candidate in the School of Computer Science and IT at RMIT University, Australia. He is working on improving the efficiency and accuracy of homology search techniques, and the BLAST algorithm in particular, under the supervision of Dr Hugh E. Williams and Dr Andrew Turpin. He is a member of the RMIT Search Engine Group. His research interests include homology search, sequence alignment, and data structures and algorithms. He received the BCompSc(Hons) degree from Monash University in 2001.

Date:
Haut-parleurs:
Michael Cameron
Affiliation:
RMIT University, Australia