acactus 0.2.1

acactus is a C++20 accelerator for the common, reference-guided core of Minigraph-Cactus plus a guide-tree progressive aligner. Version 0.2 adds local multi-block mapping, inversions, translocations, repeated traversals, duplications, novel insertions, structural VCF records, and reconstructed internal ancestors. Version 0.2.1 removes the cohort-sized memory wall while preserving 0.2.0's native GFA, VCF, PAF, and MAF bytes.

The project has two deliberately separate execution contracts:

Backend	Purpose	Outputs
Native accelerator	Fast Tier A/B analysis	GFA 1.1, VCF 4.3, local PAF, projected or progressive MAF
Exact upstream	Preserve the installed Cactus contract	HAL, vg/GFA/VCF, GBZ/Giraffe, Toil, liftover, and every upstream option

The native backend is not claimed to be a bit-for-bit Cactus replacement. The exact backend is the default in bin/acactus-full; selecting --backend native is explicit. See equivalence tiers and compatibility limits.

Build and test

Requirements are GNU Make, a C++20 compiler, Python 3 for tests, and zlib development headers.

make -j
make test

Use make clean && make -j NATIVE=1 for a machine-specific binary.

Native pangenome workflow

Input uses the Cactus two-column sample-to-FASTA seqfile. Relative paths are resolved from the seqfile directory; plain and gzip FASTA are accepted.

GRCh38    assemblies/grch38.fa.gz
HG002.1   assemblies/hg002-paternal.fa.gz
HG002.2   assemblies/hg002-maternal.fa.gz

build/acactus pangenome samples.seqfile \
  --reference GRCh38 \
  --out-prefix results/cohort \
  --maf results/cohort.maf.gz \
  --threads 16

This creates cohort.gfa, cohort.vcf, cohort.paf, and the optional MAF. Any output ending in .gz is compressed atomically.

Each query contig is mapped as adaptive local blocks. A block whose identity falls below --split-identity is recursively divided down to --min-chunk-size. Terminal sequence below --min-map-identity remains in the graph as private sequence instead of being forced onto the reference. The important controls are:

--chunk-size 65536
--min-chunk-size 4096
--split-identity 0.85
--min-map-identity 0.55
--query-buffer-mb 16
--variant-buffer-mb 128

These blocks may change reference chromosome or orientation and may revisit a node, allowing GFA paths and VCF records to retain translocations, inversions, duplications, and novel insertions. Every GFA walk is tested by spelling it back to the original FASTA sequence.

Bounded-memory execution

The native pangenome path parses query FASTA incrementally and maps short contigs in bounded batches. It retains compact edit replay data instead of full query and oriented-query copies, represents reference graph nodes as coordinate views, spills sorted VCF event runs once --variant-buffer-mb is reached, and spools GFA walks to a temporary sidecar before the final atomic write.

--query-buffer-mb is a batch target, not a hard rejection threshold: one individual contig larger than the target is still processed. Peak memory thus scales with the reference index, the largest query contig, compact mapping records, and the unique graph/variant complexity rather than all raw query sequence. Temporary files are created beside the requested outputs and removed after success or failure.

Progressive workflow

Progressive mode requires a Newick guide tree before the seqfile entries.

((human:0.01,chimp:0.01):0.02,gorilla:0.03);
human   human.fa
chimp   chimp.fa
gorilla gorilla.fa

build/acactus progressive primates.seqfile --out-maf primates.maf.gz

Child profiles are merged in tree order, and every internal node contributes a consensus ancestral row such as Anc0.ancestral. This is a topology-respecting profile alignment, but it is not Cactus's duplication-aware ancestral graph.

Cactus-compatible front door

Check which exact-backend tools are installed:

bin/acactus-full doctor

The default forwards the complete invocation to official Cactus:

bin/acactus-full pangenome jobstore samples.seqfile \
  --outDir results --outName cohort --reference GRCh38 \
  --gfa --vcf --gbz --giraffe

Select the accelerator for the supported common tier:

bin/acactus-full pangenome --backend native jobstore samples.seqfile \
  --outDir results --outName cohort --reference GRCh38 \
  --gfa --vcf --maxCores 16

Native compatibility output uses cohort.gfa.gz, cohort.raw.vcf.gz, and cohort.paf. Unsupported native flags fail with an actionable error rather than being ignored. bin/cactus-pangenome-fast and bin/cactus-fast are short aliases for this native mode.

Progressive native output can be converted to a star-projection HAL when maf2hal is installed by naming the output .hal. Use the default upstream backend for hierarchical HAL, liftover, duplication-aware homology, or exact Progressive Cactus behavior.

Performance and accuracy

The sparse alignment kernel is currently 29–341× faster than the included quadratic exact baseline at 4–30 kbp. That is an internal algorithm benchmark, not a Cactus comparison. On a mutation-heavy 33 Mbp regression cohort, 0.2.1 used 168,808 KiB peak RSS versus 1,030,024 KiB for 0.2.0 (6.10× lower) while slightly improving median wall time and preserving GFA, VCF, and PAF bytes. See benchmarks for the full conditions and caveats.

Generate a deterministic truth set and validate the native result:

python3 bench/simulate_truth.py \
  --out-dir benchmark-data --acactus build/acactus

Measure both engines on the same input, outputs, resources, and truth gates:

python3 bench/compare_upstream.py \
  --seqfile benchmark-data/input.seqfile \
  --truth benchmark-data/truth.json \
  --reference reference --threads 16 \
  --work-dir benchmark-comparison

The comparison script records wall time, CPU time, peak RSS, graph statistics, VCF overlap, semantic truth metrics, commands, and the resulting speedup. It refuses to print a fabricated upstream speedup when cactus-pangenome is not installed.

License

MIT. See LICENSE.