title: Speeding up whole-genome alignment by indexing frequency vectors.
abstract: BACKGROUND
  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.
  
  
  BACKGROUND
  A web-based demo can be found at http://bioserver.cs.ucsb.edu/. Source code is available from the authors on request.
authors.affiliation: Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA 93106-5110, USA. tamer@cs.ucsb.edu
authors.forename: Tamer
authors.initials: T
authors.lastname: Kahveci
authors.forename: Vebjorn
authors.initials: V
authors.lastname: Ljosa
authors.forename: Ambuj K
authors.initials: AK
authors.lastname: Singh
mesh_terms: D030541:Databases, Genetic; D005787:Gene Frequency; D016678:Genome; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software; D014584:User-Computer Interface