SlideSort: all pairs similarity search for short reads.

ABSTRACT:

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

SUBMITTER: Shimizu K 

PROVIDER: S-EPMC3035798 | biostudies-literature | 2011 Feb

REPOSITORIES: biostudies-literature