TreQ 0.1 beta

TreQ 0.1 beta maps high-throughput DNA sequencing reads (100 nt to several hundred nt) to reference genomes while improving handling of large edit distances and indels to enable more accurate detection of genetic variation.

Key Features:

• Approximate string matching via geometric embedding: Transforms reads and reference substrings into q-gram frequency vectors and formulates mapping as nearest neighbor queries in that vector space.
• L(1) distance lower bounds: Uses the L(1) distance between q-gram frequency vectors to provide lower bounds for edit distances with affine gap costs.
• Cache-oblivious kd-tree implementation: Employs a cache-oblivious kd-tree for nearest neighbor queries to optimize running times and maintain constant running time and memory for read lengths between 100 and 1000 bp.
• Accuracy for structural variation detection: Demonstrates superior accuracy relative to many popular read mappers across a broad spectrum of structural variants, including large indels and complex rearrangements.

Scientific Applications:

• Genetic Variation Analysis: Determining the spectrum and abundance of genetic variations, including single nucleotide polymorphisms (SNPs) and structural variants.
• Personal Genomics: Mapping individual-specific sequencing reads to reference genomes to support personalized genomic analyses.
• Structural Variation Detection: Detecting large insertions, deletions, and complex genomic rearrangements with improved sensitivity over a wide range of edit distances.

Methodology:

Geometric embedding of q-gram frequency vectors to convert mapping into nearest neighbor queries; use of L(1) distance as lower bounds for edit distances with affine gap costs; and a cache-oblivious kd-tree for nearest neighbor search with constant running time and memory for reads in the 100–1000 bp range.