SlideSort

SlideSort identifies similar sequence pairs within a pool of strings using edit distance to accelerate sequence-similarity detection for de novo genome assembly, genome-wide alignment, and short-read summarization.

Key Features:

• Exact Algorithm Design: Finds all similar pairs by exact computation of edit distance within a string pool.
• Efficient Pattern Growth Algorithm: Uses a pattern growth algorithm to identify chains of common k-mers and narrow the search space.
• Performance and Scalability: Outperforms traditional backtracking methods such as BWA (Burrows-Wheeler Aligner) for remote matches and scales to tens of millions of sequences.
• Single Link Clustering Functionality: Provides single link clustering to summarize and group short reads.

Scientific Applications:

• De Novo Genome Assembly: Aids assembly from short reads without a reference by identifying similar reads and overlaps.
• Genome-Wide Alignment: Supports genome-scale alignment and comparison by detecting sequence similarity across large datasets.
• Data Summarization and Processing: Summarizes short-read datasets via clustering to streamline downstream processing.

Methodology:

Identifies chains of common k-mers via a pattern growth algorithm to reduce the number of edit distance calculations required.