Theoretical Foundations of Distances for Phylogenetic Structures

Project Description

Research Project

Phylogenetic structures, including trees and evolutionary networks, are fundamental combinatorial models used to represent complex evolutionary relationships. Their comparison arises in a wide range of problems in computational biology. However, several fundamental questions remain open regarding the mathematical properties of the associated distance measures and the computational complexity of the resulting algorithmic problems.
This research project lies within theoretical computer science and focuses on the mathematical foundations of phylogenetic structure comparison. The work aims to develop new distance measures, establish their theoretical properties, and improve the understanding of computational limits in this context.
Particular attention will be given to the characterization of representation spaces induced by phylogenetic structures, the study of the properties of metrics defined on these spaces, and their impact on comparison problems.
Depending on the selected topic, the research may include:
•	the design of new distance models for phylogenetic trees and networks;
•	the derivation of theoretical results on the metric and combinatorial properties of these distances;
•	the analysis of representation spaces associated with different classes of phylogenetic structures;
•	the study of the computational complexity of fundamental comparison problems;
•	the proof of tractability results or NP-hardness results;
•	the development of exact methods based on algorithm design, parameterized complexity, or combinatorial optimization;
•	the derivation of new results in graph theory, combinatorics, and algorithms applied to phylogenetic structures.
The work is primarily based on mathematical modeling, formal proofs, and complexity analysis. It is intended for candidates interested in contributing to the theoretical foundations of computational biology.

Profile

A strong background in algorithms and discrete mathematics is recommended. An interest in graph theory, computational complexity, mathematical proofs, and theoretical computer science is an asset. Knowledge of bioinformatics or phylogenetics is welcome but not required.
The project is open to Master’s (M.Sc.) and Ph.D. students in Computer Science, Mathematics, or related disciplines.
At the doctoral level, an international co-supervision arrangement may be considered, including collaborations with partners in France or other countries, depending on the candidate’s research interests and the project direction.

Interns are also invited to submit their applications. An internship within this project may serve as an excellent transition toward graduate-level research (master’s or doctoral studies), by providing a gradual introduction to research problems and to the tools developed within the group.

Application

Please send your application to:
Nadia.Tahiri@USherbrooke.ca
Applicants should include the following documents:
•	a curriculum vitae;
•	the most recent academic transcripts;
•	a statement of motivation;
•	a letter of recommendation;
•	two references (name, affiliation, address, and email).

Funding offered

To be discussed

The last update was on 30 June 2026. The University reserves the right to modify its projects without notice.