MashMap

MashMap computes approximate local alignment boundaries between long DNA sequences to enable fast, resource-efficient genome-to-genome and assembly-to-genome comparisons and duplication/repeat detection.

Key Features:

• Approximate alignment algorithm: Uses an approximate algorithm to compute local alignment boundaries between long DNA sequences.
• k-mer-based estimation: Uses k-mer-based statistics to estimate alignment boundaries and sequence identity thresholds.
• Configurable thresholds: Allows specification of minimum alignment length and identity threshold for targeted searches.
• Probabilistic guarantees: Provides probabilistic guarantees on output sensitivity for specified parameters.
• Plane-sweep filtering: Implements a plane-sweep based filtering technique that prioritizes higher-scoring alignment intervals and is theoretically optimal.
• Fast mapping modes: Performs fast assembly-to-genome and genome-to-genome mappings.
• Resource efficiency: Demonstrated mapping of an error-corrected NA12878 human assembly to hg38 in ~1 minute using <4 GB memory across eight CPU threads.
• High recall: Achieves recall accuracy exceeding 97% for computed alignment boundaries across multiple datasets.
• Duplication detection: Performs sensitive self-alignments to identify duplications ≥1 kilobase pair with ≥90% identity, yielding coverage about twice current segmental duplication annotations on the UCSC Genome Browser.

Scientific Applications:

• Comparative genomics: Enables comparing different species via genome-to-genome alignments.
• Assembly mapping: Maps draft assemblies to reference genomes for assembly evaluation and placement.
• Repeat and duplication identification: Identifies repetitive regions and detects duplications meeting length and identity thresholds.
• Genome self-alignment: Performs sensitive self-alignments to reveal duplicated and repetitive content within genomes.

Methodology:

Uses k-mer-based statistics to estimate alignment boundaries and identity thresholds, accepts minimum alignment length and identity parameters, computes local alignment boundaries via an approximate algorithm, and applies a plane-sweep based filtering technique that prioritizes higher-scoring alignment intervals while providing probabilistic sensitivity guarantees.