Complexité théorique du calcul pour problèmes en biologie computationnelle
Sommaire
- DIRECTION DE RECHERCHE
- Manuel Lafond, Professeur - Département d'informatique
- UNITÉ(S) ADMINISTRATIVE(S)
-
Faculté des sciences
Département d'informatique
- CYCLE(S)
-
2e cycle
3e cycle - LIEU(X)
- Université de Sherbrooke, campus principal
Description du projet
Ce projet se situe à l’intersection de l’informatique théorique, de l’algorithmique et de la théorie des graphes, avec des applications potentielles en biologie computationnelle. En bio-informatique, plus particulièrement en évolution biologique, il existe plusieurs outils pratiques pour l’analyse d’arbres et de réseaux évolutifs. Par contre, une compréhension théorique rigoureuse demeure essentielle afin de déterminer ce qu’il est possible - ou impossible - de calculer efficacement dans ce domaine. Les réseaux évolutifs sont utilisés pour modéliser des phénomènes biologiques complexes tels que l’hybridation, les transferts horizontaux de gènes, ou l’évolution tumorale. Plusieurs problèmes fondamentaux liés à ces réseaux demeurent toutefois ouverts du point de vue de leur complexité algorithmique. Par exemple, pour certaines métriques de distance entre réseaux évolutifs, on ignore encore s’il existe des algorithmes en temps polynomial ou si les problèmes sont NP-difficiles. Le principal objectif du projet est d’étudier la complexité algorithmique de problèmes de comparaison de réseaux évolutifs en considérant différentes métriques et modèles combinatoires. Le projet pourra inclure : • l’analyse de la complexité de problèmes de distance ou de similarité entre réseaux évolutifs; • la conception de preuves de NP-difficulté ou d’algorithmes polynomiaux; • l’étude d’algorithmes d’approximation pour les problèmes NP-difficiles; • l’étude d’approches en complexité paramétrée (fixed-parameter tractability); • le développement de nouveaux outils théoriques en algorithmique et théorie des graphes appliqués aux réseaux évolutifs. Compétences recherchées • Intérêt marqué pour la recherche fondamentale; • Bonnes connaissances en algorithmique; • Bonne maturité mathématique, particulièrement en mathématiques discrètes; • Capacité d’abstraction et intérêt pour les preuves théoriques. Atouts • Connaissances en complexité du calcul; • Connaissances en théorie des graphes; • Aucune connaissance en biologie n’est requise. Le projet convient à des étudiantes et étudiants intéressés par les fondements théoriques de l’informatique et leurs applications à des problèmes modernes en biologie computationnelle.
Discipline(s) par secteur
Sciences naturelles et génie
Génie informatique et génie logiciel, Informatique, Mathématiques appliquées
Financement offert
Oui
La dernière mise à jour a été faite le 15 mai 2026. L’Université se réserve le droit de modifier ses projets sans préavis.