title: SlideSort: all pairs similarity search for short reads.
abstract: BACKGROUND
  Recent progress in DNA sequencing technologies calls for fast and accurate algorithms that can evaluate sequence similarity for a huge amount of short reads. Searching similar pairs from a string pool is a fundamental process of de novo genome assembly, genome-wide alignment and other important analyses.
  
  
  RESULTS
  In this study, we designed and implemented an exact algorithm SlideSort that finds all similar pairs from a string pool in terms of edit distance. Using an efficient pattern growth algorithm, SlideSort discovers chains of common k-mers to narrow down the search. Compared to existing methods based on single k-mers, our method is more effective in reducing the number of edit distance calculations. In comparison to backtracking methods such as BWA, our method is much faster in finding remote matches, scaling easily to tens of millions of sequences. Our software has an additional function of single link clustering, which is useful in summarizing short reads for further processing.
  
  
  BACKGROUND
  Executable binary files and C++ libraries are available at http://www.cbrc.jp/~shimizu/slidesort/ for Linux and Windows.
authors.affiliation: Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology, Japan.
authors.forename: Kana
authors.initials: K
authors.lastname: Shimizu
authors.forename: Koji
authors.initials: K
authors.lastname: Tsuda
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software