Skip to content

Hifuku (被覆)

GPU-accelerated mapping of the phylogenetic likelihood landscape over tree space.

Hifuku measures how the alignment log-likelihood varies across tree space, rather than returning only the single most likely tree. Each tree is given a position in a two-dimensional coordinate system built from three anchor trees and a height equal to its alignment log-likelihood, computed exactly by the Felsenstein pruning recursion. The result is a map of log-likelihood over that coordinate system. The height is a directly computed likelihood, not a free-energy estimate and not a posterior density, so Hifuku is a mapping tool rather than an optimizer or a posterior estimator.

An elite-archive (MAP-Elites) survey fills the map. The chart is partitioned into niches, and the survey keeps the best (highest log-likelihood) tree found in each niche. Each step selects an occupied niche, varies its elite with a tree move, evaluates the offspring, and places it. The survey halts on discovery saturation, when new niches and elite gains both fall off. This spreads the measurement across the whole chart rather than concentrating near one maximum. All mutable state is GPU-resident on the device path; the CPU survey is the reference for parity.

MAP-Elites is an illumination algorithm, not an optimizer (Mouret & Clune 2015). An optimizer returns the single best tree; an illumination algorithm returns the best tree in each region of a feature space, revealing how fitness varies across it. Hifuku applies this quality-diversity view to phylogenetics, so the output is a map of the likelihood landscape rather than a point estimate.

Core concepts

Global taxon namespace. All alignments share a single taxon table. Coordinates are indexed in the global namespace and masked for taxa absent from a given tree, so maps from different genes are directly comparable once produced from the same shared table.

Two-dimensional coordinate system. Three anchor trees, one neighbor-joining tree per gene, fix a triangle in the plane through their pairwise distances. Any tree is located in the triangle by its barycentric coordinates (lambda1, lambda2, lambda3), computed from its distances to the three anchors. Two coordinates resolve saddles and mixed topologies that a single distance from one reference tree collapses onto the same value.

Normalized branch-score metric. The distance is defined as

\[ d^2 = (1-w) \frac{\mathrm{CBS}^2}{C_{\mathrm{ref}}} + w \frac{\mathrm{RF} }{\mathrm{R}_{\mathrm{ref}}} \]

This is the clade branch score (kuhner1994branch) combined with the Robinson-Foulds count (robinson1981rf), weighted by w in [0, 1] from pure branch length to pure topology. The chart owns a metric instance whose normalizers are the mean CBS^2 and RF over the anchor set, so w means the same across datasets.

Height from the log-likelihood. The height of the map is the alignment log-likelihood, evaluated at each tree by the Felsenstein pruning recursion. It is read directly from the likelihood and does not depend on the survey parameters.

Elite archive. The archive keeps the best tree per niche. Coverage grows as the survey discovers new niches, and elevation improves as it refines the elite within a niche. The archive renders the map elevation, an interpolated surface, and per-elite coordinates for joint analysis.

Quick start

The Python API runs a survey and exposes the intermediate objects:

from hifuku.alignment import load_alignment
from hifuku.anchor_triangle import AnchorTriangle
from hifuku.nj import nj_tree
from hifuku.substitution import jc69
from hifuku.gpu_walk import run_archive_gpu
from hifuku.taxa import TaxonTable

taxa = TaxonTable()
paths = ("geneA.fasta", "geneB.fasta", "geneC.fasta")
alignments = [load_alignment(p, taxa) for p in paths]
anchors = [nj_tree(a, taxa) for a in alignments]      # one NJ anchor per gene
r1, r2, r3 = anchors

triangle = AnchorTriangle.from_anchors(r1, r2, r3)    # chart + owned metric
model = jc69()

result = run_archive_gpu(
    r1, r2, r3, alignments[0], model, start_trees=[r1],
    triangle=triangle, taxon_table=taxa, seed=0,
)
archive = result.archive                              # EliteArchive

archive is an EliteArchive. Read its elites, coordinates, and surface with the accessors in the Elite Archive (CPU) reference. The neighbor-joining anchors and the chart are shared across genes, so per-gene archives land in one common frame.

Requirements

  • aarch64 (Arm), Ubuntu 24.04, CUDA 13, NVIDIA Blackwell (sm_12x)
  • Python environment pinned in env.lock (conda, miniforge3)
  • Install: pip install -e .
  • Run tests: pytest tests/

License

BSD 3-Clause. See LICENSE, and CONSTRAINTS.md for licensing notes on prior art and dependencies.

Bibliography

All prior-art references used in this project. Keys match references/refs.bib.