Projets 2013-14

Le projet consiste en la mise en oeuvre d'un algorithme de recherche de caractéristiques sur-représentées au sein d'un ensemble de gènes par confrontation avec d'autres ensembles de gènes (relation de voisinage). Les caractéristiques/voisinages à rechercher sont constitué(e)s d'ensembles de gènes imbriqués les uns dans les autres selon 3 structures (posets) : (i) arbre, (ii) graphe acyclique orienté ou encore (iii) treillis. Des algorithmes efficaces sont présentés dans [1], et aussi [2] pour la structure en treillis. Vous aurez donc à choisir une des méthodes pour sa mise en oeuvre. Le travail à réaliser se décompose en :

sélection d'une des méthodes (Projet 1, 2 ou 3 ci-desssous)
implémentation sous forme de script(s) Perl
constitution de jeux de données (et éventuellement de scripts pour convertir les données)
utilisation du/des script(s)
remise d'un rapport (conception et réalisation du script, conversion des données, constitution du jeu de test, évaluation, bilan et perspectives. annexe : présentation détaillée du travail de chacun)
présentation orale et démonstration

Projet 1 : Relation de voisinage représenté par un graphe acyclique orienté (DAG)

La représentation sous forme de DAG est la plus générique. Il s'agit de l'algorithme 2 présenté dans [1]. Pour ce projet, il est conseillé d'utiliser la relation de voisinage induite par les annotations de la Gene Ontology. Le site http://www.geneontology.org met à disposition l'ontologie (Downloads->Ontologies) et les associations (Downloads->Annotations).

Une recherche s'effectue comme vue pendant les enseignements (avec le script search_enriched_sets.pl) mais la représentation des ensembles et l'algorithme de recherche seront adaptés.

Pour la génération de jeu de données, il faudra donc intégrer la structure de la Gene Ontology avec des gènes associés. Pour cela, vous pourrez utiliser la librairie goperl. Cette librairie permet de charger la structure puis d'y ajouter des gènes associations à des gènes. Une des partie de ce projet consistera donc à convertir ces informations en un ficher de format simple de la forme suivante : chaque ligne représente un noeud du graphe selon la syntaxe : node_id node_name nb_genes child_node_id?[,child_node_id]* gene_id?[,gene_id]* ROOT?

Exemple extrait de Media:EcolA.go.closure.2012.dag :

# format: dag
# version: 1.0
GO:2001001      biological_process: negative regulation of xylan catabolic process      0       GO:2000916,GO:2000922           
GO:0006285      biological_process: base-excision repair, AP site formation     2       GO:0045007,GO:0045008   MUG,MUTM        
GO:0006284      biological_process: base-excision repair        8       GO:0006285,GO:0006286,GO:0006287,GO:0006288     ALKA,MUG,MUTM,MUTY,NEI,NTH,TAG,UNG      
GO:0015777      biological_process: teichoic acid transport     0                       
ROOT    Gene Ontology   3646    GO:0003674,GO:0005575,GO:0008150                ROOT
GO:0008750      molecular_function: NAD(P)+ transhydrogenase (AB-specific) activity     2               PNTA,PNTB

Commentaires :

ROOT indique la racine
GO:0006285 sert à annoter MUG et MUTM, c'est un descendant de GO:0006284 ; par conséquent ce dernier sert également à annoter MUG et MUTM

Afin de faire une recherche, les étapes requises sont donc : récupérer le DAG de la Gene Onotology, récupérer les associations gene <-> Term GO, intégrer ces 2 informations pour extraire la représentation compacte sous forme de DAG (format de fichier proposé ci-dessous),

Projet 2 : Voisinage représenté par un arbre (tree)

Projet 3 : Voisinage représenté par un treillis (lattice)

Références

Projets 2012-13

Calendrier :

1 octobre : proposition de projets

2 octobre : sélection d'un projet : envoyer un mail indiquant
- le projet choisi
- pour la confrontation ensembliste, l'hypothèse biologique testée et quelles sources de données (et sur quel organisme) vont être confrontées pour tester cette hypothèse.

19 octobre : remise des projets par voie électronique sous la forme :
- un rapport
- les scripts réalisés

Une démo de biomart sera à prévoir pour ceux qui auront choisi le projet n°1.

Contenu du rapport : Le contenu est à adapter un fonction du projet. Dans tous les cas, il faudra

motiver et documenter les choix effectués
décrire les difficultés rencontrées, quelles solutions ont été envisagées, testées, fructueuses ou infructueuses (quoi, pourquoi, comment ?)

Projet 1 : ajout d'une source de données (BioCyc)

Récupérer les données BioCyc prétraitées (lin sur cette page en bas) et :

ajouter à l'instance de serveur BioMart
faire un script python pour récupérer, en fonction de l'espèce spécifiée, un fichier d'entrée pour sookoos pour les données BioCyc à partir des services Web du serveur biomart.
analyser les pathways biocyc en les confrontant avec sookoos à différents autres critères de regroupement (par exemple les données d'expression).
synthétiser et interpréter les résultats de sookoos.

Projet 2 : implémentation d'un module Perl pour sookoos

Implémentation du module

Le module Perl Neighborhood fourni permet actuellement de rechercher des ensembles similaires au sein d'ordres partiels sur les ensembles représentés par soit de simples ensembles (sets), soit une hiérarchie sous forme d'arbre (newick), soit une hiérarchie sous forme de graphe (dag). Il s'agit donc de développer un module Perl Neighborhood::Lattice qui permette de rechercher des ensembles similaires sur un ou des chromosomes.

L'algorithme pour rechercher les ensembles similaires est le suivant :

foreach chromosome
  for i=0..query_length-1
    left_bound = query[i] # position of gene[i] on the chromosome
    next if left_bound == query[i-1]+1 # previous iteration was more pertinent
    for j=i+1..query_length
      right_bound = query[j]
      next if right_bound +1 == query[j+1] # next iteration will be more pertinent
 
      # compute pvalue or dissimilarity
      ...
      # add to results if significant
      ...

Remarque : Attention, dans le cas de chromosome circulaire, il faut adapter la définition de pertinence et la prise en compte de l'intervalle. En effet, deux gènes de l'ensemble requête définissent un intervalle sur le chromosome et en cas de chromosome circulaire il faut prendre le plus petit des 2 intervalles possibles (Qi..Qj ou Qj..Qi).

Les autres méthodes à développer sont les suivantes :

load(filename): pour charger les données.
searchSingleSet(id1, id2, ...): recherche d'ensembles similaires.

Utilisation du module

Confronter différents critères de regroupement avec la localisation des gènes sur le(s) chromsome(s) (String, GO, ...).

Analyser et interpréter les résultats de sookoos.

M2BBS Integration de Donnes Heterogenes - Projets

From silico.biotoul.fr

Contents