Improved gapped alignment in BLAST genomic search

Michael Cameron

School of Computer Science and IT

Date and time: 11.30am-12.30pm, Friday 3rd June, 2005

Venue: 10.08.04

Abstract:

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.

About the speaker:

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 received the BCompSc(Hons) degree from Monash University in 2001.

Seminar Organisation

Seminars are free and open to the general public. No booking is necessary. If you are interested in giving a presentation in this seminar series, or to make suggestions for speakers, please contact Xiaodong Li, the seminar co-ordinator.