bio-comparative-genomics-whole-genome-alignment

What this skill does

## Version Compatibility

Reference examples tested with: Progressive Cactus 2.9.1+ (ComparativeGenomicsToolkit/cactus; Armstrong 2020 Nature 587:246), Minigraph-Cactus (Hickey 2024 Nat Biotech 42:663; bundled with Cactus 2.5+), HAL toolkit 2.3+ (Hickey 2013 Bioinformatics 29:1341), LASTZ 1.04.22+, UCSC kentUtils for chain/net (Kent 2003 PNAS 100:11484), MUMmer 4.0.0+, minimap2 2.28+, AnchorWave 1.2.5+, progressiveMauve 2.4.0+, sibeliaz 1.2.5+, winnowmap 2.03+ (Jain 2022 Nat Methods 19:705). Toil workflow runner 6.0+ for Cactus on HPC/cloud.

Before using code patterns, verify installed versions match. If versions differ:
- CLI: `cactus --help`, `cactus-pangenome --help`, `halStats --help`, `lastz --version`, `nucmer --version`, `minimap2 --version`
- Python: `pip show toil`, `toil --version`

If code throws `Toil workflow restart failure`, `HAL file corrupted`, `WDL workflow missing`, the Cactus pipeline is Toil-based and requires careful checkpointing; failed runs must be restarted with `--restart`. HAL file versions differ across hal-toolkit releases; pin the version that produced the file.

# Whole Genome Alignment

**"Align these multiple genomes at the base-pair level"** -> Choose between **reference-free** progressive alignment (Cactus / Minigraph-Cactus: produces HAL, no privileged reference) and **reference-anchored** pairwise alignment (LASTZ chains/nets, MUMmer, minimap2: one genome is the reference, queries align to it). The fundamental tradeoff is **scale vs structure**: pairwise pipelines scale linearly per pair but lose multi-way relationships; progressive Cactus scales linearly with a tree but quadratically without and produces ancestrally-coherent alignments. For comparative genomics at vertebrate / mammal scale, Cactus is now the standard substrate (Zoonomia, Hickey 2023; Bird10000 Genomes); for pangenome graph construction, Minigraph-Cactus (Hickey 2024) is the production pipeline.

- CLI: `cactus jobStore seqFile.txt output.hal --binariesMode local` -- reference-free progressive WGA
- CLI: `cactus-pangenome --reference ref name --vcf` -- pangenome graph from genomes
- CLI: `lastz target.fa[multiple] query.fa` then UCSC chain-net pipeline -- pairwise to a reference
- CLI: `minimap2 -ax asm5 ref.fa query.fa | samtools sort` -- fast pairwise for closely related
- CLI: `nucmer --maxmatch ref.fa query.fa` then `dnadiff` -- MUMmer4 pairwise
- CLI: `anchorwave proali --ploidy 4` -- WGD-aware sequence-level synteny alignment

## Algorithmic Taxonomy

| Tool | Approach | Output | Strength | Fails when |
|------|----------|--------|----------|------------|
| Progressive Cactus (Armstrong 2020 Nature 587:246) | LASTZ pairwise -> CAF graph -> BAR -> ancestral assembly per node | HAL multi-genome alignment | Reference-free; scales to 1000s of genomes with phylogenetic tree; ancestral assembly at every internal node | Quadratic without tree; ALSO scaling problems if branch_scale and chaining parameters mis-tuned (Armstrong 2020 Supp Methods) |
| Minigraph-Cactus (Hickey 2024 Nat Biotech 42:663) | minigraph SV graph base + Cactus base-level resolution | Pangenome graph (VCF, GFA, BAM) | Combines structural variation (minigraph) with base-level alignment (Cactus); HPRC standard | Requires reference; designed for intra-species pangenomes (90 human haplotypes) |
| LASTZ + UCSC chain/net (Kent 2003 PNAS 100:11484) | LASTZ local alignments -> chains (collinear) -> nets (one-to-one selection) | Reference-anchored alignment (chain, net, MAF) | Standard for UCSC genome browser tracks; well-validated; pairwise interpretable | Reference-bias; quadratic scaling for N genomes; per-pair manual chain/net pipeline |
| MUMmer4 nucmer (Marçais 2018 PLoS Comp Biol 14:e1005944) | Maximal exact matches -> clustering -> alignment extension | Pairwise alignment (delta format) | Fast for closely related (>= 70% identity); robust | Slow at low identity; pairwise only |
| minimap2 (Li 2018 Bioinformatics 34:3094) | Minimizer-based seeding + base-level alignment | SAM / PAF pairwise | Very fast; preset `-x asm5/10/20` for divergence | Lower accuracy at < 70% identity vs LASTZ |
| AnchorWave (Song 2022 PNAS 119:e2113075119) | CDS/exon anchors -> wavefront alignment | Sequence-level synteny + SV | WGD-aware (ploidy parameter); plant-friendly | CDS-anchored; intergenic resolution limited |
| Progressive Mauve (Darling 2010 PLoS One 5:e11147) | Local collinear blocks (LCBs) -> progressive alignment | Multi-genome bacterial alignment | Bacterial-friendly; handles inversions natively | Slow for > 30 genomes; less common today |
| SibeliaZ (Minkin & Medvedev 2020 Nat Commun 11:6327) | de Bruijn graph + colinear blocks | Bacterial / closely related multi-genome alignment | Scales to 100+ genomes | Highly diverged genomes lose recall |
| HAL toolkit (Hickey 2013 Bioinformatics 29:1341) | Hierarchical Alignment Format | Index, slice, project, extract from HAL | Standard substrate for downstream Cactus tools (TOGA, halSynteny, halLiftover) | HAL file version pinning required |
| Winnowmap2 (Jain 2022 Nat Methods 19:705) | minimap2-derived with masked repetitive minimizers | SAM / PAF | Optimized for highly repetitive regions (centromeres, telomeres) | Niche; for repeat-rich pairwise alignment |
| BLASTZ (legacy) | LASTZ predecessor | Local alignments | Historical; superseded by LASTZ | Use LASTZ instead |
| Multiz (Blanchette 2004 Genome Res 14:708) | Reference-anchored chain-merging | Multi-species MAF | UCSC's older multi-species pipeline | Superseded by Cactus |
| Lagan / mLagan (Brudno 2003) | Local-global hybrid alignment | Pairwise / multi-species | Historical; not actively developed | Use Cactus or LASTZ chain/net |

Methodology evolves; Cactus / Minigraph-Cactus / HAL are now the dominant production pipelines for vertebrate / mammal / plant WGA. LASTZ chains/nets remain the standard for adding a single new species to a reference-anchored ecosystem (UCSC, Ensembl).

## Decision Tree by Experimental Scenario

| Scenario | Recommended approach | Why |
|----------|------------------------|-----|
| Vertebrate clade WGA, 10-500 genomes | Progressive Cactus | Reference-free; phylogenetic-tree guided; HAL output |
| Mammalian Zoonomia-scale WGA, 500-2000 genomes | Progressive Cactus with `--branchScale` tuning + HPC | Cactus scales to 1000s with proper Toil config |
| Plant clade WGA, with WGD | AnchorWave proali OR Cactus | AnchorWave WGD-aware; Cactus more general |
| Bacterial / archaeal genome alignment | progressiveMauve OR SibeliaZ | Designed for compact, rearrangement-rich genomes |
| Single new species added to reference (e.g. UCSC, Ensembl track) | LASTZ + chain/net | Standard reference-anchored pipeline; interpretable |
| Closely related strains / haplotypes (~95% identity) | minimap2 `-x asm5` or MUMmer nucmer | Fast pairwise; sufficient accuracy |
| Cross-species ~70-90% identity | LASTZ with `--strategy` tuned | minimap2 loses accuracy below ~70% |
| Cross-species ~50% identity (e.g. human vs zebrafish) | LASTZ with HoxD55 matrix | Specialized parameters for distant genomes |
| Pangenome graph for variant calling | Minigraph-Cactus or PGGB | See [[pangenome-analysis]] for graph-based variant calling |
| Repeat-rich genome (large mammal, plant) | Cactus with masked input | Pre-mask repeats with RepeatMasker/RepeatModeler2 |
| Centromeric / telomeric alignment | Winnowmap2 | Optimized for repetitive minimizers |
| Comparative annotation projection | Cactus -> TOGA + CESAR (see [[comparative-annotation-projection]]) | Cactus HAL is TOGA input |
| Conservation analysis (phyloP, PhastCons) | Cactus -> hal2maf to MAF for phyloP | MAF format from HAL is the substrate |
| Pairwise alignment for synteny | minimap2 `-x asm5` -> SyRI | See [[synteny-analysis]] |
| Long-read assembly pairwise validation | nucmer + dnadiff | Standard for assembly QC |
| Reference-to-pangenome lift-over | halLiftover or vg paths | HAL coordinate-system tools |

## Per-Tool Failure Modes

### Cact