Equipe : Bonsai (LIFL, INRIA-LNE)
Encadrants : Maude Pupin et Laurent Noé (prenom.nom@lifl.fr)
Point de départ :
Plusieurs bases de données généralistes de molécules biologiques mettent à disposition
gratuitement leurs données (PubChem, PDB) qui comprennent, entre autre, la structure
chimique des molécules sous un format standard tel que SMILES ou SDF et leurs activités
biologiques. Les structures chimiques peuvent être représentées sous la forme d'un graphe
d'atomes dont les arêtes sont les liaisons covalentes entre ceux-ci. Il existe déjà des
librairies (OpenBabel) qui offrent des fonctions de manipulation des formats courants
et de recherche d'une molécule dans une autre, entre autre. Les informations présentes
dans les bases, ainsi que les logiciels existants sont
utilisés dans les domaines pharmaceutiques et biotechnologiques pour découvrir de nouvelles
molécules exploitables économiquement. Des méthodes informatiques sont développées pour
faciliter ces découvertes en se basant sur le principe que deux molécules ayant des
structures (2D ou 3D) et/ou des propriétés physico-chimiques similaires ont de fortes chances
d'avoir la même activité. Ce principe, appelé QSAR pour Quantitative structure-activity
relationship (Kubinyi, 2002 ; Nikolova and Jaworska, 2003), a atteint ses limites dans sa
capacité de prédiction (Doweyko, 2008).
A côté de ces bases généralistes, des bases
spécialisées se concentrent sur un spectre de données répondant à des critères précis comme l'activité (APD), les particularités structurales (Cybase) ou le mode de
synthèse (Norine). Ces bases offrent des informations spécifiques au domaine choisi, en
complément des informations fournies par les bases spécialisées. L'équipe de recherche Bonsai (LIFL et INRIA-LNE) travaille en bio-informatique
et a conçu la base de données de référence sur les peptides non-ribosomiques, appelée Norine, en collaboration avec des microbiologistes
du laboratoire ProBioGEM de l'Université Lille 1. Ces peptides sont synthétisés par certains
micro-organismes via des complexes enzymatiques appelés synthétases. Les peptides
non-ribosomiques ont une grande diversité de structures qui leur confèrent des activités
intéressantes telles que antibiotique, anti-tumeur ou encore prévention du rejet des greffes.
Leurs structures sont constituées de plus de 500 composés (briques) de base, appelés
monomères (acides aminés, mais aussi lipides, glucides ou autre), alors que les
peptides et protéines "classiques" n'en comptent que 20. Elles peuvent contenir des cycles
et/ou des branchements, alors que les peptides et protéines "classiques" sont linéaires.
C'est pourquoi, dans Norine, les peptides non-ribosomiques sont représentés sous la forme de
graphes de monomères, c'est-à-dire un graphe non orienté dont les noeuds sont les monomères
et les arêtes les liens chimiques entre ces monomères. Dans les articles scientifiques, les
peptides sont majoritairement représentés par leur structure chimique (graphe d'atomes).
Problématique :
Nous avons déjà démontré que la composition en monomères est déterminante pour
l'activité des peptides non-ribosomiques (Caboche et al., 2010 ; Abdo et al., 2012).
Il est donc utile de pouvoir convertir automatiquement les graphes d'atomes, disponibles
dans les banques généralistes, en graphes de monomères tels qu'ils sont définis pour
les peptides non-ribosomiques. D'un point de vue informatique, il s'agit de faire une
recherche de sous-graphes, représentant les monomères, dans un graphe plus grand, représentant les peptides, en maximisant la couverture du graphe.
Dans Norine, nous disposons du graphe d'atomes de tous les monomères et de quelques
centaines de graphes d'atomes pour les peptides, ainsi que le graphe de monomères des
plus de 1100 peptides de la base. Ainsi, il est possible de vérifier si la reconstruction
du graphe de monomères à partir des graphes d'atomes fonctionne correctement.
Un premier programme a déjà été développé et donne des résultats prometteurs.
Travail à réaliser :
- Etudier et concevoir un matching de graphes approché (Mehlhorn, 1984) afin de localiser au mieux les monomères présents dans les peptides.
- Inférer de nouveaux monomères par analyse comparative de graphes (Golumbic, 2004), à partir des molécules fortement couvertes, et ainsi compléter la base de monomères.
- Identifier des substitutions de composés entre différentes molécules. Ainsi, il sera possible d'en déduire des règles et fréquences de substitution qui sont nécessaires à l'alignement de peptides. De plus, ces modèles pourront aider à améliorer le point 2. Ce problème amène à étudier la comparaison multiple de graphes (problème courant en bioinformatique sur les séquences, plus compliqué sur les graphes).
Ces problèmes sont très souvent NP-durs, mais la taille des données nous laisse penser que, dans premier temps, des algorithmes exponentiels arriveront à leurs fins.
Ce stage de Master Recherche Informatique est rémunéré.
Bibliographie :
- Abdo,A. et al. (2012) A new fingerprint to predict nonribosomal peptides activity. J. Comput. Aided Mol. Des., 26, 1187-1194 (article)
- Caboche,S. et al. (2010) Diversity of monomers in non-ribosomal peptides: towards the prediction of origin and biological activity. J. Bacteriol, 192, 5143-5150 (article)
- Doweyko,A. (2008) QSAR: dead or alive? Journal of Computer-Aided Molecular Design, 22, 81-89 (article)
- Kubinyi,H. (2002) From Narcosis to Hyperspace: The History of QSAR. Quantitative Structure-Activity Relationships, 21, 348-356 (article)
- Mehlhorn,K. (1984) Graph algorithms and NP-completeness Springer-Verlag New York, Inc., New York, NY, USA (livre)
- Nikolova,N. and Jaworska,J. (2003) Approaches to Measure Chemical Similarity - a Review. QSAR & Combinatorial Science, 22, 1006-1026 (article)
- Golumbic,M.C. (2004) Algorithmic Graph Theory and Perfect Graphs, Volume 57, Second Edition 2nd ed. North Holland (livre)