iiinova — where your digital self keeps evolving

Karel Břinda @brinda.eu · 05/12/2025

8/9 Empirics on genomes / pan- / meta- / sampled: • FMSI uses ~2–3× less RAM than SBWT/SSHash • SBWT with particularly space-tuned params can match space in some cases, but FMSI is then usually 2–4× faster

110

Karel Břinda @brinda.eu · 05/12/2025

4/9 Core idea: index shortest superstrings. Masked superstring (S, M): a single sequence S containing all k-mers, plus a mask M marking the real ones. MBWT indexes (S, M) by carrying the mask in SA order → exact index over any k-mer set (incl. sampled).

110

Karel Břinda @brinda.eu · 11/04/2025

Does this scale? Yes. Fast, parallel, and batchable. A comput. cluster can phylogenetically compress millions of genomes overnight (+much more speedup still possible). Compression gains? 1–3 orders of magnitude, depending on the structure of data. SW: github.com/karel-brinda... 11/

100

Karel Břinda @brinda.eu · 11/04/2025

Here's the protocol: 1️⃣ Cluster genomes via species (e.g. Kraken) 2️⃣ Split into size/diversity-balanced batches 3️⃣ Build phylogenies (e.g. Mash+NJ) 4️⃣ Reorder+compress (e.g. XZ) Works for: 🧬 Assemblies 🧬 de Bruijn graphs 🧬 Bloom filters 🧬 k-mer indexes 🧬 sketches General principle, many use cases. 10/

100

Karel Břinda @brinda.eu · 11/04/2025

But doesn't this require phylogenetic inference? Isn’t that hard? Yes and no. No need for perfect trees – just rough evolutionary orderings – cheap to compute. We split genomes into phylogenetically related batches, then reorder each batch via a tree. Enough for big compression gains. 9/

111

Karel Břinda @brinda.eu · 11/04/2025

In our bookshelf analogy, redundancies once separated by tens of kilometers now sit just decimeters apart. So even basic compressors can easily pick them up. Here's what the resulting structure looks like in Bloom filters (columns = genomes, rows = k-mer hashes). Highly locally compressible! 8/

101

Karel Břinda @brinda.eu · 11/04/2025

The number of sequenced microbes is growing exponentially, but computational power grows at a slower rate. The result? BLAST – the "Google of biology" – can search only a fraction of sequenced microbes, and that fraction is shrinking exponentially over time. 2/

142

Karel Břinda @brinda.eu · 11/04/2025

A decade ago, we had thousands of bacterial genomes. Now, we have millions. How to scale computational methods? Our paper in @naturemethods.bsky.social answers this: use evolutionary history to guide compression and search. rdcu.be/eg4OA w/ @baym.lol, @zaminiqbal.bsky.social et al. 🧵1/

316037