# Phylogenetic compression as a core compression technique for extremely large microbial genome collections

Karel Břinda, Zamin Iqbal, Michael Baym

► To cite this version:

Karel Břinda, Zamin Iqbal, Michael Baym. Phylogenetic compression as a core compression technique for extremely large microbial genome collections. Genome Informatics 2024, Nov 2024, Hinxton, Cambridge, United Kingdom. 2024. hal-04842914

HAL Id: hal-04842914

https://inria.hal.science/hal-04842914v1

Submitted on 17 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Phylogenetic compression as a core compression technique for extremely large microbial genome collections

Karel Břinda¹,², Zamin Iqbal³,⁴, Michael Baym²

1 Inria, Univ. Rennes, France; 2 Dpt. of Biomedical Informatics, Harvard Medical School, Boston, USA; 3 EMBL-EBI, UK; 4 Milner Centre for Evolution, University of Bath, UK

## The challenge: exponentially decreasing genome searchability

<figure><img src="image_2.png" /><figcaption>Their BLASTable proportion exponentially decreasing</figcaption></figure>

<figure><img src="image_3.png" /></figure>

## Key idea to regain searchability

**Reordering** genomes according to their **evolutionary history** makes them locally compressible even via simple methods

<figure><img src="image_4.png" /></figure>

## Method: Phylogenetic compression [1]

**Step 1:** cluster / batch genomes via phylogenetic information

<figure><img src="image_5.png" /></figure>

**Step 2:** phylogenetically reorder within each batch (left to right)

<figure><img src="image_6.png" /></figure>

**Step 3:** per-batch compress / index using an arbitrary tool

- compression of assemblies, de Bruijn graphs, sketches, ...

## Results: improv. of 1-3 orders of magnitude

<figure><img src="image_7.png" /><figcaption>**Make searchable on laptops/desktops – Phylign**</figcaption></figure>

<figure><img src="image_8.png" /></figure>

Total CPU time [h] to search 2,826 plasmids across the 661k

**Many recent modifications from the user community**

github.com/allthebacteria/phylign – for AllTheBacteria
github.com/jorgeavilacartes/mof-search – for pan-genomics
github.com/Francii-B/phylign – acceleration for plasmids

## How to use?

### User

Everything **works the same way**, just the data have reduced space requirements and improved searchability **using any method**.

**Example:**
AllTheBacteria [3] and the derived indexes such as [4]

### Genome collection developer

**Step 1:** QC+species ID (e.g., by Kraken / Sylph)

**Step 2:** Batching by Miniphy

**Step 3:** Per-batch tree inference and xz-based compression by Miniphy

**Step 4 (Optional):** Recompression or indexing by specialized tools

### Method developer

**Step 1:** Download a genome collection that was previously phylogenetically compressed (.tar.xz files)

**Step 2:** Apply your low-level compressor / indexer on the batches with the genomes in the same phylogenetic order.

**Useful starting datasets:**
- 661k [2] – the release from https://brinda.eu/mof
- AllTheBacteria [3] – the official release

## Online information

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

## Acknowledgements

Leandro Lima, Simone Pignotti, Natalia Quinones-Olvera, Kamil Salikhov, Rayan Chikhi, Gregory Kucherov, Daniel Anderson, Wei Shen, Jorge Eduardo Avila Cartes, Francesca Brunetti

## References

[1] Břinda & al., Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression, bioRxiv, 2023.

[2] Blackwell & al. Exploring bacterial diversity via a curated and searchable snapshot of archived DNA sequences, PLoS Biol., 2021

[3] Hunt & al., AllTheBacteria - all bacterial genomes assembled, available and searchable, bioRxiv, 2024

[4] Li, BWT construction and search at the terabase scale, arXiv, 2024.