# Mathematical model of phylogenetic compression

Veronika Hendrychová, Karel Břinda

► To cite this version:

Veronika Hendrychová, Karel Břinda. Mathematical model of phylogenetic compression. SeqBIM 2023 - journées annuelles Séquences en Bioinformatique, Informatique et Mathématiques, Nov 2023, Lille, France. pp.1-2. hal-04842883

HAL Id: hal-04842883

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

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
Abstract

# Mathematical model of phylogenetic compression

Veronika Hendrychová¹*, Karel Břinda¹*

¹Inria, IRISA, Univ. Rennes, 35042 Rennes, France

*Corresponding authors: veronika.hendrychova@etudiant.univ-rennes1.fr, karel.brinda@inria.fr

Abstract

Comprehensive genome collections play a pivotal role in life sciences research. However, their exponential growth exceeds the pace of development of computational capacities, which renders genome storage and analysis increasingly difficult [6]. For instance, the proportion of data searchable using the Basic Local Alignment Search Tool (BLAST) [1] and its successors has been decreasing exponentially over time [5]. While substantial efforts have recently been devoted to the development of highly optimized alignment-based [3, 7] and k-mer based approaches [9], these provide one-time improvements rather than a systematic solution of the underlying scalability challenge.

One fundamental way to address the data explosion has been proposed via so-called compressive genomics [8, 10], a paradigm exploiting the geometrical structure of genomic data to design entropy-scaling algorithms that would be sub-linear in space and time. However, despite its theoretical benefits, compressive genomics has not yet been fully implemented on a large scale in usable tools, due to the underlying practical challenges such as how to efficiently identify redundancies across large and diverse genome collections, especially those arising in bacterial genomics [2, 4].

A recent work introducing a so-called phylogenetic compression, inspired by compressive genomics, has shown that, by using evolutionary history to guide existing algorithms and data structures, we can improve the state-of-the-art methods for compression and search of large and diverse bacterial genome collections by 1–2 orders of magnitude [5]. However, in spite of the clear performance improvement of phylogenetic compression, its theoretical foundations, including a mapping to the previously developed theory of entropy-scaling algorithms, are yet to be established.

In this talk, we develop a formal framework to study the compression capabilities of phylogenetic compression. To do so, we select one protocol of phylogenetic compression and formalize data compression as an optimization problem. We show that despite the fact that the problem itself might be NP-hard (as it can be reformulated as a specific variant of the Traveling Salesman Problem), when input data are modeled by a simplified, yet realistic evolutionary models, phylogenetic compression solves this problem optimally in polynomial time using algorithms that are efficient in practice. Finally, using a series of computational experiments, we demonstrate that these theoretical results well correspond to the compression performance observed in practical applications.
References

[1] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. *J. Mol. Biol.*, 215(3):403–410, Oct 1990.

[2] P. Bradley, H. C. den Bakker, E. P. C. Rocha, G. McVean, and Z. Iqbal. Ultra-fast search of all deposited bacterial and viral genomic data. *Nat. Biotechnol.*, 37(2):152–159, Feb 2019.

[3] B. Buchfink, C. Xie, and D. H. Huson. Fast and sensitive protein alignment using diamond. *Nat. Methods*, 12(1):59–60, Jan 2015.

[4] G. A. Blackwell et al. Exploring bacterial diversity via a curated and searchable snapshot of archived dna sequences. *PLoS Biol.*, 19(11):e3001421, Nov 2021.

[5] 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.

[6] P. Muir et al. The real cost of sequencing: scaling computation to keep pace with data generation. *Genome Biol.*, 17:53, Mar 2016.

[7] H. Li. Minimap2: pairwise alignment for nucleotide sequences. *Bioinformatics*, 34(18):3094–3100, Sep 2018.

[8] P.-R. Loh, M. Baym, and B. Berger. Compressive genomics. *Nat. Biotechnol.*, 30(7):627–630, Jul 2012.

[9] C. Marchet, C. Boucher, S. J. Puglisi, P. Medvedev, M. Salson, and R. Chikhi. Data structures based on k-mers for querying large collections of sequencing data sets. *Genome Res.*, 31(1):1–12, Jan 2021.

[10] Y. W. Yu, N. M. Daniels, D. C. Danko, and B. Berger. Entropy-scaling search of massive biological data. *Cell Syst*, 1(2):130–140, Aug 2015.