Panmap: Scalable phylogeny-guided alignment, genotyping, and placement on pangenomes

Panmap is a scalable tool that utilizes a phylogenetically compressed k-mer index to efficiently align, genotype, and place sequencing reads onto mutation-annotated pangenomes containing millions of genomes, significantly reducing computational time and storage requirements compared to existing methods.

The Gist

Imagine you are trying to find a specific person in a crowd of 8 million people.

In the old way of doing this (using traditional tools), you would have to carry a giant, heavy photo album containing a picture of every single person. To find your target, you'd have to flip through millions of pages, comparing faces one by one. It would take hours, you'd need a massive backpack (computer memory) to carry the album, and if the person you were looking for had a slightly different haircut than the photo, you might miss them entirely.

Panmap is like a super-smart, magical GPS that changes the rules of the game. Instead of carrying a photo album of everyone, it carries a family tree and a list of only the differences between family members.

Here is how Panmap works, broken down into simple concepts:

1. The "Family Tree" Shortcut

Most genetic tools treat every genome (the genetic code of a virus, bacteria, or person) as a completely separate, unique file. Panmap realizes that most of these genomes are actually cousins. They share 99.9% of their DNA.

• The Old Way: Storing 8 million genomes is like storing 8 million copies of the same book, where only one sentence is different in each copy. It's a waste of space.
• The Panmap Way: Panmap stores one master book and a tiny notebook that says, "On page 42, Cousin A changed the word 'cat' to 'bat', and Cousin B changed it to 'rat'."
• The Result: Instead of needing a warehouse to store the data, Panmap shrinks the entire library down to the size of a single paperback. It's 600 times smaller than other tools.

2. The "Magic Compass" (Phylogenetic Placement)

When you have a new sample (like a virus from a wastewater pipe or a drop of ancient blood), you need to figure out where it fits in the family tree.

• The Old Way: You have to align the new sample against every single reference genome one by one. It's like asking every person in the crowd, "Are you my target?"
• The Panmap Way: Panmap uses the family tree structure. It looks at the new sample and asks, "Which branch of the family tree does this look most like?" It skips the irrelevant branches instantly.
• The Speed: It can place a new virus sample onto a tree of 8 million genomes in under two minutes. That's faster than you can brew a cup of coffee.

3. Finding the Needle in the Haystack (Metagenomics)

Imagine you have a smoothie made of 10 different fruits (a mix of different virus strains). You want to know exactly how much of each fruit is in the mix.

• The Old Way: You try to separate the fruits by taste, but if the fruits are very similar, you get confused and miss the subtle flavors.
• The Panmap Way: Panmap tastes every single drop of the smoothie and instantly knows, "This drop tastes like Strawberry, this one like Blueberry." It can even detect fruits that aren't in the original recipe (new mutations) because it understands the flavor profile of the whole family tree.
• The Benefit: This is huge for wastewater surveillance. It can tell public health officials exactly which virus variants are spreading in a city, even if the sample is dirty or the virus is mutated.

4. Time Travel (Ancient DNA)

Sometimes scientists find DNA that is thousands of years old. It's broken into tiny, dusty fragments.

• The Old Way: You try to fit these tiny fragments into a modern reference. If the ancient DNA is too different from the modern one, the pieces don't fit, and you throw them away.
• The Panmap Way: Because Panmap understands the ancestors (the great-great-grandparents in the family tree), it can place these ancient fragments onto the tree even if they don't match any living person perfectly. It's like recognizing a great-grandchild by their nose, even if they have a different hairstyle.
• The Result: Panmap found five times more ancient mammoth DNA in frozen soil samples than previous methods, revealing a clearer picture of the past.

Why This Matters

Think of Panmap as the upgrade from a flip phone to a smartphone for genetic analysis.

• Before: You needed a supercomputer to analyze a few thousand viruses.
• Now: You can analyze millions of viruses on a standard laptop.
• Impact: This means scientists can track pandemics in real-time, detect new variants the moment they appear, and study ancient history without needing massive, expensive servers. It turns a task that used to take days into a task that takes seconds.

In short, Panmap doesn't just look at the data; it understands the story behind the data, allowing it to find answers faster, cheaper, and more accurately than ever before.

Technical Summary

Technical Summary: Panmap – Scalable Phylogeny-Guided Alignment, Genotyping, and Placement on Pangenomes

1. Problem Statement

Pangenome approaches, which utilize multiple reference genomes to capture population-level genetic diversity, have become essential in genomics. However, current methods face significant scalability bottlenecks:

• Graph-Based Limitations: Tools like VG and Minigraph represent variation as sequence graphs. While powerful, they require massive memory and time for indexing and read alignment, making them impractical for pangenomes containing millions of genomes (e.g., global SARS-CoV-2 datasets).
• Preprocessing Dependencies: Existing phylogenetic placement tools (e.g., EPA-ng, pplacer, UShER) typically require reads to be pre-aligned, assembled, or converted into VCFs before placement. This discards reads that fail to map to a single reference and limits sensitivity in low-coverage or degraded samples (e.g., ancient DNA).
• Reference Bias: Single-reference methods struggle with highly diverse populations, leading to systematic errors and poor coverage in regions divergent from the reference.

2. Methodology

Panmap introduces a novel framework that leverages the Pangenome Mutation-Annotated Network (PanMAN) format. Instead of storing full sequences for every genome, PanMAN encodes variation as mutations along the branches of a phylogenetic tree.

Core Algorithm: Phylogenetically Compressed k-mer Index

• Delta Encoding: Panmap traverses the PanMAN phylogeny once. Instead of indexing k-mers for every genome independently, it stores only the differences (delta) in k-mer seed presence between a parent node and its child.
• Seed Selection: It uses linked syncmers (k-mers where the lexicographically smallest s-mer is at the start or end) as seeds. By default, it uses 3-linked syncmers ($l=3$) to chain seeds, providing specificity even for short reads.
• Index Construction: The index is a compact, depth-first list of nodes and mutation records. This allows the reconstruction of any genome's seed set by traversing from the root and applying branch-specific changes.
• Compression: This approach exploits the high similarity between closely related genomes, reducing index size by up to 600-fold compared to graph-based or phylo-k-mer indices.

Operational Modes

Panmap operates in two distinct modes:

1. Single-Sample Mode:
   • Placement: Reads are decomposed into seeds. Panmap performs a single tree traversal, scoring all seeds collectively against every node to find the optimal reference haplotype (sampled or inferred ancestor).
   • Alignment & Genotyping: Once the best reference is identified, reads are aligned to that specific sequence (using Minimap2 or bwa-aln for ancient DNA). Genotype likelihoods are calculated using a mutation spectrum prior derived from the phylogeny.
   • Output: Placement report, BAM alignments, VCF genotypes, and consensus FASTA.
2. Metagenomic Mode:
   • Independent Scoring: Each read is scored independently against the index.
   • Deconvolution: An Expectation-Maximization (EM) algorithm estimates the relative abundance of constituent haplotypes.
   • eDNA Application: Includes competitive mapping filters (low seed-hit, phylogenetic ambiguity, and coverage evenness) to assign reads to taxa in complex environmental samples without prior alignment.

3. Key Contributions

• Scalability: Panmap enables read mapping and placement on pangenomes containing millions of genomes (demonstrated on 8 million SARS-CoV-2 genomes), a scale previously intractable for graph-based aligners.
• Alignment-Free Placement: It performs phylogenetic placement directly from raw sequencing reads, eliminating the need for pre-alignment or assembly, thereby recovering signal from reads that would otherwise be discarded.
• Extreme Efficiency: The phylogenetic compression reduces index construction time by three orders of magnitude and index size by hundreds of times compared to VG Giraffe and IPK/EPIK.
• Ancestral Inference: The method can place reads onto inferred ancestral sequences at internal nodes, providing a suitable reference even when the query diverges from all sampled leaf nodes.

4. Results and Performance

• Indexing Efficiency:
  • For 20,000 SARS-CoV-2 genomes, Panmap built a 7.3 MB index in 3 seconds.
  • In contrast, VG Giraffe required a 4.5 GB index and 7.5 hours; IPK/EPIK failed to index the dataset.
  • For 8 million SARS-CoV-2 genomes, Panmap built a 2.5 GB index in 1 hour 20 minutes.
• Placement Speed & Accuracy:
  • Placed a 100× coverage SARS-CoV-2 sample onto 20,000 genomes in 0.4 seconds and onto 8 million genomes in under 2 minutes.
  • Achieved high accuracy (median placement within 0–5 mutations of the true position) across all coverage levels (0.5× to 100×) and read lengths (down to 10 bp).
• Genome Assembly:
  • Outperformed single-reference pipelines (BWA+iVar, Clockwork) in consensus accuracy, particularly at low coverage (0.5×). At 0.5× coverage, Panmap achieved 91% RSV genome recovery vs. 15% for BWA+iVar.
• Metagenomics & Wastewater:
  • Accurately estimated haplotype abundances in simulated SARS-CoV-2 mixtures with up to 20 unobserved SNPs per haplotype.
  • On real wastewater data, Panmap matched the accuracy of WEPP (a state-of-the-art tool) but ran >10x faster.
• Ancient DNA (eDNA):
  • Applied to 2-million-year-old sediment DNA, Panmap identified significantly more high-confidence Elephantidae reads (4,098) compared to traditional competitive mapping (846), and provided deeper phylogenetic placements than pathPhynder.

5. Significance

Panmap represents a paradigm shift in pangenomic analysis by decoupling scalability from computational cost through evolutionary compression. Its ability to handle millions of genomes directly from raw reads makes it uniquely suited for:

• Real-time Pathogen Surveillance: Rapidly processing global viral datasets (e.g., SARS-CoV-2, HIV) for lineage tracking and variant detection.
• Low-Quality/Complex Samples: Enabling analysis of ancient DNA and wastewater metagenomics where reference bias and low endogenous content are major hurdles.
• Resource-Constrained Environments: Drastically reducing the memory and time requirements for pangenome analysis, democratizing access to large-scale genomic data.

By integrating phylogenetic structure directly into the indexing and mapping process, Panmap transforms pangenomes from static reference collections into dynamic, computationally tractable frameworks for evolutionary and epidemiological inference.