Requêtes dans les réseaux d'intéractions protéiques

L'achèvement de l'analyse et du séquençage des génomes de plusieurs organismes a été marqué par une surprise de taille pour les généticiens : l'homme n'a que 25 000 à 30 000 gènes, soit seulement deux fois plus que la mouche du vinaigre (13 600 gènes) et bien moins que le riz (50 000 gènes).

Et si la complexité de l'espèce humaine résidait en partie dans les protéines ? Le nombre et la fonction biologique de la plupart de ces molécules codées par les gènes ne sont pas encore connus. Un même gène peut en effet détenir l'information utile à la fabrication de plusieurs formes d'une même protéine. Ces formes aboutissent à des fonctions très variées, d'où l'intérêt de l'étude des protéines : la protéomique.

Le nombre d'interactions entre protéines est considérable. L'exploration de ces réseaux protéiques complexes nécessite des méthodologies adaptées ainsi que des outils bioinformatiques puissants pour les analyser.

La recherche de voies métaboliques (molecular pathways) au sein de bases de données d'intéractions est un problème important de la bio-informatique. Les recherches récentes se sont limitées à des requêtes simples - sous la forme de chemins ou de réseaux simples (forêts ou graphes ayant une largeur arborescente bornée).

En tenant compte des recherches récentes basées sur la technique de "color coding" de Alon et al. ("color coding" est une technique aléatoire pour trouver des chemins ou cycles simples d'une longueur fixée dans un graphe), l'ojectif premier de ce stage concerne l'extension de la classe des voies métaboliques pouvant être efficacement utilisées dans des requêtes, i.e., fournir des outils algorithmiques permettant de gérer des requêtes sous forme de graphes (généraux) en prenant en compte d'éventuelles erreurs au sein de la requête ou du réseau. En particulier, la classe de graphes ayant un "vertex feedback set" borné (i.e. l'ensemble minimal de sommets à supprimmer d'un graphe pour le rendre acyclique) doit être étudiée. Le second objectif du stage est d'implémenter un outil permettant les requêtes sous forme de graphes. En prenant en compte la taille importante des réseaux à comparer, l'efficacité (en temps) devra être la priorité.

Algorithmique, Programmation (aucune connaissance en biologie n'est, a priori, requise)