gcsa2

gcsa2 constructs a compressed, haplotype-aware full-text index of genetic variation graphs using Burrows-Wheeler Transform-based methods to enable mapping and querying of genomic sequences across complex variation.

Key Features:

• Burrows-Wheeler Transform (BWT)-based indexing: Implements BWT-based indexing techniques tailored for graph structures to produce a compressed full-text index.
• Haplotype-aware indexing: Incorporates haplotype information to distinguish biologically plausible paths in variation graphs from non-biological recombinations.
• de Bruijn graph approximation: Approximates complex variation graphs using de Bruijn graphs with a k parameter typically set at 256 or less, enabling indexing of graphs that include cycles.
• Graph simplification algorithm: Applies a graph simplification algorithm that facilitates k-mer indexing while preserving all essential k-mers present in the haplotypes.
• Query length limitation and accuracy: The order of the de Bruijn graph limits the maximum reliable query length, where queries longer than k may produce false positives while no false negatives are reported.
• Scalability: Scales to whole-genome indices for large datasets, demonstrated on 5008 haplotypes from the 1000 Genomes Project and all 108,070 Trans-Omics for Precision Medicine Freeze 5 chromosome 17 haplotypes.

Scientific Applications:

• Variant calling: Supports variation-aware read mapping and variant calling against graph-based references.
• Genome assembly: Assists assembly-related analyses by indexing alternative sequences represented in variation graphs.
• Comparative genomics: Enables comparison of haplotype-resolved genomic sequences across individuals and populations.
• Whole-genome analyses: Facilitates large-scale whole-genome analyses that require indexing many haplotypes.
• Precision medicine: Applies to precision medicine studies by indexing population-scale haplotype diversity such as datasets from the 1000 Genomes Project and Trans-Omics for Precision Medicine Freeze 5.

Methodology:

Uses BWT-based full-text indexing adapted to graphs, approximates graphs as de Bruijn graphs (k typically ≤256), incorporates haplotype-aware path filtering, employs a graph simplification algorithm that preserves haplotype k-mers, and observes de Bruijn order–dependent query length limits that can produce false positives but not reported false negatives.