General Information
| Description | All pairs similarity search for short reads |
| Homepage | http://www.cbrc.jp/~shimizu/slidesort/ |
Publications
SlideSort: all pairs similarity search for short reads
Motivation:
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.
Availability:
Executable binary files and C++ libraries are available at http://www.cbrc.jp/~shimizu/slidesort/ for Linux and Windows.
Contact:
slidesort@m.aist.go.jp; shimizu-kana@aist.go.jp
Supplementary information:
Supplementary data are available at Bioinformatics online.
Related Tools
CUSHAW
Published May 2012
A CUDA compatible short read aligner to large genomes based on the Burrows–Wheeler transform
Shifted Hamming distance
Published January 2015
A fast and accurate SIMD-friendly filter to accelerate alignment verification in read mapping
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
