Projet de rapport de conférence

Intervalles communs de séquence pour l'inférence des homologues positionnels

                          I.      Introduction                                                                                                            

               1) Version Exemplaire (Sankoff)                                                                                        

      2) Couplage générale                                                                                                         

 III.   Aperçu de MSOAR                                                                                                      

              1) Software CIGAL : (Common Intervals Global Aligner)                                                

                V.      Filtrage                                                                                                                          

              1) Génomes bactériens :                                                                                           

     2) Le génome humain et celui de la sourie                                                                    

VII.      Test du programme CIGAL                                                                                       

               VIII.      Critique                                                                                                                          

                    IX.      Conclusion                                                                                                                                                            

                       X.      Références                                                                                                                   

             I.      Introduction :

Pour comparer deux génomes, il faut comparer tout d’abord leurs séquences génomiques pour identifier les gènes homologues. Mais la relation un à un n’est pas toujours évidente à cause de plusieurs phénomènes, les  réarrangements, duplication, transfère latéral entre autres.

Pour cela, plusieurs approches ont été décrites pour distinguer les paires de gènes homologues. En effet, on distingue deux catégories fondamentales de gènes homologues : les orthologues et les paralogues.

          II.  Notion d’orthologie-paralogie :

•Deux gènes sont homologues s'ils ont divergé à partir d'une séquence ancêtre commune.

•Deux gènes sont orthologues si leur divergence est due à la spéciation (le gène ancêtre commun se trouvait dans l'organisme ancêtre).

•Deux gènes sont paralogues si leur divergence est due à la duplication du gène ancêtre. [1]

Il existe deux approches pour les homologues de position :

 1) Version Exemplaire (Sankoff) :

Afin d’assigner les hortologues on doit normalement minimiser la distance d’inversion entre deux séquence ou maximiser les intervalles commun en considérant les intervalles les plus longs et minimiser les breakpoints, hors, ces deux approches sont NP-complet ! [2]

La comparaison se fait  en gardant qu’un seul gène de chaque famille dans G1 et G2 faut lever les ambiguïtés pour chaque famille de gènes dupliqués.

 G1 = +1 + 2 + 3 − 2 + 5 + 4 + 4

G2 = −1 + 2 + 1 + 5 − 3 + 2 + 4

Un exemple:

G’1 = +1 + 2 + 3 + 5 + 4

G’2 = +1 + 5 − 3 + 2 + 4

La correspondance 1-1 est implicite

 2) Couplage générale :

Dans ce cas le couplage se fait en correspondant le nombre maximum de couple gènes entre G1 et G2

 G1 = +1 + 2 + 3 − 2 + 5 + 4 + 4

G2 = −1 + 2 + 1 + 5 − 3 + 2 + 4

Un matching maximal:

G’1 = +1 + 2 + 3 − 2 + 5 + 4

G’2 = +2 + 1 + 5 − 3 + 2 + 4

 Dans les deux méthodes plusieurs critères sont considérés.

  Critères:

 Pour une distance ou une mesure de similarité D ou la distance d’inversion donnée il faudrait

trouve le matching ou l’exemplarisation qui optimise D

Principe de parcimonie peut être appliqué.

Tous ces problèmes sont d’ordre NP-difficile.

 Soit G un génome.

occ(G, x): nombre d’occurrences du gènes x dans G

occ(G): maximum des occurrences (G, x) pris sur toutes les

familles x de gênes

f (G): nombre de famille de gènes différentes dans G

       III.      Aperçu de MSOAR

 *Recherche d’homologie

*Comparaison des gênes deux a deux avec Blastn

*Choisir les Blastp hits avec les scores de similarité au dessus du cut off :

·        2 gênes sont homologues si le score est  moins de 50.

·         la longueur du meilleur alignement local trouver par blast couvre au moins 50% de la longueur du gêne,

Prendre les 5 meilleurs hits bidirectionnel.

L’Assignation d’orthologue se fait en calculant la distance d’inversion.

Cette méthode se base sur une application des règles optimales.

La partition commune minimale est aussi appliquée.

La décomposition du graphe maximale et la détection des in-paralogue se fait en identifiant le ‘noise gene pairs’.

 Puisque les copies des  gènes hortologues partagent généralement les même positions génomiques dans des contextes définis comme les opérons des bactéries par exemple, une nouvelle  approche a été décrite lors de cette conférence : il s’agit de la notion des intervalles communs basée sur le contexte génomique.   

            L’article décrit une nouvelle approche se basant sur la notion d’intervalle commun

Dans la comparaison de deux génomes, la première tache consiste en la comparaison de leurs nucléotides ainsi que de leurs acides amines dans le but de déterminer les gènes homologues.

Il existe des gènes dont la similarité des séquences et si forte qu’on suppose l’existence d’un gène ancestral commun.

La distinction de pairs de gènes orthologue de familles de gènes se trouvant dans diverses positions pour deux génomes est plutôt difficile.

Plusieurs méthodes ont été proposées pour la distinction de pairs de gènes, appelés homologues positionnels. Ces derniers pouvant être éventuellement des gènes orthologues. [3]

On modélise généralement le génome G d'une espèce par une séquence d'entiers possiblement signés: chaque entier représente un gène et le sens de lecture du gène sur le chromosome n'est pas ici pertinent (les entiers sont non signés) aussi que l’ordre et le nombre de copies de chaque gène. Si un entier i apparaît plusieurs fois dans la séquence, on dit alors que le gène i est dupliqué dans le génome. On cherche bien sûr à comparer des espèces deux à deux en comparant les génomes. De nombreuses méthodes existent, et on s'intéressera en particulier ici au calcul du nombre d'intervalles communs [3].

Si on schématise nos séquences génomiques par cette présentation :

Les gènes sont symbolisés par des entiers :

Voici un exemple d’un intervalles communs entre ces quatre séquences :

Le calcul du nombre d'intervalles communs peut s'effectuer très facilement lorsque les deux génomes ne présentent pas de duplications. Cependant, on sait maintenant qu'il existe des duplications - en nombre non négligeable - de gènes dans les génomes (estimées par exemple à 15% chez l'Homme). Malheureusement, en présence de duplications, le calcul du nombre de points de cassure devient beaucoup plus complexe. En fait, déterminer une correspondance entre les entiers des deux séquences de manière à  maximiser le nombre d'intervalles communs entre les deux séquences signées résultantes est un problème NP-complet.

Plusieurs méthodes ont été proposées pour la distinction de pairs de gènes, appelles homologues de position. Ces derniers pouvant être éventuellement des gènes orthologues.

Il existe deux approches pour les homologues de position :

   1) Le programme CIGAL : (Common Intervals Global Aligner):

 Dans l’article, l’approche de matching est utilisé avec le choix de touts les homologues de position. L’heuristique du MIBC qui est glouton et l’originalité de la méthode réside dans le fait qu’elle calcule pas les pairs de permutation qui sont optimale donnée par un critère choisis, mais s’appuie sur une approche gloutonne couplant de façon récursive des segments de gènes dont dans la structure combinatoire est commune.

Hors, cette procédure est NP-difficile

 Mais en tenant compte du contexte génomique, on peut faire une approximation de ce problème NP-difficile dans un temps quadratique. 

 * Cette méthode est implantée dans un programme appelé CIGAL [3].

    V.      Filtrage :

L’extraction des intervalles communs peut aboutir à des mauvais couplage (par exemple des grandes boitesd’intervalles communs ayant un nombre très réduit en gènes), alors on fait un filtrage des intervalles communs obtenus en imposant le nombre minimal de gène qui doit exister dans un intervalle commun.

     VI.      Résultat :

Ce programme a été testé avec deux masses de données génomiques : 

1)      Huit génomes bactériens.

2)      Le génome humain et celui de la sourie. 

Les résultats sont comparés aux résultats donnés par LCS [5] (Longest Common Substrings) et MSOAR :

          1)Génomes bactériens :

les souches bactériens qui ont été étudiées sont :

 Résultat de l’Assignation sur les génomes de proteobactere:

* LCS est plus précis mais moins consistant car CIGAL détecte beaucoup plus de faux négatifs).

   Résultat de l’Assignation sur les génomes de protéobactere après filtrage:

* Après le filtrage la consistance augmente. On observe aussi que Cigal a un meilleur perfect ratio components.

        2) Le génome humain et celui de la sourie :

 Résultat de l’Assignation des orthologues pour la souris et l’homme :

Il est vrai que MSOAR  est le plus précis dans le couplage des gênes othologues ainsi que dans la détermination de vrai positifs cependant Cigal est un outil aussi performant vu les résultats obtenues (détection de 69% de vrai positifs)

   VII.      Test du programme CIGAL :

On a testé le programme CIGAL avec 3 souches bactériennes de Bacillus :

                  ·        NC_000964.2: Bacillus subtilis génome complet.

·        NC_003997.3: Bacillus anthracis génome complet.

·        NC_006274.1: Bacillus cereus E33L génome complet.

Pour cela, Nous avons développé un script python qui permet de générer, à partir de la base de données NCBI, les gènes des numéros d’accession sont fournis au préalable.

Script utilisé :

#!/usr/bin/python
URL = "http://www.ncbi.nlm.nih.gov/entrez/viewer.fcgi?db=nucleotide&val=%s&send\
to=t"

IDS = ["NC_000964.2", "NC_003997.3", "NC_006274.1"]
PATH = "/tmp/"

from urllib import urlopen
from pprint import pprint
import re

GEN_PAT = re.compile('     gene.*?/gene="(.*?)"', re.DOTALL)

def is_org(line):
    return line.strip().startswith("ORGANISM")

for rsid in IDS:
    lines = urlopen(URL % rsid).readlines()
    print rsid
    org = filter(is_org, lines)[0].strip()
    org = org[org.find(" "):].strip()

    genes = GEN_PAT.findall("\n".join(lines))
    print org, ":", genes

    data = ">%s\n%s\n" % (org, "\n".join(genes))
    open(PATH+org.replace(" ", "_")+".txt", "w").write(data)
# The END!

 Il suffit de le sauvegardé dans un fichier foo.py puis de le lancer:
python foo.py
Des fichier .txt dans /tmp/  vont être engendrés

Pour l’extration des intervalles commun:
on utilise la commande : cigal /tmp/(nom du fichier1).txt /tmp/(nom de fichier2).txt /tmp/foo.cigal
Pour visualiser les intervalles communs :
on utilise la commande  : cigalgui /tmp/foo.cigal

Pour faire une capture d'écran: 

Commande: ksnapshot

Pour extraire le couplage :
on utilise la commande  : cigalf -d /tmp/coupl.txt  /tmp/foo.cigal (Ça met le couplage dans /tmp/coupl.txt).

 Pour visualiser le couplage :
on utilise la commande : cigalgui /tmp/coup1.cigal

    Résultat :

le couplage se fait entre les trois combinaisons suivantes (Bacillus anthracis et Bacillus subtilis, Bacillus anthracis et Bacillus cereus et Bacillus subtilis  et Bacillus cereus) :

L’extraction des intervalles communs et le couplage se fait dans un temps très court de quelques secondes) ce qui confirme à une certaine mesure la rapidité de ce programme.

Les intervalles communs montres un nombre important de régions conservés entre la famille des Bacillus (on a retrouvé plusieurs opérons communes pour ces souches qui ont été décrites sans la littérature comme étant des opérons rp et cta qu’on  illustre plus bas)

Voici quelques illustrations des résultats retrouvés :

               ·        Intervalles communs entre Bacillus anthracis et Bacillus subtilis :

(schéma démontrant des inversion dans cette portion).

·        Intervalles communs entre Bacillus anthracis et Bacillus cereus :

·        Intervalles communs entre Bacillus subtilis  et Bacillus cereus :

(On remarque des inversion dans cette portion).

·        Couplage de l’opéron rp (qui code pour les sous-unités de ribosomes) :

·        Couplage de l’opéron cta (qui code pour la cytochrome oxydase) entre Bacillus anthracis et Bacillus subtilis :

On a une inversion dans ce cas :

  VIII.      Critique :

Positif :

·        LCS (Longest Common Substring)  ne permet pas de détecter les inversions tant dis que CIGAL le permet

·        CIGAL est rapide.

Négatif :

·       CIGAL est incapable de détecter l’insertion d’un gène alors que la méthode de « max gap clusters » [6] le permet  (la détection des insertions est de complexité exponentielle). 

·        Certaines relations d’évolution entre gènes sont indétectables par les méthodes usuelles de comparaison de séquences. En effet, toutes les parties d’un gène n’ont pas la même histoire [7] c’est à dire qu’un gène peut coder pour une protéine constituée de domaines provenant de plusieurs autres gènes. Dans ce cas, c’est chacun des domaines qui partage un lien d’homologie avec un domaine similaire codé par un autre gène. Considérons l’exemple du gène de biosynthèse du tryptophane d’E. coli trpC(F) (Figure 1). Ce gène code pour une enzyme bi-fonctionnelle qui inclut la fonction indole-3-glycerol phosphate synthase assurée par le domaine IGPS et la fonction anthranilate isomérase assurée par le domaine PRAI.

Ce gène est issu de la fusion des gènes trpC et trpF tels que présents par exemple chez         B. subtilis où le gène trpC code pour une indole-3-glycerol phosphate synthase constituée du domaine IGPS et le gène trpF pour une anthranilate isomérase constituée du domaine PRAI. Dans ce cas, si l’on s’interroge sur la relation d’homologie qui existe entre ces trois gènes, la définition atteint ses limites puisque ce sont les domaines IGPS et PRAI qui sont homologues deux à deux. On peut citer également les cas de permutations circulaires pour lesquels les outils classiques de détection d’homologie (alignement de séquences) sont inadapté [8].

Figure : Domaines des protéines codées par les gènes trpC, trpF et trpC(F)

Fitch, dans une revue traitant des problèmes liés à la notion d’homologie, mentionne ce point qu’il nomme ‘The recombination problem’. Il en arrive à la conclusion que, lorsqu’on veut tenir compte des réarrangements de domaines, le gène n’est pas l’unité adéquate pour parler d’orthologie ou de paralogie. Dans ce cas, le domaine s’avère être une unité plus pertinente. Quant à Koonin, il généralise cette conclusion en suggérant de revoir l’ensemble des processus évolutifs en terme de domaines plutôt qu’en terme de protéines   (gènes) (Koonin, 2000) [10].

        IX.      Conclusion : 

Le programme CIGAL est un outil robuste pour la détection des intervalles communs (tenir compte du contexte génomique) pour le couplage des gènes orthologues en termes de rapidité (comparativement aux méthodes classiques de détections des intervalles communs) et d’efficacité.

Le test du programme nous a permis d’extraire les intervalles communs ainsi que le couplage entre les trois génomes de Bacilllus. Les résultats obtenus (recherche des opérons) concorde parfaitement avec les données publiées dans la littérature.

CIGAL permet aussi de détecter les inversions, mais reste cependant incapable de détecter les insertions (beaucoup reste a faire dans ce domaine).

           X.      Références :

1-     Koonin, E. V.  (2005) Orthologs, paralogs, and evolutionary genomics.

2-     D. Sankoff et al. (1999)  Gene order breakpoint evidence in animal mitochondrial phylogeny.

3-     Z.Fu, et al. (2006) A parsimony Approach to Genome-Wide Ortholog Assignement.

4-     J. Etienne et al. (2006) Intervalles communs de séquence pour l'inférence des homologues positionnels.

5-     Guillaume B, et al. (2006) Inferring positional homologs with common intervals of sequences.

6-     G.Blin et al. (2005) Longest Common Substrings.

7-     Karine St-Onge et al. (2005)  Fast identification of gene clusters in prokaryotic genomes.

8-     Fitch WM. 2000. Homology a personal view on some of the problems.

9-     J. Weiner et al. (2005) Rapid motif-based prediction of circular permutations in multi-domain proteins.

10-  Galperin, MY et Koonin, EV. (2000). Who's your neighbor? New computational approaches for functional genomics.