ELaSTIC

ELaSTIC identifies and clusters similar DNA sequences at large scale using an alignment-free MinHash-based similarity estimation to enable construction of sequence similarity graphs for high-throughput sequencing datasets.

Key Features:

• MinHash-based similarity estimation: Employs MinHash to efficiently approximate pairwise sequence similarity without performing pairwise alignment.
• Alignment-free detection: Detects similar sequence pairs using alignment-free methods to reduce computational cost for large datasets.
• Parallel and distributed processing: Scales across thousands of processors with distributed memory to handle large-scale computations.
• Load balancing strategies: Manages computational imbalance using multi-way number partitioning and work stealing techniques.
• Large-scale graph construction: Constructs sequence similarity graphs from millions of DNA sequences.
• High-throughput sequencing compatibility: Designed to process datasets generated by high-throughput sequencing technologies.

Scientific Applications:

• Large-scale similarity detection: Identification of similar sequence pairs within extensive biological sequence collections.
• Sequence clustering: Clustering of similar DNA sequences from massive datasets.
• Sequence similarity graph analysis: Construction and analysis of large-scale sequence similarity graphs.
• High-throughput sequencing data analysis: Analysis of millions of DNA sequences produced by high-throughput sequencing technologies.

Methodology:

Uses a MinHash-based, alignment-free strategy to approximate sequence similarity and builds large-scale similarity graphs with parallel, distributed-memory execution while employing multi-way number partitioning and work stealing for load balancing across thousands of processors.