PhD Position F/M Novel computational methods for phylogenetic compression of data structures

Contract type : Fixed-term contract

Level of qualifications required : Graduate degree or equivalent

Fonction : PhD Position

About the research centre or Inria department

The Inria Centre at Rennes University is one of Inria's eight centres and has more than thirty research teams. The Inria Centre is a major and recognized player in the field of digital sciences. It is at the heart of a rich R&D and innovation ecosystem: highly innovative PMEs, large industrial groups, competitiveness clusters, research and higher education players, laboratories of excellence, technological research institute, etc.

Context

The emergence of modern DNA sequencing technologies has revolutionized the life sciences. However, the exponential growth of sequencing data outpaces the expansion of computational capacities, making traditional search methods such as Basic Local Alignment Search Tool (BLAST) [1] and its successors increasingly less effective. To keep up with the volumes of sequencing data being generated, we need novel sublinear approaches that could store and analyze data directly in the compressed domain. However, while it has been shown that genomic data have particular geometrical properties that guarantee the existence of such efficient algorithms [2], [3], the compression of exponentially growing genome collections in a scalable manner remains an unsolved challenge.

A novel approach, called phylogenetic compression, has recently been proposed to address this challenge [4]. The technique builds upon the insight that the redundancies in genomic data have, in fact, a highly predictable structure, mirroring the underlying evolutionary processes. As the evolutionary history of genomes can be rapidly estimated, this history can be embedded directly into the compression and search algorithms to increase their efficiency and scalability. The preliminary results demonstrated remarkable improvements over the state-of-the-art compression methods and suggested its applicability to many diverse data structures across bioinformatics [4].

[1] S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman, “Basic local alignment search tool,” J. Mol. Biol., vol. 215, no. 3, pp. 403–410, Oct. 1990.

[2] P.-R. Loh, M. Baym, and B. Berger, “Compressive genomics,” Nat. Biotechnol., vol. 30, no. 7, pp. 627–630, Jul. 2012.

[3] Y. W. Yu, N. M. Daniels, D. C. Danko, and B. Berger, “Entropy-scaling search of massive biological data,” Cell Syst, vol. 1, no. 2, pp. 130–140, Aug. 2015.

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

Assignment

The objective of this PhD thesis is to develop novel computational techniques and mathematical frameworks for the phylogenetic compression of data structures. The candidate will combine skills in algorithm design and analysis, discrete mathematics, and probability, with a taste for programming and experimenting with big genomic data. One focus of the thesis will be the development of a mathematical framework for formalizing phylogenetic compression as an optimization problem, with the use of data structure modeling based on evolutionary models. Another direction will focus on the development of phylogenetically compressed variants of modern indexing structures, such as those based on de Bruijn graphs, Bloom filters, and sketches. An important aspect of the thesis will be the efficient implementations of the proposed algorithms and experimental evaluations on high-performance computing clusters with large genomic databases. The thesis is expected to provide novel computational solutions to the current challenges and its results may have a direct impact on a range of applications, from search engines for sequence data to infectious disease diagnostics in remote locations.

Benefits package

  • Subsidized meals
  • Partial reimbursement of public transport costs
  • Possibility of teleworking (90 days per year) and flexible organization of working hours
  • Partial payment of insurance costs

Remuneration

Monthly gross salary amounting to 2100 euros for the first and second years and 2200 euros for the third year