Bioinformatics Advance Access originally published online on April 8, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(13) © Oxford University Press 2004; all rights reserved.
Speeding up whole-genome alignment by indexing frequency vectors
Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA 93106-5110, USA
Received on June 21, 2003; revised on January 29, 2004; accepted on February 8, 2004
Advance Access Publication April 8, 2004
Motivation: Many biological applications require the comparison of large genome strings. Current techniques suffer from high computational and I/O costs.
Results: We propose an efficient technique for local alignment of large genome strings. A space-efficient index is computed for one string, and the second string is compared with this index in order to prune substring pairs that do not contain similar regions. The remaining substring pairs are handed to a hash-table-based tool, such as BLAST, for alignment. A dynamic strategy is employed to optimize the number of disk seeks needed to access the hash table. Additionally, our technique provides the user with a coarse-grained visualization of the similarity pattern, quickly and before the actual search. The experimental results show that our technique aligns genome strings up to two orders of magnitude faster than BLAST. Our technique can be used to accelerate other search tools as well.
Availability: A web-based demo can be found at http://bioserver.cs.ucsb.edu/. Source code is available from the authors on request.
Contact: tamer{at}cs.ucsb.edu