Computational complexity of algorithmic problems in bioinformatics

Project Description

This project lies at the intersection of theoretical computer science, algorithm design, and graph theory, with potential applications in computational biology.

In bioinformatics, and more specifically in biological evolution, many practical tools already exist for the analysis of evolutionary trees and networks. However, a rigorous theoretical understanding remains essential in order to determine what can — or cannot — be computed efficiently in this domain.

Evolutionary networks are used to model complex biological phenomena such as hybridization, horizontal gene transfer, and tumor evolution. Several fundamental problems related to these networks remain open from the perspective of algorithmic complexity. For example, for certain distance metrics between evolutionary networks, it is still unknown whether polynomial-time algorithms exist or whether the problems are NP-hard.
The main objective of the project is to study the algorithmic complexity of problems related to the comparison of evolutionary networks under various metrics and combinatorial models. The project may include:
•	analyzing the complexity of distance or similarity problems between evolutionary networks; 
•	designing NP-hardness proofs or polynomial-time algorithms; 
•	studying approximation algorithms for NP-hard problems; 
•	studying parameterized complexity approaches (fixed-parameter tractability); 
•	developing new theoretical tools in algorithms and graph theory applied to evolutionary networks. 
Desired qualifications
•	Strong interest in fundamental research; 
•	Good knowledge of algorithms; 
•	Strong mathematical maturity, particularly in discrete mathematics; 
•	Ability for abstract thinking and interest in theoretical proofs. 

Assets
•	Knowledge of computational complexity; 
•	Knowledge of graph theory. 
•	No knowledge of biology is required.
The project is well suited for students interested in the theoretical foundations of computer science and their applications to modern problems in computational biology.
.

Funding offered

Yes

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