# Mathematical model of phylogenetic compression

Veronika Hendrychová, Karel Břinda

► To cite this version:

Veronika Hendrychová, Karel Břinda. Mathematical model of phylogenetic compression. DSB 2024 - Workshop Data Structures in Bioinformatics, Mar 2024, Montpellier, France. hal-04842903

HAL Id: hal-04842903

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

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>
Mathematical model of phylogenetic compression

Hendrychová Veronika¹ and Břinda Karel¹

¹Inria Rennes, Bretagne Atlantique, France

**Abstract**

Comprehensive genome collections play a pivotal role in life sciences research. However, their exponential growth outpaces the development of computational capacities, rendering genome storage and analysis increasingly challenging. For instance, the proportion of data searchable using the Basic Local Alignment Search Tool (BLAST) and its successors has been decreasing exponentially over time. While substantial efforts have recently been devoted to the development of highly optimized alignment-based and k-mer based approaches, these have provided rather partial improvements than a systematic solution of the underlying scalability challenge. Recent work introducing so-called phylogenetic compression has shown that by using evolutionary history to guide existing algorithms and data structures, we can improve state-of-the-art methods for compression and search of large and diverse bacterial genome collections by one to two orders of magnitude [1]. However, despite the clear performance improvement with phylogenetic compression, its theoretical foundations are yet to be established. In this talk, we develop the first formal framework to mathematically study the compression capabilities of phylogenetic compression. To do so, we select one specific protocol of phylogenetic compression and also formalize data compression as a general optimization problem. We demonstrate that, although the compression problem itself might be NP-hard, when input data are modeled by simplified, yet realistic, evolutionary models, phylogenetic compression can provide an optimal solution in polynomial time. Finally, we show that the developed framework accurately models the compression improvement observed in practical applications.

**Keywords:** phylogenetic compression, compressive genomics, compression

**References**

[1] K. Břinda et al., “Efficient and Robust Search of Microbial Genomes via Phylogenetic Compression,” bioRxiv, Apr. 2023, doi: 10.1101/2023.04.15.536996.