Le 29/03/2023 par Ronan :

Encadrants : Emmanuel Néron et Ronan Bocquillon.

Lieu : Tours, Laboratoire d’Informatique Fondamentale et Appliquée de Tours (LIFAT).

Financement : Bourse doctorale de la Région Centre-Val de Loire.

Début de la thèse : Octobre 2023.

Mots-clés : Recherche opérationnelle, graphe, bio-informatique.

Consignes pour candidater : Envoyer un CV, une lettre de motivation, vos relevés de notes de master (ou équivalent) par courriel à emmanuel.neron@univ-tours.fr et ronan.bocquillon@univ-tours.fr. Vous pouvez y joindre des lettres de recommandation.

Sujet :

Nous avons travaillé ces dernières années à la mise en place d’outils pour la comparaison de graphes hétérogènes, avec des applications en bio-informatique. Nous pensons que poursuivre ces travaux présente un intérêt scientifique : d’une part pour mettre au point de nouvelles méthodes de comparaison et les tester, y compris sur des données réelles ; d’autre part pour parfaire notre compréhension des enjeux biologiques sous-jacents [1, 2, 3].

Il s’agit d’une ouverture sur des problématiques jusqu’ici peu abordées au LIFAT, et propices à des collaborations multidisciplinaires (informatique, bio-informatique, biologie). Des premiers contacts ont été pris avec des collègues du laboratoire Biomolécules et Biotechnologies Végétales (BBV, EA 2106), travaillant sur des problèmes proches.

Le problème traité, NP-difficile au sens fort [4, 5], se pose comme suit. Soient un graphe orienté D (représentant un réseau métabolique) et un graphe non-orienté G (représentant la proximité des gènes produisant les protéines en jeu), tous deux définis sur le même ensemble de sommets. Le problème consiste à trouver un plus long chemin dans D, tel que le sous-graphe de G engendré par les sommets de ce chemin est connexe. On cherche donc une plus longue voie métabolique impliquant des protéines produites par des gènes voisins. Nous nous intéressons à la recherche des chemins élémentaires et non-élémentaires, dits trails. Ces chemins constituent des marqueurs des espèces et peuvent servir à leur comparaison [6].

Nous souhaitons dans le cadre de la thèse proposée :

1. Explorer plus en avant ce problème de comparaison de graphes hétérogènes, en modélisant le problème du plus long trail, et en adaptant les différentes méthodes exactes développées (modélisations mathématiques, programmation par contraintes), jusqu’à leur application sur des données réelles. Des méthodes par décomposition pourront être envisagées.

2. Modéliser les critères de comparaison d’espèces dans les problèmes de recherche d’un plus long chemin et d’un plus long trail, en vue de trouver une famille de chemins ou de trails adaptée à cette comparaison. Il est envisagé que dans cette dernière modélisation des chemins bicritères soient considérés (longueur et disparité par exemple).

3. Ouvrir ce travail à d’autres problèmes pertinents concernant les réseaux métaboliques modélisés par des graphes. Nous considérerons en particulier le problème de l’énumération des ensembles de précurseurs minimaux [7, 8].

Les compétences recherchées sont :

• une bonne connaissance des outils de la recherche opérationnelle et de l’IA, tels que la théorie des graphes, la programmation linéaire et/ou la programmation par contraintes,
• un intérêt pour les problèmes biologiques et une curiosité pour adapter ces compétences à ce domaine,
• une capacité à discuter avec des chercheurs non-informaticiens.

Références :

[1] Mohamed Lemine Ahmed Sidi. Nouvelles approches informatiques et mathématiques pour la résolution de problèmes biologiques. Thèse de doctorat. Université de Tours. 2022.

[2] Mohamed Lemine Ahmed Sidi, Ronan Bocquillon, Hafedh Mohamed Babou, Cheikh Dhib, Mohamedade Farouk Nanne, Emmanuel Néron and Ameur Soukhal. Improved approaches to solve the One-To-One SkewGraM problem. Computers and Operations Research. 2021.

[3] Mohamed Lemine Ahmed Sidi, Ronan Bocquillon, Hafedh Mohamed Babou, Cheikh Dhib, Mohamedade Farouk Nanne, Emmanuel Néron et Ameur Soukhal. Un modèle de programmation par contraintes pour la recherche d'un chemin DG-consistant dans des réseaux biologiques. Congre?s annuel de la Socie?te? Franc?aise de Recherche Ope?rationnelle et d’Aide a? la De?cision. 2021.

[4] Guillaume Fertin, Christian Komusiewicz, Hafedh Mohamed Babou and Irena Rusu. Finding supported paths in heterogeneous networks. Algorithms. 2015.

[5] Hafedh Mohamed Babou. Comparaison de réseaux biologiques. Thèse de doctorat. Université de Nantes. 2012.

[6] Alexandra Zaharia, Bernard Labedan, Christine Froidevaux and Alain Denise. CoMetGeNe: mining conserved neighborhood patterns in metabolic and genomic contexts. BMC Bioinformatics. 2019.

[7] Ricardo Andrade, Martin Wannagat, Cecilia C. Klein, Vicente Acuña, Alberto Marchetti-Spaccamela, Paulo V. Milreu, Leen Stougie and Marie-France Sagot. Enumeration of minimal stoichiometric precursor sets in metabolic networks. Algorithms for Molecular Biology. 2016.

[8] Vicente Acuña, Paulo Vieira Milreu, Ludovic Cottret, Alberto Marchetti-Spaccamela, Leen Stougie and Marie-France Sagot. Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. Bioinformatics. 2012.