geodesic · · algorithm

geodesic

How it works

01 · Fingerprinting

Each genome gets a unique fingerprint

Every genome's DNA is broken into overlapping 21-letter words (k-mers). These are hashed into 10,000 numerical bins — a compact signature that captures the genome's genetic content without storing the full sequence.

If two genomes share 95% of their DNA, roughly 95% of their fingerprint matches. No alignment needed.

Each dot on the sphere is a genome. Similar genomes cluster together naturally.

02 · Projection

Placing every genome on a sphere

The 10,000-number fingerprint is compressed into a 256-dimensional unit vector — a single point on the surface of a hypersphere. The angle between two points directly encodes their genetic distance.

Genetically identical genomes sit at the same point. Completely unrelated ones sit at opposite poles.

Genetic similarity now equals a dot product — instant to compute at any scale.

03 · Threshold

Learning the strain scale from the data

A spatial index (HNSW) finds each genome's 10 nearest neighbours. The average distance to those neighbours gives an isolation score — high values flag rare lineages and contamination candidates. The k-NN graph's minimum spanning tree (Kruskal's algorithm) is then computed: its longest edge is the natural inter-strain scale at which the population becomes connected, and sets the diversity threshold automatically.

No fixed ANI threshold to tune — the threshold is inferred from the shape of the population itself.

Lines show nearest-neighbour connections; the most isolated genome becomes the first representative.

04 · Selection

Choosing representatives to cover all diversity

Greedy farthest-point sampling: at each step, pick the genome most poorly covered by existing representatives. Stop when every genome is within the ANI similarity threshold of some representative.

This guarantees complete diversity coverage with the fewest possible representatives — a minimax coverage problem on the sphere.

Colored circles show each representative's coverage zone. Watch the sphere fill in.

05 · Certification

Verifying every genome is covered

Representatives within the merge threshold are collapsed via Union-Find. Then every non-representative is checked directly against its assigned representative by exact OPH Jaccard — any genome not covered in sketch space is promoted to a representative.

The simulation below is schematic — it shows what the final representative distribution looks like on the sphere, not the certification procedure itself.

Press Simulate to visualise the final representative distribution.

1 / 5

Representatives

Genomes covered

—

Largest gap

—

Status

—

UNIT SPHERE S²⁵⁵

Genome

Representative

Coverage zone