Adaptation du système de recherche d'événements …sites.univ-provence.fr/evol/images/stories/rapports/Rapport_stage... · Prolog est une abréviation de « PROgrammation LOGique

Adaptation du système de recherche d'événements

génétiques: DAGOBAH, aux génomes bactériens.

Laurent Guijarro,

Master Bioinformatique, Biochimie Structurale et Génomique, Faculté des Sciences de Luminy.

2010

Maîtres de Stage

Mr Pierre PONTAROTTIMr Philippe GOURET

Laboratoire Evolution biologique et modélisation UMR 6632 / IFR48Université de Provence - case 19 - 19 Place Victor Hugo - 13 331 Marseille cedex 03

2

Table des matières

Introduction........................................................................................................................................5

Matériels et méthodes.........................................................................................................................7

1 Prolog.............................................................................................................................................7

2 Figenix............................................................................................................................................9

3 Dagobah.........................................................................................................................................9

4 OrthoMCL (Orthologous Markov Cluster)..................................................................................11

Développement d'outils et résultats................................................................................................13

1 Interface universelle.....................................................................................................................13

2 Étude des groupes orthologues d'OrthoMCL...............................................................................15

2.1 L'analyse syntaxique du fichier de sortie d'OrthoMCL.........................................................15

2.2 Dagobah: agent étude résultat orthoMCL.............................................................................15

2.3 Résultats.................................................................................................................................21

3 Pré-étude d'événements génétiques..............................................................................................23

3.1 Figenix: « pipeline » filtres....................................................................................................23

3.2 Outils mise en forme résultats...............................................................................................25

3.2.1 Séquences orthologues.................................................................................................25

3.2.2 Séquences orphelines...................................................................................................27

3.3 Résultats.................................................................................................................................27

4 Etude d'événement génétique, agent Dagobah transfert horizontal »..........................................29

Conclusion et discussion...................................................................................................................31

Bibliographie.....................................................................................................................................35

Liste des abréviations.......................................................................................................................37

Annexe...............................................................................................................................................39

Résumé...............................................................................................................................................48

3

Figure 1: Arbre de la vie basé sur ARNr ( D'après Pace nr., 2009, Microbiogy and Molecular biology Reviews )

Figure 2: phylogénie Protéobactéria ARNr 16S( D'après Esser c., 2007, The origin of mitochondria in light of a fluid prokaryotic

chromosome model )

4

Introduction

Les nouvelles techniques de séquençage haut débit permettent d'obtenir de nombreuses séquences de génomes complets. Chaque jour les bases de données s'enrichissent de ces nouvelles données. Cette immense source d'information est peu utilisée dans son ensemble par manque de moyens (informatique, humain et budgétaire) .

Le laboratoire au sein duquel j'ai effectué mon stage a développé deux systèmes informatiques complémentaires Figenix (Gouret et al. 2005) et Dagobah (en cours de publication, thèse Gouret 2009). Ils automatisent entièrement le procédé complexe d'étude génomique qui nécessite habituellement une lourde intervention humaine.Leur autonomie est rendu possible grâce à la modélisation du raisonnement humain sous forme de règles logiques et l'intégration d'un système expert. Ce système applique un sous ensemble de ces règles sur un sous ensemble de données qu'il conserve pour valider la question est posée et produire éventuellement de nouvelles données. Le moteur de résolution logique choisi est associé au langage Prolog. (développé par Colmerauer a. et Roussel p., 1971).

Cette automatisation de la phylogénie à la recherche d'événements génétiques permet d'utiliser au mieux l'ensemble des informations du Web.

Dagobah est capable de prédire plusieurs événements génétiques (perte de gène, transfert horizontal, pseudogénisation, recombinaisons, etc...). Il a été développé pour étudier l'évolution des génomes de vertébrés.

Le transfert horizontal est un processus dans lequel un organisme intègre du matériel génétique provenant d'un autre organisme sans en être le descendant. Ce processus est presque inexistant chez les vertébrés. J'ai développé des outils permettant l'étude des génomes d'organismes où le transfert horizontal existe.

J'ai travaillé à partir de séquences de Protéobactéries (figure 1) et plus précisément à partir d'un sous groupe de ces bactéries les Alphaprotéobactéries (figure 2). Nous avons sélectionné 30 espèces de la famille des Ricketsiales, 1 espèce extérieure à cette famille: Caulobacter crescentus et nous avons construit leur arbre de la vie (figure 3). Ces 31 espèces ont leur génome complet disponible sur le NCBI (National Center for Biotechnology Information: http://www.ncbi.nlm.nih.gov/).

Pour permettre à Dagobah d'étudier de façon efficace ces génomes, j'ai intégré à son environnement de travail la base de données nr (Non-redundant protein sequences) du NCBI. J'ai aussi mis en place des filtres pour orienter les analyses vers des agents spécifiques de Dagobah et éviter de faire systématiquement des phylogénies.

5

Figure 3: Arbre de la vie des 31 espèces d'Alphaprotéobactéries sélectionnées pour l'étude.

Les chiffres en vert correspondent aux numéros de taxon (taxid) identifiant une espèce sur le NCBI. Pour les nœuds internes, les chiffres en bleu clair sont les taxid du nœud correspondant sur le site du NCBI. Si le nœud n'est pas présent ont l'identifie avec un chiffre négatif donné de manière arbitraire.

6

Matériels et méthodes

1 Prolog

Prolog est une abréviation de « PROgrammation LOGique » conçu pour implanter un système de communication homme machine en langage naturel.

Un programme Prolog se construit sous forme de règles ou prédicats. On peut définir, par exemple un frère par la règle: « deux frères ont le même père » en Prolog:

frere(X,Y) :- pere(P,X), pere (P,X).

Le lancement d'un programme ProLog commence par la vérification d'un ou plusieurs faits ce qui entraînera la vérification d'autres faits et ainsi de suite.

ProLog se base sur deux concepts fondamentaux l’unification et le « backtracking ». L’unification correspond à la fusion de deux concepts l'affectation et le test d'égalité entre terme ProLog.Le backtracking naturel du ProLog permet d’étudier tous les cas possibles, en effet le backtracking permet en effet de revenir en arrière afin de dérouler l’ensemble des branches de l’arbre des solutions.

Ces deux principes permettent donc d’utiliser les prédicats définis en ProLog soit pour donner des valeurs à des variables, soit pour donner l’ensemble des valeurs répondant aux règles définies par le prédicat.

Par exemple, le programme Prolog donnant deux faits:

pere(paul,jacques).pere(paul,pierre).

En posant la question pere(paul, X) l'interpréteur va tenter d'unifier la variable X avec les faits qu'il connait

pere(paul,X) vrai si X=jacques.

Il va aussi, grâce au backtracking donner toutes les solutions possibles:

ou pere(paul,X) vrai si X=pierre.

L'ajout du prédicat du début (frere(X,Y) vrai si :- pere(P,X), pere (P,Y) est vrai.) à ces deux faits va nous permettre de répondre à une autre question: jacques et pierre sont-il frère? En prolog:

frere(jacques,pierre).

Unification de X avec jacques, de Y avec pierre et de P avec paul donnent un succès Prolog.

7

Figure 4: Architecture technique de DAGOBAH

Les différents agents de Dagobah sont représentés par des cercles. On peut voir aussi les différents éléments extérieurs au système expert qui sont le système Figenix, le serveur web ensembl, l’ontologie et sa base de données PostgreSQl associée utilisée pour le stockage des informations résultantes des études réalisées.

8

L'exécution de Prolog s'appuie sur la librairie GNU PROLOG for JAVA (Plotnikov, 2000). Il est donc possible d'utiliser la puissance de Prolog tout en gardant un univers Java plus adapté à l'utilisation du réseau, la manipulation des fichiers, des bases de données, … en créant des prédicats Prolog en Java.

2 Figenix

Lors d'une étude le biologiste doit préparer un jeu de données, appliquer sur celui-ci des logiciels à base algorithmique, puis appliquer sur les résultats des transformations et sélections issues de son expérience et de sa compétence, puis à nouveau appliquer des logiciels à base algorithmique ..... jusqu'à obtenir les résultats scientifiques permettant de vérifier ou d'infirmer ses hypothèses, ou d'en générer de nouvelles.

Figenix est une plate-forme (4 machines virtuelles java) qui automatise ce type d'étude. Le biologiste choisit des données à étudier, modifie éventuellement les paramètres scientifiques pour les adapter spécifiquement à ses données, lance un procédé automatique (tâche) pouvant enchaîner des dizaines d'étapes, et collecte tous les résultats.

Tout au long de l'exécution d'une instance de pipeline (tâche), le moteur de résolution logique conserve les données biologiques sous forme de faits. Sollicité sur une question, il essaye de vérifier sa véracité et de donner toutes les solutions possibles, s'il y en a plusieurs.

Figenix est une boite à outils pour le biologiste, il est constitué de nombreux pipelines, utilisant ou non le système expert et liant différents outils (Blast, ClustalW, …).

3 Dagobah

Dagobah (1 machine virtuelle java) est un système informatique multi-agents (figure 4) dont l'objectif premier est le placement phylogénétique d'événements génétiques apparus au cours de l'histoire évolutive des génomes.

Un agent Dagobah est un logiciel autonome développé en Prolog qui peut communiquer avec l'ensemble des agents présents.Tous les agents suivent le modèle BDI: Belief Desire Intention. Ils possèdent à tout instant un ensemble de connaissances ou de croyances: Belief, un ensemble d'objectifs qu'il cherche à atteindre: Desire, et un ensemble d'actions qu'il tente de réaliser pour atteindre ces objectifs: Intention. Ainsi une stratégie prend forme pour chaque agent, et constitue un plan d'exécution.

Le plan de chaque agent est constitué de règles du système expert en chaînage avant, c'est à dire qu'ils sont des producteurs de faits sous la forme:

Action 1...Action k | Condition 1... Condition n -> Conclusion 1...Conclusion m Conditions à éliminer 1...Conditions à éliminer z

9

Figure 5: Algorithme d'orthoMCL

Li et al, 2003, Genome Research, OrthoMCL : Identification of Ortholog Groups for Eukaryotic Genomes.

10

Si l'ensemble des conditions (faits) 1 à n est connu du moteur, si au moins une des conclusions (faits) 1 à m n'est présente et si le moteur réalise les actions 1 à k avec succès, alors on considère comme des faits véridiques les conclusions 1 à m et l'on élimine des connaissances du moteur, les conditions indiquées 1 a z.

Le moteur logique fonctionne par itérations successives, à chaque itération l'ensemble des règles définies dans le plan de l'agent sont appliquées à l'ensemble des faits présents (conditions présentes).

4 OrthoMCL (Orthologous Markov Cluster)

Deux gènes homologues, descendant d'un même gène ancestral, sont considérés comme orthologues s'ils sont issus d'un événement de spéciation. Ils sont paralogues s'ils sont séparés par un événement de duplication.

OrthoMCL est un algorithme à l'échelle du génome pour le groupement des séquences de protéines orthologues.

L'algorithme est composé de 5 phases (figure 5) :

– Filtre des séquences. Cette phase permet d'éliminer les séquences qui pourrait perturber l'étude. Exemple: séquence trop petite, ayant trop de codon stop, …

– Blast

– Étude résultats

– Recherche des relations deux à deux: permet d'identifier les relations d'orthologie entre les protéines.

– Cluster en utilisant MCL (Markov algorithme de clustering, Van Dongen 2000) pour regrouper les paires de protéines orthologues.

11

Figure 6: Exemples d'url requêtes qui « interrogent » les différentes bases de données du NCBI

Figure 7: Résultat sous format XML de la requête http://eutils.ncbi.nlm.nih.gov/entrez/eutils/efetch.fcgi?db=taxonomy&id=293613&retmode=xml

permettant d'identifier le parent des Rickettsia canadensis str. McKiel (taxeId 293613).

Figure 8: Partie du code permettant d'obtenir le parent taxId à partir d'un taxId (taxon identifiant du NCBI). Ce code récupère l'information contenue entre les balises

<ParentTaxId>788</ParentTaxId> en utilisant la requête (url) de la figure 7.

12

Développement d'outils et résultats

1 Interface universelle.

Tous les outils du laboratoire sont pensés pour offrir une grande souplesse fonctionnelle. Cette souplesse permet de les faire évoluer facilement en même temps que les concepts. L'architecture de Dagobah doit donc permettre des modifications aisées et multiples, en fragilisant le moins possible sa fiabilité. Dagobah est un logiciel intégratif, il utilise d'autres logiciels distants avec lesquels il communique grâce au réseau (notamment Figenix).

Cette philosophie m'a permis d'utiliser la base de données NR du NCBI , indispensable pour l'étude des génomes bactériens, sans modifier les agents de Dagobah. Cet ajout sans modifications des agents est rendu possible par l'utilisation d'un des fondements du langage Java: l'interface.

Notre interface universelle décrit toutes les méthodes qui seront utilisées par les agents (récupérer une séquence, récupérer le gène à partir de la protéine ou la protéine à partir du gène, des informations,etc...). Un « helper » (une classe java) propre à chaque source d'information extérieure implémente chaque méthode définie par l'interface. Sur Ensembl (base de données disponible à l'adresse http://www.ensembl.org/ et utilisées par le laboratoire pour les eucaryotes) trouver la séquence du gène X ne demande pas la même requête que sur le NCBI.

Grâce à cette interface, il est possible d'ajouter facilement une nouvelle source d'informations, en créant un « helper », NR par exemple, qui implémente l'interface. Pour l'utiliser il faut désigner le bon « helper » de travail au lancement.

Toutes les fonctions (liste en annexe) de cette interface répondent à un besoin des agents. En général, la fonction consiste en une requête sur le site du NCBI (figure 6), puis la récupération du résultats sous forme XML (figure 7) qu'on peut parser (figure 8) pour rechercher une information grâce au parseur XML de java (librairies: javax.xml.parsers.DocumentBuilder, javax.xml.parsers.DocumentBuilderFactory, org.w3c.dom.Document, org.w3c.dom.Element, org.w3c.dom.NodeList). Cette implémentation correspond à 1500 lignes de codes Java.

Aujourd'hui tous les agents de Dagobah peuvent utiliser les informations du NCBI pour leur étude.

13

Figure 9: Partie du fichier de sortie d'orthoMCL.

Figure 10: Grammaire et lexique du parseur OrthoMCL

14

2 Étude des groupes orthologues d'OrthoMCL

2.1 L'analyse syntaxique du fichier de sortie d'OrthoMCL

Le fichier de sortie d'OrhoMCL (figure 9) donne une liste de gènes regroupés dans des groupes d'orthologues. Pour pouvoir utiliser ce fichier, il faut un analyseur syntaxique.

L' OrthoMCLParser que j'ai développé utilise une grammaire sous forme BNF (Backus-Naur form, figure 7) qui permet d'identifier chaque élément du fichier de sortie d'OrthoMcl de façon simple à l'image du principe des poupées russes:

les groupes OrthoMCL sont constitués soit d'un seul groupe soit d'une suite de groupes. Un groupe est constitué d'un identifiant suivi d'une description séparée par deux points. Un identifiant est constitué d'un préfixe (ici PL) suivi d'un nombre. Une description est constituée d'un gène et d'une liste de gènes et ainsi de suite jusqu'à la lettre ou le chiffre.

Le fichier est parcouru élément par élément. Chaque élément est identifié (création d'un objet java) et traité par une méthode qui lui est propre.

Cette mécanique de parcours permet de vérifier la validité du fichier d'entrée. S'il ne respecte pas la grammaire ou le lexique, l'élément « non conforme » provoquera une erreur précise, l'élément X à la position x ne correspond pas à un identifiant.

2.2 Dagobah: agent étude résultat orthoMCL

Le clustering d'orthologues va nous permettre de réaliser une première étude d'événements, directement à partir du fichier de résultats.

Le fichier de sortie orthoMCL regroupe des gènes orthologues et nous donne un groupe d'espèces.

Nous avons nos 31 génomes et donc 31 espèces dans notre arbre de la vie. Pour chaque groupe on peut tagger (mettre une étiquette) les feuilles de façon à indiquer la présence ou l'absence de l'espèce dans notre groupe. À partir de l'annotation des feuilles, l'algorithme de Sankoff (Clemente jc. Et al. 2009) va identifier pour chaque nœud si l'absence ou la présence de l'espèce est plus probable.

Voici un noeud en Prolog:

[name('190650'),taxeid('190650'),species('CAULOBACTER~CRESCENTUS~CB15'),length('0.0'),duplication(false),id('190650'),sankoff(['PL_101782',absent,0])]

Chaque tag identifiable (name, taxeid, species, sankoff, …) par son nom donne une information.

La manipulation des arbres ou encore l’extraction de sous arbres a nécessité l’utilisation d’un outil programmé en ProLog, développé par le laboratoire « Phylopattern » (Gouret p. et al. 2009).

15

Groupe ortoMCL:

PL_101782: rrs0|YP_001495155.1 rrs1|YP_001650426.1 rcs2|NP_360703.1 rbr0|YP_538484.1

Figure 11: Représentation d'un arbre agent orthoMCL pour la recherche d'événement dans un groupe orthoMCL.

Les espèces présentent dans le groupe (rrs0, rrs1, rcs2, rbr0) ont leur feuille entourée. En remontant la présence ou l'absence de l'espèce à chaque nœud, on peut placer les événements dans l'arbre pour expliquer la présence et l'absence de l'ensemble des espèces du groupe. La présence de ces 4 espèces dans ce groupe s'explique par 2 gains et 1 perte.

16

L'arbre ainsi taggé pourra être parcouru par phylopattern pour rechercher un motif particulier soit de gain:

pattern_matching(SankoffTree, @([ [ [_,

[sankoff([_, 'present', _]), id(IdChildApomorphic)]], [_, [sankoff([_, 'absent', _]), id(IdChildPlesiomorphic)]] ], [sankoff([_, 'absent', _]), id(IdParent)] ]), [], _), Motif recherché

ResultsGain),

soit de perte:

pattern_matching(SankoffTree, @([ [ [_,

[sankoff([_, 'present', _]), id(IdChildPlesiomorphic)]], [_, [sankoff([_, 'absent', _]), id(IdChildApomorphic)]] ], [sankoff([_, 'present', _]), id(IdParent)] ]), [], _),

ResultsLosse), Motif recherché

Phylopattern va unifier les variables IdChildApomorphic (caractère dérivé), IdChildPlesiomorphic (caractère de l'ancêtre), IdParent (ancêtre commun) au motif qui correspond pour créer une liste de tous les résultats qu'on pourra afficher:

['GAIN group name : ','PL_101782','Id Parent: ','768',' Apomorphic ','-4','Plesiomorphic ','574556']

J'ai créé un agent de Dagobah pour automatiser ce travail. Il fait une annotation groupe par groupe et taggue avec l'algorithme de Sankoff (déjà intégré à Dagobah) chaque nœud de l'arbre des 31 espèces choisies (Exemple d'arbre pour le groupe PL_101782, figure 8).

Grâce à cet agent on peut détecter des événements en comptant le nombre de gain et de perte dans chaque groupe.

Bien qu'il soit nécessaire de continuer l'étude pour définir plus précisément l'événement, cette approche permet d'orienter les résultats vers un agent de Dagobah précis l'agent de perte de gènes et l'agent transfert horizontal.

→ 0 gain: il y a un gain ancestral avant notre racine qui explique la présence de toutes les espèces dans notre groupe.→ 1 seul gain: agent de transfert uniquement.→ 1 seul gain , n pertes: transfert ou apparition d'un nouveau gène, agent de transfert horizontal et agent de perte de gènes.→ 1 seule perte: étude avec l'agent perte de gènes.

Les autres cas donnent trop de possibilités, une étude complète est nécessaire.

17

Figure 12: Partie du code de l'agent Dagobah orthoMCL: filtre des groupes.

Figure 13: Partie du code de l'agent Dagobah orthoMCL: sélection de la meilleure séquence d'un groupe.

18

Le prédicat filter de l'agent permet de filtrer les groupes (figure 12). Le fait range(1, 1, infinite, 0) permet par exemple de sélectionner tous les groupes ayant 1 unique gain (1 gain minimum, 1 gain maximum) et n pertes (entre 0 est « l'infinie »).Ce prédicat va faire appel au prédicat generate_numbers pour générer tous les termes conformes au fait donné.

generate_numbers(0, 0, MaxEvents, NbLosses, NbGains)

Les deux premiers 0 permettent d'initialiser le nombre de pertes et de gains. MaxEvents est un fait passé en paramètre qui permet d'avoir le nombre maximum d'événements. Pour nos 31 espèces on aura 31 événements maximum.

Le backtracking et l'unification de ces termes à l'ensemble des groupes vont permettre de récupérer tous les groupes ayant un unique gain.

Pour chaque groupe un prédicat récupère l'identifiant du gène sélectionné en fonction d'un ordre de priorité (passé en paramètre). Les génomes les plus étudiés (identifiés par leur taxid) sont prioritaires par rapport aux génomes moins étudiés.

Pour chaque groupe nous avons le nombre de pertes, de gains mais aussi l'identifiant de la meilleure séquence qui nous permettra de lancer une phylogénie.

[Format for ExtractSequencesInFasta.java,PL_102365,334380,YP_001937386.1,1,1,]

Le prédicat choose_best_sequence_in_group récupère un fait passé en paramètre une liste de priorité (species_priority(['190650','69474','784','942','28211'])). Elle liste les taxid (d' espèce: 190650 Caulobacter crescentus CB15, 784 Orientia tsutsugamushi, de genre: 69474 Orientia, d'une famille 942 Anaplasmataceae, d'une classe: 28211 Alphaproteobacteria) par ordre de préférence.

Pour chaque groupe un prédicat fabrique une liste de toutes les séquences de ce groupe (SequencesList). Ce prédicat donne pour chaque groupe une seule séquence représentative du groupe et étant la « meilleure » selon nos critères de priorités. Cette séquence sera unifiée avec la variable Sequence.

Le prédicat prédicat tris (quick_sort) la liste des séquences d'un groupe en fonction de leur espèce (taxid). Il sélectionne la séquence qu'on considère comme la « meilleure » des séquences d'un groupe. Cette séquence sera la première séquence de la liste triée ([Sequence|_]).

Pour pouvoir trier les séquences le prédicat quick_sort (déjà intégré à Dagobah) à besoin d'un comparateur worst_from_two.Ce comparateur utilise la liste de priorités pour comparer deux taxid et donc deux séquences.

À partir du taxid de la séquence, il cherche le parent, le parent du parent, … dans l'arbre de la vie des 31 génomes tant qu'il ne trouve pas un noeud identifié par un taxid de la liste de priorité (en utilisant le prédicat parent_in_speciesPriorityList).

19

Avec ce prédicat le taxid d'une séquence aura un taxid correspondant dans la liste de priorité. En identifiant sa position (prédicat member), le comparateur peut indiquer quel taxid et donc quelle séquence est la meilleure.

2.3 Résultats

0 pertes 1 perte 2 pertes 3 pertes 4 pertes 5 pertes

0 gain 267 653 69 28 9 3

1 gain 0 1292 558 88 39 13

2 gain 0 0 164 132 62 26

3 gain 0 0 0 31 45 24

4 gain 0 0 0 0 5 4

5 gain 0 0 0 0 0 1

La cellule verte indique un gain ancestral qui précède l'apparition de l'ancêtre connu des Alphaprotéobactéries. Tous les autres gains sont des gains plus tardifs. Le fait d'avoir un seul gain peut s'expliquer par un transfert cellules bleues.

Cet agent a environ 500 lignes de code Prolog (on considère généralement que la mise au point d'une ligne de Prolog correspond à la mise au point de 10 lignes de Java).

20

Figure 14: Visualisation du pipeline Filterbacteria avec Jakarta tomcat

Figure 15: Visualisation des résultats de l'algorithme « Blast »

21

3 Pré-étude d'événements génétiques

3.1 Figenix: « pipeline » filtres

Pour étudier les séquences, un pipeline Figenix a été créé. Il est constitué de quatre étapes paramétrables grâce à un fichier XML décrivant chaque brique :

- SequenceProvider transmet au flux du pipeline toutes les séquences une par une.- Blast_remote utilise l'algorithme « Blast » en ligne et de récupérer ses résultat sous format

XML.- Blast_filter récupère l'ensemble des hits résultats de l'algorithme « Blast » ce qui permet

de filtrer les séquences.- Bad Termination ou Termination permet de savoir si le pipeline s'est terminé (avec ou

sans erreur).

Figenix a un site web dynamique développé en Java utilisant un serveur jakarta tomcat.La description de chaque brique, sous forme XML permet de suivre l'avancement du pipeline, de changer facilement les paramètres, (figure 14) et d'avoir les résultats sous forme graphique (figure 15).

Chaque brique est une classe java. En utilisant Blast, on peut identifier des séquences ayant une fortes similarités avec un groupe extérieur ou alors des séquences propre à une espèce. Pour définir un groupe extérieur nous avons mis en place différents scopes (liste des taxid, numéro identifiant une espèce accepté ou refusé)

J'ai créé deux filtres, tous les deux parcourent l'ensemble des hits récupérés à partir du Blast de notre séquence requête. Pour chaque hit une méthode inFamilyTaxon identifie si le taxId est accepté ou refusé. Cette méthode recherche l'espèce parent (le taxid parent) du hit puis le parent du parent et ainsi de suite jusqu'à trouver un taxid du scope ou la racine, si l'espèce du hit n'est pas dans le scope.Le premier filtre le scope -75, -766 donne toutes les séquences n'ayant pas de groupe extérieur aux Caulobacter (75) et au Rickettsiales (766) dans leurs résultats de l'algorithme « Blast » qu'on ajoute au fichier selected_sequences_after_filter.fasta. Ce fichier identifie toutes les séquences spécifiques à ces deux genres. Les autres séquences ont au moins un groupe extérieur (nombre de groupe paramétrable), au minimun1 hit qui n'est pas de la familles des Rickettsiales ou des Caulobacters. Elles seront dans le fichier selected_bad_sequences.fasta. Ce fichier indique les séquences pouvant être le résultat d'un transfert.

22

Figure 16: Stratégie des différents filtres

Figure 17: Partie du code montrant la sélection des séquences du filtre 2

23

Le deuxième filtre étudie les Rickettsiales ou les Caulobacters. Il détecte transferts et pertes pour chaque genre.Il permet en autre d'identifier la position du groupe extérieur, pour affiner nos résultats. Ce filtre compte le nombre de hits dans le premier scope 28211 (Alpaprotéobactérie) puis dans le deuxième soit 69657, 255474, 76892 identifiant les Caulobacters ou 766 identifiant les Rickettsiales et s'arrête dès qu'il trouve un groupe extérieur.

Une séquence sera ajoutée au fichier ResultFilter_HitOutScope.fasta si un groupe extérieur est trouvé à partir des résultats de l'algorithme « Blast ». Ce fichier regroupe toutes les séquences issues d'un transfert. Sinon elle sera ajoutée au fichier au fichier ResultFilter_allHitInScope.fasta pouvant identifier une perte chez Caulobacters ou chez les Rickettsiales selon la séquence de départ.Nous avons paramétré une e-value (valeur reflétant la probabilité de trouver le même résultat par hasard) de 10-10 pour l'algorithme « Blast ». Cette e-value permet un compromis acceptable entre le nombre de résultats et leur fiabilité.

Grâce à ces filtres ont été détecté des pertes et des transferts. Nous pouvons maintenant utiliser l'agent spécifique de Dagobah pour mieux connaître l'événement et le placer sur un arbre. Cette pré-étude ne fait pas seulement gagner du temps, en classant les séquences, elle permet aussi de consolider les outils (vérification orthoMCL, agents Dagobah).Bien qu'utilisant les mêmes filtres, il est nécessaire de séparer deux études: l'étude des gènes n'étant pas dans un groupe d'orthologues (gène orphelin ou spécifique à une espèce) et les gènes orthologues des groupes ayant été identifié par l'agent Dagobah comme ayant un unique gain. Ce dernier le gain peut s'expliquer par l'apparition d'un nouveau gène ou par un transfert horizontal ce que détermine les filtres.

3.2 Outils mise en forme résultats.

3.2.1 Séquences orthologues

Toutes les séquences sont formatées en sortie du filtre 2 sous cette forme:>GI|189183104|REF|334380|YP_001936889_1|ORIENTIA~TSUTSUGAMUSHI~STR|NUMBER_IN_14|NUMBER_BEFORE_14|NUMBER_ALL_20 MLHSSLRNNSIFCLGGNCNTPTIIPNRDIAKVAHLAMLNQMSKDIKTNPVSVFSGKHRKCK

le NUMBER_IN correspond au nombre de hits de l'algorithme « Blast » dans le scope 2 (filtre 2). Le NUMBER_BEFORE correspond au nombre de hits dans le scope 1 et 2 (filtre 2) avant un éventuel groupe extérieur et le NUMBER_ALL correspond au nombre de hits total de l'algorithme « Blast ».

J'ai développé un outil TransfertAnalyser qui utilise ce formatage pour fabriquer deux jeux de données, le premier pour l'étude des tranferts (fichier Result_transfert.fasta), l'autre pour l'étude des pertes (fichier Result_Perte.fasta).

Toutes les séquences du ResultFilter_HitOutScope (fichier résultat du filtre 2) ont une espèce extérieure à un scope donné ce qui permet d'identifier un transfert potentiel. L'égalité du NUMBER_BEFORE avec NUMBER_IN signifie que le groupe d'espèces est homogène avant l'espèce extérieure. Pour l'étude des Ricketsiales avec le scope 1: 28211 et le scope 2: 766, un groupe homogène n'a que des résultats de l'algorithme « Blast » dans la famille des Ricketsiales .

24

Ce filtrage permet de déterminer les cas simples de transfert qui sont ajoutés au fichier transfert.

L'autre fichier que ce programme utilise, ResultFilter_allHitInScope (fichier résultat du filtre 2), contient uniquement des séquences de Caulobacter, cela signifie que la séquence a été perdu chez les Rickettsiales ou contient uniquement des séquences des Rickettsiales on peut donc penser à une perte chez les Caulobacters. Toutes ces sequences seront ajoutées au fichier perte.

3.2.2 Séquences orphelines

J'ai développé deux outils pour l'étude des séquences orphelines OrphanOrthoMCL et OrphanAnalyseur. OrphanOrthoMCL permet de récupérer les séquences orphelines, option non prévue par le programme OrthoMCL. En comparant les séquences présentent dans le fichier d'entrée et non groupée par OrthoMCL on peut facilement identifier les gènes non orthologues spécifiques d'une espèce.OrphanAnalyseur permet de détecter les vrais orphelins à partir du filtre 2 en utilisant son formatage particulier:

NUMBER_ALL_1 vrais orphelins, NUMBER_ALL_0 erreurs du blast, NUMBER_ALL > 1 artefacts.

3.3 Résultats

4240 gènes non orthologues (environ 11% des séquences de départ) ont été identifié, le plus souvent des séquences de petite taille. Pour éviter de travailler sur des « faux » gènes, erreurs d'annotation, nous avons enlevé toutes les séquences de moins de 50 acides aminés. Pour consolider nos résultats, il serait éventuellement préférable d'augmenter cette taille à 100 ce qui donnerait une forte probabilité d'avoir que des vrais gènes.À partir de ces gènes non orthologues nous avons trouvé 569 transferts et 231 pertes chez les Rickettsiales. Et nous avons pu identifier 1627 vrais orphelins, spécifiques d'une espèce.

En testant les séquences orphelines nous avons trouvé beaucoup d'artefact, la principale raison est le fait d'avoir choisi « que » 31 génomes. OrthoMCL identifie uniquement les orthologues dans ces 31 espèces.De plus chez les bactéries il existe différentes souches non identifiées par orthoMCL, puisque elles ne sont pas présentes dans nos 31 espèces.

Le problème d' OrthoMCl est qu'il n' identifie pas les paralogues lointains (homologue issu d'un événement de duplication) car il sortent avec une mauvaise « evalue » d'un Blast.

Sur les 1991 groupes présentant un seul gain, nous avons trouvé 482 transferts et 460 pertes chez les Rickettsiales. Et nous avons identifié 1327 gènes apparus de novo.Pour les gènes apparus de novo; il y a aussi de nombreux d'artefact du à la sélection de 31 génomes (et donc seulement 31 espèces).

Ces filtres et les différents outils correspondent à environ 3000 lignes de codes Java.

25

Figure 18: Visualisation d'un rapport d'agent Dagobah transfert horizontal.

Figure 19: Arbre « événement transfert horizontal »

Les trois valeurs à côté de chaque noeud correspondent aux bootstraps (valeur indiquant la robustesse d'une branche) de l'arbre trouvé par Maximum Parsimony (Fitch 1971), celui trouvé par Neighbor joining (Saitou and Nei, 1987) et celui trouvé par Maximum Likelihood (Felsenstein, 1981). Figenix utilise ces trois algorithmes mathématiques pour produire des arbres phylogénétiques. Puis il les regroupe en un arbre consensus. L'arbre de cette figure est donc un arbre consensus qui indique où est positionné le transfert horizontal (carré jaune avec l'étiquette d'information). Le cadre orange identifie le sous arbre des Rickettsia avec la séquence utilisée pour lancer la phylogénie (séquence requête).

26

4 Étude d'événement génétique, agent Dagobah transfert horizontal »

À partir des séquences sélectionnées comme ayant un transfert horizontal par les filtres, j'ai choisi une séquence pour l'étudier avec l'agent transfert horizontal. Cette séquence est codée par le gène 157803664, gène d'une Rickettsia canadensis str. McKiel.

Le rapport de l'agent de Dagobah (figure 18) indique un transfert d'une Ixode (une espèce de tiques) aux Rickettsia notamment à Rickettsia endosymbiont of Ixodes scapularis. Une endosymbiote, endosymbiont en anglais, est un organisme qui vit à l'intérieur d'une autre cellule ou d'un autre organisme, l'association ainsi formée est une endosymbiose. Cette endosymbiose peut expliquer le transfert.

27

Figure 20: Mes améliorations au système Dagobah.

28

Conclusion et discussion

Les améliorations apportées à Dagobah durant mon stage ont permis de le rendre plus généraliste. J'ai intégré grâce à l'interface universelle la base de données NR du NCBI. Il possède desormais un environnement de travail plus vaste ce qui élargie les possibilités d'études.

L'intégration d'un système de filtres à Dagobah est une autre amélioration. Ces filtres permettent à Dagobah d'aller plus loin dans l'expertise et d'être plus efficace.

Dagobah possède maintenant un agent capable de faire une pré-étude d'événements à partir du regroupement d'orthologues d'orthoMCL. Ce nouvel agent détecte les pertes et les gains à partir des groupes orthoMCL. Cette pré-étude permet d'orienter les séquences vers l'agent spécifique de l'événement détecté. L'étude de l'agent spécifique conduit à un positionnement de l'événement dans la phylogénie de la séquence pré-étudiée.

Lors de l'étude des 31 génomes d'Alphaprotéobactéries complets sélectionnés (38 895 séquences de protéines au total clusterisé dans 3 537 groupes), il a été mis en évidence plusieurs cas d'orientant les études:

- Le premier cas est la détection d'une unique perte dans un groupe orthoMCL (653 groupes), une séquence de ce groupe va être étudiée par l'agent de perte de gènes uniquement.

- Le deuxième cas la détection d'un seul gain (1991 groupes). Ce cas amène à développer un nouveau « pipeline » Figenix (« BlastFilter ») pour différencier les deux causes possibles de ce gain unique: apparition d'un nouveau gène ou transfert horizontal. La détection d'un groupe extérieur à la famille étudiée dans les résultats obtenus grâce à l'outil « Blast » permet d'identifier un transfert et d'orienter ces séquences vers l'agent de transfert horizontal (filtre 1). Les séquences sans groupes extérieurs dans leurs résultats obtenus avec l'algorithme « Blast » sont donc des séquences spécifiques à l'espèce (filtre 2). L'étude de l'agent perte de gène et l'agent de transfert ne sont pas utiles.

Pour les autres cas (893 séquences à étudier) beaucoup trop de scénarios sont possibles et il est nécessaire de lancer les études avec chaque agent.

Le « pipeline » Figenix « BlastFilter » permet également d'étudier les séquences non regroupées par orthoMCL (4240 séquences).Ces séquences peuvent avoir des homologues dans des espèces qui ne sont pas présentes dans les 31 espèces sélectionnées. Il faut donc aussi étudier le transfert pour ces séquences (filtre 1).Sinon ces séquences peuvent être orphelines, elles n'ont pas de séquences similaires, autre qu'elle même, dans les résultats récupérés à partir de l'algorithme « Blast ». Les détecter permet d'éviter la production d'une phylogénie inutile.

29

Cette stratégie est applicable à l'ensemble des êtres vivants. Elle est très intéressante pour l'étude des génomes d'organismes pour lequel les transferts horizontaux ont été mis en évidence. Il y a évidemment les bactéries mais aussi les Nématodes ou les Rotifères par exemple (Gladyshev EA et al. 2008 Massive horizontal gene transfer in bdelloid rotifers, Hotopp JC et al. 2007 Widespread lateral gene transfer from intracellular bacteria to multicellular eukaryotes, Rumpho ME 2009 Horizontal gene transfer of the algal nuclear gene psbO to the photosynthetic sea slug Elysia chlorotica)

Le système expert de Dagobah repose sur les connaissances actuelles qu'il a été possible de décrire en règles. L'avancement des études permet un avancement sur le chemin de la connaissance. Intégrer cette connaissance à Dagobah permet d'affiner ses résultats et par conséquent de faire de nouvelles découvertes et ainsi de suite.Par exemple, l'étude des transferts des bactéries, grâce à ces outils, a montré qu'il existe des transferts multiples c'est à dire qu'une séquence peut être transféré plusieurs fois à différents organismes. L'intégration de cette information permettra l'amélioration de Dagobah.C'est un apprentissage perpétuel.

30

31

Bibliographie

Altschul, S.F., Gish, W., Miller, W., Myers, E.W. & Lipman, D.J. Basic local alignment search tool. J Mol Biol. 1990 Oct 5;215(3):403-10.

Clemente JC, Ikeo K, Valiente G, Gojobori T. Optimized ancestral state reconstruction using Sankoff parsimony. BMC Bioinformatics. 2009 Feb 7;10:51.

Fitch WM. Toward defining the course of evolution: Minimum change for a specific tree topology. Syst Zool 1971;20:406–416

Gladyshev EA, Meselson M, Arkhipova IR. Massive horizontal gene transfer in bdelloid rotifers. Science. 2008 May 30;320(5880):1210-3.

Gouret P . Automatisation de Processus d'Annotation Génomique Contrôlée par Système Expert.. Thèse 2009 disponible à partir du site du laboratoire: http://sites.univ-provence.fr/evol/.

Gouret P, Thompson JD, Pontarotti P. PhyloPattern: regular expressions to identify complex patterns in phylogenetic trees. BMC Bioinformatics. 2009 Sep 19;10:298.

Hoare. Quicksort. The Computer Journal 1962

Hotopp JC, Clark ME, Oliveira DC, Foster JM, Fischer P, Torres MC, Giebel JD, Kumar N, Ishmael N, Wang S, Ingram J, Nene RV, Shepard J, Tomkins J, Richards S, Spiro DJ, Ghedin E, Slatko BE, Tettelin H, Werren JH. Widespread lateral gene transfer from intracellular bacteria to multicellular eukaryotes. Science. 2007 Sep 21;317(5845):1753-6. Epub 2007 Aug 30.

Moran NA, Jarvik T. Optimized ancestral state reconstruction using Sankoff parsimony. BMC Bioinformatics. 2009 Feb 7;10:51.

Paganini J (2009), « Analyses de données et implémentations d’améliorations dans deux agents de Dagobah ». Rapport de stage disponible à partir du site du laboratoire: http://sites.univ-provence.fr/evol/.

Remm M, Storm CE, Sonnhammer EL. Automatic Clustering of Orthologs and in-paralogs from Pairwise Species comparaisons. J Mol Biol. 2001 Dec 14;314(5):1041-52.

Rumpho ME, Worful JM, Lee J, Kannan K, Tyler MS, Bhattacharya D, Moustafa A, Manhart JR. Horizontal gene transfer of the algal nuclear gene psbO to the photosynthetic sea slug Elysia chlorotica. Proc Natl Acad Sci U S A. 2008 Nov 18;105(46):17867-71. Epub 2008 Nov 11.

Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol 1987;4:406–425

Stijn van Dongen. Graph Clustering by Flow Simulation. 2000 PhD thesis, University of Utrecht.

Strimmer K, von Haeseler A. Quartet puzzling: a quartet maximum likelihood method for reconstructing tree topologies. Mol Biol Evol 1996;13:964–969.

32

Liste des abréviations

BDI: Belief Desire Intention.

BLAST: Basic Local Alignment Search Tool.

BNF: Backus-Naur Form.

NCBI: National Center for Biotechnology Information.

NR: Non Redundant Protein Sequences

ORTHOMCL: Orthologous Markov Cluster.

PROLOG: PROgrammation LOGique.

TAXID: Taxon Identifiant.

XML: Extensible Markup Language.

33

34

Annexe

35

Liste des méthodes de l'interface universelle de Dagobah

public interface EBMExternalDatabasesUniversalInterface

/** * get a DNA segment in on a given region for a given species * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param regionType: 'chromosome' or 'scaffold' * @param regionIdentifier: identifier of region on external database * @param strand: -1 for negative strand, +1 for positive strand * @param start: start position of segment on the region * @param end: end position of segment on the region * @param repeatMasked: determine if repeat segments must be masked on

final result * @param tobeMaskedRepeatsTypes: if repeatMasked is true, gives all

repeat types to be masked (specific to external database) * @return DNA extracted data segment * @throws EBMExternalDatabasesAccessException */public String ebmGetDNASegmentFromRegion(

String speciesName,String regionType,String regionIdentifier,int strand,int start,int end,boolean repeatMasked,List<String> tobeMaskedRepeatsTypes)

throws EBMExternalDatabasesAccessException;

/** * get exons definitions for a protein * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param proteinRef: reference of protein on external database * @return XML (FIML) for gene prediction => exons definitions * @throws EBMExternalDatabasesAccessException */public String ebmGetExonsPredictionsForProteinAsFIML(

String speciesName,String proteinRef)


36

/** * get full DNA sequence associated to a given protein (result of gene

coding) * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param proteinRef: reference of protein in external database * @param repeatMasked: determine if repeat segments must be masked on

final result * @param tobeMaskedRepeatsTypes: if repeatMasked is true, gives all

repeat types to be masked (specific to external database) * @return DNA sequence * @throws EBMExternalDatabasesAccessException */public String ebmGetDNAForProtein(

String speciesName,String proteinRef,boolean repeatMasked,List<String> tobeMaskedRepeatsTypes)


/** * get closest gene to a gene on both sides * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param geneRef: reference of gene in external database * @param maxNumberOfGenesOneSide: max number of genes to search on one

side * @return list of genes references * @throws EBMExternalDatabasesAccessException */public List<String> ebmGetGeneClosestGenesBothSides(

String speciesName,String geneRef,int maxNumberOfGenesOneSide)throws EBMExternalDatabasesAccessException;

/** * get closest gene tip in region at position * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param regionType: 'chromosome' or 'scaffold' * @param regionIdentifier: identifier of region on external database * @param position: position on region * @param toTheEnd: true => to the end of the region, false => to the

start * @return position of closest gene tip on region if any (maximum range

should be defined) * @throws EBMExternalDatabasesAccessException */public int ebmGetClosestGeneTipAtRegionPosition(

String speciesName,String regionType,String regionIdentifier,int position,boolean toTheEnd)


37

/** * get gene reference in external database from a protein reference in

external database * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param proteinRef: reference of protein in external database * @return gene reference * @throws EBMExternalDatabasesAccessException */public String ebmGetGeneReferenceFromProteinReference(



/** * get gene reference in external database from another external reference

in another external database * external database must know these reference * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param sourceName: name of other database in which externalRef exists * @param externalRef: reference of an entity in another external database * @return gene reference * @throws EBMExternalDatabasesAccessException */public String ebmGetGeneReferenceFromOtherExternalReference(

String speciesName,String sourceName,String externalRef)


/** * get protein references in external database from gene reference in

external database * external database must know these reference * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param geneRef: reference of gene in external database * @return protein references * @throws EBMExternalDatabasesAccessException */public List<String> ebmGetProteinReferencesFromGeneReference(

String speciesName,String geneRef)


/** * get species taxid from a reference in external database * @param ref: entity reference in external database * @return taxid as a string * @throws EBMExternalDatabasesAccessException */public String ebmGetSpeciesTaxidFromReference(

String ref)throws EBMExternalDatabasesAccessException;

38

/* get reference in another external database from a gene reference in the external database

* external database must know these other external reference * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param sourceName: name of other database in which an other reference

exists for the gene * @param geneRef: reference of a gene in the external database * @return other database external reference * @throws EBMExternalDatabasesAccessException */public List<String> ebmGetOtherExternalReferencesFromGeneReference(

String speciesName,String sourceName,String geneRef)


/** * test if a reference is the reference of a gene in the external database * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param ref: a reference * @return fact that the reference is the reference of a gene in the

external database * @throws EBMExternalDatabasesAccessException */public boolean ebmReferenceIsGeneReference(

String speciesName,String ref)


/** * get first ortholog found for a gene in external database, searched on a

target species * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param geneRef: reference of a gene in the external database * @param targetSpeciesName: uppercased species name (blank or underscore

must be replaced by '~' character) * @return ortholog genes' references in external database */public List<String> ebmGetFirstComingOrthologGeneInTargetSpeciesForGene(

String speciesName,String geneRef,String targetSpeciesName)


/** * get protein sequence in external database from a protein reference in

external database * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param proteinRef: reference of protein in external database * @return AA sequence * @throws EBMExternalDatabasesAccessException */public String ebmGetFullAASequenceForProtein(



39

/** * get biggest protein in a set of isoforms * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param proteinsRefs: list of proteins references in external database * @return biggest protein * @throws EBMExternalDatabasesAccessException */public String ebmGetBiggestProtein(

String speciesName,List<String> proteinsRefs)


/** * get gene genomic location * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param geneRef: reference of a gene in the external database * @return Location class instance * @throws EBMExternalDatabasesAccessException */public EBMLocation ebmGetGeneLocation(

String speciesName,String geneRef)


/** * count number of genes between two genomic locations * @param location1: first location * @param location2: second location * @return number of genes * @throws EBMExternalDatabasesAccessException */public int ebmCountGenesBetweenTwoLocation(

EBMLocation location1,EBMLocation location2)


/** * get region length * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @param regionType: 'chromosome' or 'scaffold' * @param regionIdentifier: identifier of region on external database * @return length of region * @throws EBMExternalDatabasesAccessException */public int ebmGetRegionLength(

String speciesName,String regionType,String regionIdentifier)


40

/** * get genes' references for given region * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @return genes' list * @param location: search in location * @throws EBMExternalDatabasesAccessException */public List<String> ebmGetGenesInRegion(

String speciesName,EBMLocation location)


/** * get database information from given species * @param speciesName: uppercased species name (blank or underscore must

be replaced by '~' character) * @return information'String * @throws EBMExternalDatabasesAccessException */public String ebmGetDataBaseInformation(

String speciesName)throws EBMExternalDatabasesAccessException;

}

41

42

Résumé

Le Laboratoire d' Evolution Biologique & Modélisation de l' Université de Provence Site St Charles à développé des outils permettant, de façon autonome, d'identifier toutes sortes d'événements génétiques (transferts horizontaux, pertes d'un gène, recombinaisons …) chez les vertébrés.

Le but de mon projet permettre l'utilisation de ces outils pour les génomes bactériens. De plus j'ai intégré à ces outils des filtres pour éviter de systématiquement faire des phylogénies et orienter les études en mettant au point une pré-étude d'événements.

Arbre de la vie des 31 espèces sélectionnées pour commencer l'étude et mettre au point la stratégie.

43

Documents

Adaptation du système de recherche d'événements …sites.univ-provence.fr/evol/images/stories/rapports/Rapport_stage... · Prolog est une abréviation de « PROgrammation LOGique