Méthodes exactes pour la détermination d’un plus long chemin DG-consistant dans des réseaux biologiques Mohamed Lemine Ahmed Sidi, Ronan Bocquillion, Hafedh Mohamed Babou, Cheikh Dhib, Mohamedade Farouk Nanne, Emmanuel Neron, Ameur Soukhal To cite this version: Mohamed Lemine Ahmed Sidi, Ronan Bocquillion, Hafedh Mohamed Babou, Cheikh Dhib, Mohamedade Farouk Nanne, et al.. Méthodes exactes pour la détermination d’un plus long chemin DG-consistant dans des réseaux biologiques. ROADEF 2019, 20ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision, Feb 2019, Le Havre, France. ฀hal02400161฀ HAL Id: hal-02400161 https://hal.archives-ouvertes.fr/hal-02400161 Submitted on 12 Dec 2019 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Méthodes exactes pour la détermination d’un plus long chemin DG-consistant dans des réseaux biologiques Mohamed Lemine AHMED SIDI1,2 , Ronan BOCQUILLION1 , Hafedh MOHAMED BABOU2 , Cheikh DHIB2 , Mohamedade Farouk NANNE2 , Emmanuel NÉRON1 , Ameur SOUKHAL1 1 2 Laboratoire d’Informatique Fondamentale et Appliquée de Tours, LIFAT EA 6300, ROOT ERL-CNRS 7002, 64 av. Jean Portalis, 37200 Tours, France mohamedlemine.ahmedsidi@etu.univ-tours.fr, {ronan.bocquillion,emmanuel.neron,ameur.soukhal}@univ-tours.fr Unité de Recherche Documents Numériques et Interaction de l’Université de Nouakchott Al-Asriya, BP 880, Nouakchott, Mauritanie hafedh.mohamed-babou@esp.mr, dhib.cheikh@iscae.mr, farouk@una.mr Mots-clés : recherche opérationnelle, bio-informatique, comparaison de réseaux biologiques, programmation linéaire en nombres entiers, procédure par séparation et évaluation. 1 Introduction Un réseau biologique est une représentation abstraite d’un système biologique. En bioinformatique, ces réseaux sont souvent modélisés par des graphes. Les sommets sont des composants biologiques et les arêtes représentent leurs interactions. En fonction de la nature de ces réseaux, les graphes correspondants peuvent être orientés ou non-orientés. Notre intérêt porte sur la comparaison de deux réseaux biologiques hétérogènes (un réseau d’interaction protéineprotéine et un réseau métabolique). L’objectif principal est d’étudier les relations entre les composants de ces réseaux, pour analyser ou prédire leurs fonctions biologiques. La comparaison de réseaux biologiques est actuellement l’une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques [2], dont l’étude a permis le développement de concepts nouveaux et une réelle avancée scientifique. Cela concerne, par exemple, l’identification de variants génétiques et l’étude de leurs liens avec tel ou tel trait phénotypique (dépistage de pathologie). Ces travaux s’inscrivent dans la continuité de ceux entrepris dans [1] et [3] par Babou et al. Ces derniers ont identifié un problème d’optimisation combinatoire N P-difficile, appelé One-to-One SkewGraM, et défini comme suit. Considérons un graphe orienté D et un graphe non-orienté G, induits sur le même ensemble de sommets V = {1, 2, . . . , n}. Un chemin (D, G)consistant est un chemin dans D, tel que le sous-graphe dans G induit par les sommets de ce chemin est connexe. Le problème One-to-One SkewGraM consiste à calculer le plus long chemin (D, G)-consistant (cf. Figure 1). À notre connaissance, très peu d’études ont été consacrées à la comparaison de réseaux hétérogènes. Dans [1] et [3], pour le problème One-to-One SkewGraM, les auteurs identifient quelques cas polynomiaux. Une méthode exacte de type branch and bound est proposée pour résoudre le cas général. L’approche est la suivante. Soit un graphe D = (V, A) et un graphe non-orienté G = (V, E), tels que D et G sont connexes. Soit l’arc (i, j) ∈ A. Une procédure par séparation et évaluation, appelée ALGOBB, permet de calculer le plus long chemin (D, G)consistant passant par (i, j). Afin de trouver une solution optimale, ALGOBB est rappelé |A| = m fois (à chaque itération, un nouvel arc est considéré). Cette méthode s’avère peu efficace pour résoudre des instances de taille moyenne. 1 2 3 1 2 4 1 2 3 4 5 4 3 5 D 6 6 7 8 D 9 10 2 4 2 3 1 2 3 4 5 4 6 5 G 1 6 7 8 G 9 10 D 1 a. 3 G b. c. FIG. 1 – Exemples de chemins DG-consistants – (a) Le chemin 1 → 2 → 4 n’est pas (D, G)-consistant car le sous-graphe dans G induit par l’ensemble {1, 2, 4} n’est pas connexe. (b) Le plus long chemin dans D est le chemin 1 → 2 → 4 → 5 → 6. Ce chemin n’est pas (D, G)-consistant, car le sousgraphe dans G induit par l’ensemble des sommets {1, 2, 4, 5, 6} n’est pas connexe. Le plus long chemin (D, G)-consistant est le chemin 1 → 2 → 3. (c) Il existe 32 chemins (D, G)-consistants de longueur 4. 2 Approches de résolution exactes Dans cette section, nous proposons deux approches de résolution exactes du problème Oneto-One SkewGraM. La première est basée sur la programmation linéaire en nombres entiers (PLNE). La deuxième s’appuie sur la procédure de branch and bound introduite dans [1, 3]. Le PLNE proposé est original. Un premier ensemble de contraintes correspond à la recherche d’un chemin dans D. Un deuxième vérifie la connexité du sous-graphe dans G induit par les sommets du chemin dans D. Cet deuxième ensemble de contraintes correspond donc à la recherche d’un arbre couvrant. L’objectif est de maximiser la longueur du chemin dans D. Concernant la procédure de branch and bound, pour améliorer l’efficacité de ALGOBB, nous développons de nouvelles bornes inférieures, nous définissons de nouvelles stratégies d’exploration de l’arbre de recherche et nous identifions quelques nouvelles règles de dominance permettant de réduire le nombre de nœuds examinés. 3 Conclusions et perspectives Pour la résolution du problème du plus long chemin DG-consistant, un PLNE et un branch and bound ont été développés. Tous les algorithmes ont été testés sur des instances générées aléatoirement. Des résultats préliminaires seront présentés pendant la conférence. La procédure de branch and bound est à ce jour plus efficace que le PLNE. Références [1] G. Fertin, H. M. Babou, and I. Rusu. Algorithms for subnet-work mining in heterogeneous networks. In Symposium on Experimental Algorithms (SEA), v. 7276, pp 184–194, 2012. [2] H. Ogata, W. Fujibuchi, S. Goto, and M. Kanehisa. A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Research, 28, pp 4021–4028, 2000. [3] H. M. Babou. Comparaison de réseaux biologiques. Thèse de doctorat en Bio-Informatique, Université de Nantes, 2012. 2