PLAST

PLAST performs local alignment searches of DNA sequence queries against graphical pangenomes to identify biologically meaningful homologous regions.

Key Features:

• Graphical Pangenome Representation: PLAST uses compacted colored de Bruijn graphs to represent pangenomes, enabling low-memory, reference-free sequence comparisons.
• Heuristic Alignment Methodology: It employs a seed-and-extend heuristic to traverse the sequence graph and identify maximum scoring local alignments, with outputs compatible with NCBI BLAST standard formats.
• Statistical Filtering: PLAST applies an alignment statistic developed for sequence-to-graph alignments to filter biologically meaningful alignments and distinguish true homologs from spurious matches.
• Performance and Scalability: The method scales sublinearly with respect to the number of genomes by exploiting sequence similarity within the pangenome.
• Comparative Analysis: PLAST enables comparison of sequence similarity within the pangenome to assess homology and evolutionary relationships.

Scientific Applications:

• Pangenomic Research: Facilitates comprehensive analysis of species genetic diversity by enabling local alignment searches across multiple genomes.
• Genomic Comparisons: Supports reference-free comparisons to study genomic variation without relying on a single reference genome.
• Evolutionary Studies: Aids inference of evolutionary relationships and sequence homology through local alignments within pangenomes.

Methodology:

PLAST uses compacted colored de Bruijn graphs and a seed-and-extend heuristic to traverse the sequence graph and find maximum scoring local alignments, applies an alignment statistic for sequence-to-graph alignment filtering, and emits outputs compatible with NCBI BLAST standard formats; the method scales sublinearly with the number of genomes.