PSI

PSI identifies fully-sensitive seed matches in sequence graphs to enable comprehensive read mapping and variant calling while avoiding combinatorial explosion issues in sequence graphs.

Key Features:

• Fully-Sensitive Seed Finding: Identifies all possible seed matches without graph pruning to ensure potential genetic variations are not overlooked during read mapping.
• Hybrid Indexing Approach: Implements a dual-index strategy combining an index over selected paths in the sequence graph and an index over query reads to maintain full sensitivity while managing computational resources.
• Exploitation of Diploid Read Sets: Leverages the property that diploid read sets realize only two alleles per locus to avoid combinatorial explosion in sequence graphs.
• Performance and Efficiency: Demonstrated on simulated and real-world datasets, including a whole human genome graph from the 1000 Genome Project, showing improvements over GCSA2 in index size, query time, and sensitivity.

Scientific Applications:

• Genome assembly: Supports accurate genome assembly.
• Variant calling: Facilitates comprehensive variant calling.
• Population genetic diversity: Enhances understanding of genetic diversity within populations.

Methodology:

Performs fully-sensitive seed finding without graph pruning, uses a dual-index strategy (index over selected paths in the sequence graph plus an index over query reads), and exploits that diploid read sets realize only two alleles per locus.