- 1 -

Académie de Montpellier

U n i v e r s i t é M o n t p e l l i e r I I

Sciences et Techniques du Languedoc

Mémoire de Stage de Master

Spécialité : Recherche en Informatique Mention : Informatique, Mathématiques, Statistiques

effectué au laboratoire LIRMM/INFO

sous la direction de STEPHANE GUINDON et OLIVIER GASCUEL

Méthodes phylogénétiques pour la détection d'évènements de recombinaison

par

Eric Audemard

11 juin 2007

- 2 -

Remerciements

Je tiens à remercier Stéphane Guindon et Olivier Gascuel, mes tuteurs de stage pour leur

disponibilité et pour avoir guidé adroitement mes recherches. Je remercie également Roland Ducournau (responsable du M2R) et l’ensemble des

enseignants pour la qualité de leurs enseignements. Merci à Denis Bertrand, Alexis Criscuolo et Vincent Berry, c’est grâce à eux que j’ai

découvert le domaine de la bioinformatique.

Merci à tous mes camarades de stage pour m’avoir aidé pendant la réalisation de ce stage et avec qui j’ai eu de très bons moments.

Merci à mes amis qui ont toujours étaient là quand j’avais besoin d’eux et avec qui j’ai

passé une très bonne année. Ils sont nombreux mais je tiens particulièrement à remercier : Yannick, Caro, Alain, Stella, Cathy et Adèle.

Enfin, je remercie ma famille qui m’a toujours soutenu dans mes choix.

- 3 -

Table des figures et des tableaux : Figure 1 : Exemple d’alignement de séquences génétiques...........................................................................................6 Figure 2 : Exemple d'arbre phylogénétique ...................................................................................................................7 Figure 3 : Schéma de deux molécules d’ADN (en bleu et en rouge) effectuant une recombinaison.............................7 Figure 4 : Exemple de recombinaison d'une espèce D vers une espèce C.....................................................................8 Figure 5 : Arbre recombinant obtenu ............................................................................................................................8 Figure 6 : Méthode de distances : inversions des distances entre deux espèces............................................................9 Figure 7 : Méthodes phylogénétiques : comptent les mutations..................................................................................10 Figure 8 : Méthodes de compatibilités : recherchent les partitions identiques ............................................................10 Figure 9 : Exemple du test du Chi-Square...................................................................................................................11 Figure 10 : Calcul de la parcimonie d'un arbre............................................................................................................14 Figure 11 : Calcul de la parcimonie d'un site recombinant et non recombinant ..........................................................15 Figure 12 : Voisinage d'un arbre .................................................................................................................................16 Figure 13 : Matrice de parcimonies.............................................................................................................................18 Figure 14 : Identification des sites recombinants à l’aide des scores de parcimonies .................................................19 Figure 15 : Arbre phylogénétique respectant l'horloge moléculaire ............................................................................21 Figure 16 : Calculs des longueurs de branches de l’arbre recombinant.......................................................................22 Figure 17 : Diagramme en baton du taux de précision et de rappel des sites non recombinants identifiés.................23 Figure 18 : Diagramme en baton du taux moyen de précision et de rappel des sites non recombinants identifiés .....25

- 4 -

Sommaire : I Introduction ........................................................................................................................................5

II Bioinformatique..................................................................................................................................6

1. Séquences génétiques .....................................................................................................................6 1.1. Définition.................................................................................................................................6

2. Les arbres phylogénétiques ...........................................................................................................6 2.1. Définition.................................................................................................................................6 2.2. Représentation de l’évolution sous forme d’arbre...................................................................7

3. La recombinaison...........................................................................................................................7 3.1. Définition.................................................................................................................................7 3.2. Représentation d’un mouvement recombinant sous la forme d’arbre .....................................8

III Méthodes existantes .......................................................................................................................9

1. Classification des méthodes...........................................................................................................9 1.1. Méthodes de distances.............................................................................................................9 1.2. Méthodes phylogénétiques ....................................................................................................10 1.3. Méthodes de compatibilités...................................................................................................10

2. Principe des méthodes les plus utilisées......................................................................................11 2.1. Maximun Chi-Square ............................................................................................................11 2.2. Rdp (Recombinaison Detection Program).............................................................................11

3. Comparaison des performances et de leurs méthodes de calcul ..............................................12 3.1. Détection des recombinaisons ...............................................................................................12 3.2. Les faux positifs ....................................................................................................................13 3.3. Discussion .............................................................................................................................13

IV Méthodes .......................................................................................................................................14

1. Le critère de parcimonie..............................................................................................................14 1.1. Calcul de la parcimonie.........................................................................................................14 1.2. Calcul de la parcimonie sur l’arbre des espèces et sur l’arbre recombinant..........................15 1.3. Recherche de l’arbre phylogénétique ....................................................................................16

2. Problème : Trouver les sites recombinants................................................................................17 2.1. Partitionner les séquences et estimer de leurs arbres phylogénétiques..................................17 2.2. Identification des sites recombinants.....................................................................................18

3. Quelques précisions......................................................................................................................19 3.1. La taille des fenêtres..............................................................................................................20 3.2. Complexité ............................................................................................................................20

V Simulation de jeux de données ........................................................................................................21

1. Arbre des espèces .........................................................................................................................21

2. Arbre recombinant.......................................................................................................................22

VI Résultats........................................................................................................................................23

VII Discussion......................................................................................................................................26 1.1. Conclusion.............................................................................................................................26 1.2. Perspectives ...........................................................................................................................27

VIII Références bibliographiques .......................................................................................................28

- 5 -

I Introduction

La bioinformatique est un champ de recherche multi-disciplinaire où travaillent de concerts biologistes, informaticiens, mathématiciens et physiciens, dans le but de résoudre des problèmes scientifiques posés par la biologie. L’un de ces problèmes est de comprendre et de modéliser l'évolution des séquences génétiques. En effet, au cours du temps, les séquences génétiques se modifient à travers divers processus et l’historique de ces modifications est détaillé par la phylogénie. On représente couramment une phylogénie par un arbre phylogénétique. Cet arbre décrit les degrés de parentés entre les espèces et leurs ancêtres communs. Parmi les différents processus évolutifs, nous allons étudier la recombinaison et ses conséquences sur la phylogénie.

La recombinaison est un processus biologique fondamental qui intervient, par exemple, dans l’évolution des virus ou des bactéries en diffusant du matériel génétique à travers une population (AWADALLA 2003). Ce transfert de matériel génétique, entre deux espèces au sein d’une séquence, implique que l’évolution des séquences ne peut plus être représentée par un seul arbre phylogénétique. En effet, les mouvements recombinants violent les liens de parenté entre espèces: une espèce récupère une partie du génome d’une autre, n’ayant parfois qu’un lien de parenté très éloigné de la première et elles deviennent « soeurs ».

Ce qui implique qu’une partie du génome continue d’évoluer selon le premier arbre et que l’autre partie du génome (qui concerne le mouvement recombinant) évolue selon un nouvel arbre où les deux espèces sont « soeurs ». La recherche des parties recombinantes dans un génome est essentielle si l’on veut définir des modèles réalistes de l’évolution des séquences génétiques.

Le présent rapport a donc pour objectif de présenter une nouvelle méthode pour la détection des mouvements recombinants. En premier lieu, nous allons résumer ce qui a déjà été réalisé dans le domaine et étudier les différentes méthodes existantes. Ainsi, nous mettrons en valeur les caractéristiques qui nous semblent importantes à l’obtention d’une bonne méthode de détection. Dans un second temps, nous présenterons la nouvelle méthode que nous avons développée. Enfin, nous justifierons notre approche à l’aide de résultats et de statistiques et nous comparerons ses performances avec des approches plus couramment utilisées.

- 6 -

II Bioinformatique

1. Séquences génétiques

1.1. Définition

D'un point de vue biologique, on peut associer chaque espèce vivante à son génome, c'est-à-dire à une séquence d’ADN. D'un point de vue informatique, on peut considérer une séquence génétique comme un mot non infini formé par un alphabet de quatre caractères: {A, C, G, T}. Ces caractères composant la séquence génétique sont appelés des sites. Un des thèmes de la bioinformatique est de comprendre et modéliser l'évolution des séquences génétiques au cours du temps, à partir de leur comparaison. Généralement, l’évolution moléculaire est modélisée par trois types de mutations ponctuelles : - substitution : un caractère se transforme en un autre dans la séquence génétique ; - délétion : un caractère disparaît de la séquence au cours de l'évolution ; - insertion : un caractère apparaît entre deux autres.

Considérons quatre mammifères : Homme, Gorille, Rat et Souris. Prenons le gène G suivant avec les alignements de séquences correspondants :

G(Homme) = ATGCATGC G(Gorille) = ATGGATGC G(Rat) = CGATCGAT G(Souris) = GGATCGAT

Figure 1 : Exemple d’alignement de séquences génétiques

On constate qu'il n'y a qu'une unique différence entre G(Homme) et G(Gorille) comme il n'y a aussi qu'une seule différence entre G(Rat) et G(Souris). Ces différences observées entre séquences contemporaines traduisent des mutations survenues dans le passé.

2. Les arbres phylogénétiques

2.1. Définition

Un arbre phylogénétique présente les relations de parenté entre organismes vivants. L'arbre phylogénétique montre la succession des émergences des groupes d'organismes vivants au cours du temps. La reconstruction des phylogénies repose sur l'analyse de nombreux caractères chez les espèces qu'il présente. Les longueurs des branches traduisent l’accumulation des mutations au sein des caractères qui ont servi à construire l'arbre. En général, ces branches sont agencées de manière à supposer le minimum de mutations dans l’arbre.

- 7 -

2.2. Représentation de l’évolution sous forme d’arbre

Reprenons l'exemple des séquences génétiques vues ci-dessus (cf. Figure 1). En s'appuyant sur l'intuition que deux espèces sont d'autant plus proches dans l'arbre qu'elles présentent peu de différences entre leur gène respectif, l'arbre représentant l'évolution entre ces quatre espèces serait donc:

Figure 2 : Exemple d'arbre phylogénétique

3. La recombinaison

3.1. Définition

La recombinaison est un mécanisme très important dans l’échange d’information génétique. Elle procède par croisement entre séquences d’ADN. Cet échange s’effectue grâce à une structure d’ADN en croix, La jonction de Holliday.

Figure 3 : Schéma de deux molécules d’ADN (en bleu et en rouge) effectuant une

recombinaison via une Jonction de Holliday

Comme toute mutation, la recombinaison peut donner des résultats viables ou non. Et

bien plus que toutes les simples mutations ponctuelles, elle aboutit rarement puisqu'elle équivaut à des centaines de mutations.

Dans certains cas, le résultat de la recombinaison peut permettre à un virus de passer d'une espèce à une autre, l'hôte pouvant être porteur d'un virus inactif pour son espèce et le combiner avec un virus actif. Le résultat pourrait avoir les caractéristiques nécessaires pour devenir actif chez son hôte.

- 8 -

3.2. Représentation d’un mouvement recombinant sous la forme d’arbre

On appelle mouvement recombinant entre deux organismes vivants, un groupe de sites donné par une espèce D à une espèce C. Ainsi C obtient des sites qui n’ont aucun lien de parenté avec l’arbre phylogénétique d’origine.

Figure 4 : Exemple de recombinaison d'une espèce D vers une espèce C

La phylogénie des espèces ne peut plus représenter à elle seule la phylogénie des

séquences. Un deuxième arbre sera nécessaire pour représenter l’évolution au sein de la partie recombinante de la séquence. Cet arbre est appelé l’arbre recombinant. Le premier arbre, représentant la partie non recombinante des séquences, est appelé l’arbre des espèces.

Figure 5 : Arbre recombinant obtenu

- 9 -

III Méthodes existantes

La détection des mouvements recombinants est essentielle à la modélisation de l’évolution des espèces. Cela fait maintenant 20 ans que la communauté scientifique développe des méthodes. Il y a 5 ans, ces méthodes ont été testées et comparées avec des jeux de données réelles ou simulées et avec une proportion plus ou moins grande de sites recombinants (MAYNARD SMITH 1999 ; BROWN et al. 2001 ; POSADA et CRANDALL 2001 ; WIUF et al. 2001 ; POSADA 2002).

1. Classification des méthodes

1.1. Méthodes de distances

Les méthodes de distances recherchent des inversions du modèle de distance, le long des alignements de séquences. Ces méthodes sont particulièrement rapides du fait qu’il n’est pas nécessaire de calculer la phylogénie des séquences. En général, elles utilisent des calculs statistiques le long des alignements de séquences, à l’aide de fenêtres glissantes, afin de déterminer les parties recombinantes. Ces méthodes détectent les recombinaisons à l’aide de variations le long des séquences.

Figure 6 : Méthode de distances : inversions des distances entre deux espèces

- 10 -

1.2. Méthodes phylogénétiques

Les méthodes phylogénétiques étudient les mutations au cours du temps. Elles recherchent les sites possédant une histoire évolutive différente de l’histoire des espèces. Les sites sont regroupés par la suite, quand ils appartiennent à un même arbre phylogénétique. Ces méthodes détectent les recombinaisons à l’aide de variations au cours du temps.

Figure 7 : Méthodes phylogénétiques : comptent les mutations

1.3. Méthodes de compatibilités

Les méthodes de compatibilité sont des méthodes phylogénétiques qui utilisent une analyse site par site. Ces méthodes déclarent deux sites compatibles, quand leurs histoires évolutives sont en accord avec le même arbre. Le calcul de la phylogénie des séquences n’est pas utile pour appliquer cette technique. Ces méthodes détectent les recombinaisons à l’aide de variations le long des séquences.

Figure 8 : Méthodes de compatibilités : recherchent les partitions identiques

- 11 -

2. Principe des méthodes les plus utilisées

2.1. Maximun Chi-Square

L’algorithme du Maximum Chi-Square compare les séquences par deux. Chaque couple de séquence possède k sites. Parmi ces k sites, s montrent une différence entre les deux séquences. Si une coupe est réalisée arbitrairement sur le site i, alors il y a r/i sites différents avant la coupe et (s-r)/(k-i) après la coupe. Nous pouvons ranger ces valeurs dans une matrice carrée de taille 2, et tester l’indépendance des lignes et des colonnes à l’aide du test du Chi-Square. Si le test révèle que les lignes et les colonnes sont indépendantes alors il y a recombinaison. La coupe qui aura le plus gros score du Chi-Square déterminera la séparation des deux groupes.

Figure 9 : Exemple du test du Chi-Square

En ce qui concerne la complexité, nous avons n séquences cela fait O(n²) couples pour

lesquels il faudra parcourir k sites, soit O(n²k).

2.2. Rdp (Recombinaison Detection Program) L’algorithme Rdp compare les séquences à l’aide de triplets à travers 3 étapes :

- La première consiste à éliminer les sites qui n’apportent pas d’information phylogénétique. Dans un triplet il y a deux séquences, A et B qui sont plus proches (similaires) que la troisième C. Les sites à éliminer sont ceux qui sont identiques ou différents dans les 3 séquences ;

- Ensuite, la séquence est parcourue à l’aide d’une fenêtre glissante site par site. A chaque étape un pourcentage est calculé pour les trois couples possibles du triplet. Une recombinaison est possible quand le pourcentage du couple AC ou BC est supérieur au pourcentage AB ;

- Enfin, une P-valeur est calculée à l’aide d’une distribution binomiale pour chaque groupe de site potentiellement recombinant. Cette P-valeur correspond à la probabilité d’obtenir la valeur de la statistique observée, sachant que l’hypothèse nulle d’absence de recombinaison est vraie.

- 12 -

Après avoir déterminé les groupes de sites recombinants ainsi que leurs P-valeur, il faut identifier la séquence qui est recombinante parmi les trois. Le processus s’exécute en trois étapes :

- Un arbre est créé à l’aide de la méthode de distances neighbour joining (NJ). Sur chaque nœud de cet arbre sont calculés trois vecteurs de parcimonie (calcul de différences de séquences, Voir IV 1.1) ;

- Le plus proche ancêtre commun d’un triplet recombinant est identifié. Un score de parcimonie est calculé entre l’ancêtre et chacune des trois séquences du triplet ;

- Nous pouvons identifier le chemin qui a le score le plus élevé. C'est sur ce chemin que la probabilité d'un mouvement recombinant est la plus forte. 3. Comparaison des performances et de leurs méthodes de calcul

Les études les plus récentes ont été réalisées il y a 5 ans (POSADA et CRANDALL 2001 ;

POSADA 2002), elles comparent 14 méthodes à l’aide de deux critères : - le taux de recombinaison identifié ; - le taux de faux positifs, c'est-à-dire le nombre de fois où le programme identifie une

recombinaison qui n’en est pas une.

3.1. Détection des recombinaisons

Tout d’abord, il est intéressant de noter que toutes les méthodes voient leurs performances augmenter lorsque le nombre de sites recombinants augmente. Ensuite, nous pouvons remarquer que les méthodes de substitutions ont des performances supérieures aux autres.

Maintenant, si l’on regarde les performances de chaque méthode, nous pouvons en nommer 5 ayant des performances supérieures aux autres :

- une méthode de distances : Maximum Chi-Square (MAYNARD SMITH 1992), Phypro (WEILLER 1998);

- une méthode de compatibilités : Reticulate (JAKOBSEN and EASTEAL 1996).

L’absence des méthodes de phylogénétique est flagrante. En effet seul Rdp (MARTIN and RYBICKI 2000) obtient des résultats satisfaisants mais reste un cran en dessous des méthodes précédemment citées. Un cas particulier est à signaler : il est très difficile de détecter les recombinaisons quand le taux de mutation est très faible ou que les recombinaisons ont eu lieu sur des espèces possédants des liens de parenté assez proches. Dans cet exercice, seule la méthode Homoplasy (MAYNARD SMITH and SMITH 1998), une méthode de substitutions, obtient de bons résultats tandis que les autres méthodes ne dépassent pas les 40%. L’étude des performances sur des données réelles donne des résultats similaires.

- 13 -

3.2. Les faux positifs

En général le taux de faux positifs tourne autour de 5% sauf pour la méthode Homoplasy qui est compris entre 30 et 80%.

En ce qui concerne les résultats sur des données réelles, nous remarquons que les méthodes phylogénétiques ont un taux de faux positifs plus faible que les autres méthodes. Rdp et Maximum Chi-Square sont les seuls à obtenir un taux de faux positif de 0%.

3.3. Discussion Les différentes études réalisées, à l’aide de jeu de données simulées, nous montrent que

les méthodes de distances et de compatibilités sont plus efficaces que les méthodes phylogénétiques. Cela est aussi vrai sur des jeux de données réelles. En effet, la recombinaison modifie un groupe de sites mitoyens et les méthodes phylogénétiques étudient les variations temporelles site par site et ne tiennent pas compte de ce phénomène. A l’inverse, les autres méthodes utilisent essentiellement les caractéristiques de ce phénomène en étudiant les variations le long des séquences. Ainsi, les méthodes de substitution sont plus développées. La dernière date de 2006 et d’après les auteurs (BRUEN, PHILIPPE and BRAYANT 2006) elle possède de meilleurs performances que la méthode du Maximum Chi-Square.

Cependant, les méthodes phylogénétiques détectent des recombinaisons anciennes qu’il est impossible de détecter avec les autres méthodes. En effet, ces mouvements recombinants sont masqués par les mutations survenues au cours du temps et ils ne peuvent plus être détectés en étudiant les variations le long des séquences. Ainsi, seules les méthodes phylogénétiques peuvent détecter ces anciens mouvements car elles étudient les variations aux cours du temps.

A la vue de ces résultats, nous avons décidé de développer une nouvelle méthode phylogénétique. En effet, nous pensons qu’il est possible d’obtenir de meilleurs résultats car la recombinaison modifie la phylogénie des espèces (voir II 3.2), ce qui n’est pas exploité par les autres méthodes. Cependant, nous sommes conscients que nous devrons développer une méthode qui identifie les sites recombinants par groupe et non site par site.

- 14 -

IV Méthodes

Il est possible d’évaluer les phylogénies selon différents critères : la vraisemblance et la parcimonie. Nous avons décidé d’utiliser le critère de parcimonie qui permet d’obtenir des résultats avec un temps de calcul réduit.

1. Le critère de parcimonie

Le critère du maximum de parcimonie consiste à utiliser le minimum de changement

évolutif pour expliquer des relations phylogéniques. On cherche le nombre de mutations minimum entre ces différentes séquences. La recherche de ces mutations se fait en comparant les sites un à un.

1.1. Calcul de la parcimonie

Nous disposons au départ d'un alignement de n séquences de longueur k. Ces séquences sont écrites sur un alphabet de quatre lettres {A, T, G, C} qui correspondent aux quatre bases azotées. Nous disposons également d'un arbre phylogénétique non orienté dont les feuilles sont caractérisées par les séquences. Nous allons effectuer les opérations suivantes pour chacun des sites:

• Pour chaque nœud i de l'arbre, on calcule son vecteur de parcimonie VP(i) = (X(i),P(i)) • Si i est un nœud interne :

- X(i) est l'ensemble des nucléotides possibles au nœud i qui minimisent la parcimonie du sous-arbre de racine i,

- P(i) est la parcimonie du sous-arbre de racine i. • Si i est une feuille:

- X(i) est le nucléotide correspondant dans l'alignement, - P(i) = 0.

Figure 10 : Calcul de la parcimonie d'un arbre

- 15 -

Le calcul du vecteur de parcimonie d'un nœud interne i, connaissant les vecteurs de

parcimonie de son fils gauche g et de son fils droit d est réalisé à l'aide de la méthode proposée par FITCH (1971) :

Si X(g)∩X(d) ≠ ∅

Alors X(i)=X(g)∩X(d) et P(i)=P(g)+P(d); Sinon X(i)=X(g)∪X(d) et P(i)=P(g)+P(d)+1;

Le calcul de la parcimonie consiste à parcourir l'arbre enraciné à l'aide d'un parcours en profondeur postfixe. Durant celui-ci, la méthode de Fitch est appliquée sur tous les nœuds.

Cet algorithme parcourt tous les nœuds de l'arbre. Sa complexité est donc en O(n). Le calcul complet de la parcimonie est en O(nk), l'algorithme précédent étant appelé pour l'ensemble des k sites.

1.2. Calcul de la parcimonie sur l’arbre des espèces et sur l’arbre recombinant

Supposons un arbre des espèces (Aesp) de quatre séquences et une recombinaison de

l’espèce C vers l’espèce D. Nous obtenons un arbre recombinant (Arec). Nous allons calculer la parcimonie pour chaque arbre d’un site recombinant et d’un non recombinant.

Figure 11 : Calcul de la parcimonie d'un site recombinant et non recombinant

La figure ci-dessus nous montre que la parcimonie d’un site recombinant (SR) est plus

faible sur l’arbre recombinant, tandis que la parcimonie d’un site non recombinant (SNR) est plus faible sur l’arbre des espèces.

- 16 -

1.3. Recherche de l’arbre phylogénétique

L’arbre phylogénétique, selon le critère de parcimonie, est celui qui aura le plus petit score de parcimonie, on l’appelle aussi l’arbre optimal. La recherche de cet arbre est un problème NP complet (FOULDS et GRAHAM, 1982). L'utilisation d'une méthode heuristique permet cependant d'atteindre un arbre satisfaisant en un temps raisonnable.

La solution la plus courante est d'appliquer l'heuristique consistant à effectuer des

réarrangements à partir d'un arbre de départ (SWOFFORD et al.,1996). L'ensemble des arbres obtenus constitue ce que l'on appelle le voisinage. On sélectionne dans ce voisinage l'arbre le plus parcimonieux (l'arbre optimal du voisinage). On obtient alors un nouvel arbre à partir duquel on recalcule un nouveau voisinage. Ce processus est réitéré jusqu'à ne plus pouvoir améliorer la parcimonie.

Figure 12 : Voisinage d'un arbre

Il existe trois méthodes de réarrangement : NNI (Nearest-Neighbor Interchanges) de

complexité O(nk), SPR (Subtree Pruning and Regrafting) de complexité O(n²k) et le TBR (Tree Bisection and Reconnection) de complexité O(n3k).

- 17 -

2. Problème : Trouver les sites recombinants

Nous avons vu précédemment :

- que les sites recombinants et les sites non recombinants évoluent au cours du temps selon des arbres phylogénétiques différents (Voir II 3.2) ;

- que le score de parcimonie d’un site recombinant (resp. non recombinant) est plus faible sur l’arbre recombinant (resp. l’arbre des espèces) (Voir IV 1.2) ;

- qu’il est possible d’obtenir l’arbre qui minimise le score de parcimonie sur un ensemble de séquences données (Voir IV 1.3). Une approche possible pour déterminer si un site est recombinant ou non, serait de

calculer son score de parcimonie sur chacun des arbres possibles pour n séquences. Nous pouvons, en conséquence, regrouper les sites qui ont obtenu un score de parcimonie similaire sur un arbre ou un ensemble d’arbres. Enfin il reste à déterminer, à chacun des groupes, s’il fait partie des sites recombinants ou non recombinants.

Première difficulté, le nombre d’arbres possibles pour n séquences est : 3 × 5 × 7 × …

× (2n-5), soit O(n!). Il est impossible de calculer la parcimonie pour chacun des arbres, il y en a beaucoup trop. Le problème est donc NP-complet. Il nous faut proposer une heuristique, qui calcule sur un nombre limité d’arbres. Il ne faut pas oublier qu’il est nécessaire d’avoir des variations du score de parcimonie entre arbres.

2.1. Partitionner les séquences et estimer de leurs arbres phylogénétiques

Si les séquences sont découpées en plusieurs sous séquences à l’aide de fenêtres glissantes, alors un arbre optimum peut être calculé pour chacune de ces fenêtres. Par la suite, nous pouvons calculer la parcimonie de chaque fenêtre avec chacun des arbres obtenus. Le nombre d’arbres phylogénétiques est réduit et nous avons la certitude de pouvoir étudier les variations de parcimonie puisque nous avons la parcimonie optimale pour chaque fenêtre. En effet, si aucune variation n’est observée, cela implique que tous les arbres sont identiques, donc qu’il n’y a pas eu recombinaison.

En général, le calcul de l’arbre le plus parcimonieux est effectué sur un nombre

conséquent de sites, sinon le résultat a de grandes chances d’être erroné. Ceci pour deux raisons étroitement liées :

- Il y a de fortes probabilités de tomber dans un minimum local. Un minimum local, c’est un arbre qui n’a dans son voisinage que des arbres de parcimonie supérieure ou égale, et qui n’est pas l’arbre optimum. En effet, les variations du score de parcimonie au sein d’un voisinage sont très petites et l’on tombe dans un minimum local en quelques mouvements ;

- Deux arbres aux topologies différentes peuvent obtenir le même score de parcimonie. Dans ce cas de figure, obtenir un arbre A plutôt qu’un arbre B ou l’inverse, dépend de l’arbre de départ, c'est-à-dire de l’arbre sur lequel on calcule le premier voisinage.

- 18 -

Dans notre étude, nous cherchons à calculer l’arbre le plus parcimonieux sur un petit nombre de sites. Cependant, nous sommes dans un cadre assez particulier et nous allons utiliser ces deux caractéristiques.

La première peut être très utile. Prenons comme arbre de départ l’arbre qui minimise la

parcimonie sur la totalité des séquences (soit tous les sites). L’arbre obtenu est un bon compromis entre l’arbre des espèces et les arbres recombinants, que nous appellerons « l’arbre moyen ». En conséquence, les arbres obtenus ne seront pas foncièrement différents de l’arbre moyen. Cela nous permet d’en déduire que les arbres obtenus se sont rapprochés soit de l’arbre des espèces, soit d’un arbre recombinant.

La deuxième raison peut nous faire croire que les sites présents dans deux fenêtres n’ont pas évolué suivant le même arbre évolutif. Ce problème est résolu à condition que l’arbre de départ soit identique pour chaque fenêtre. En effet, les méthodes qui recherchent l’arbre le plus parcimonieux sont des méthodes itératives. Ainsi, les mêmes causes produiront les mêmes effets.

2.2. Identification des sites recombinants

Nous avons découpé les séquences à l’aide de s fenêtres de F1 à Fs. Puis, nous avons calculé l’arbre optimum pour chaque fenêtre, nous obtenons ainsi s arbres de A1 à As. Il nous faut maintenant déterminer pour chaque fenêtre si elle possède des sites recombinants ou non.

Pour cela nous allons calculer un score de parcimonie pour chaque arbre à partir de chaque fenêtre, nous obtenons ainsi s² scores de parcimonie de P1,1 à Ps,s que l’on peut représenter sous la forme d’un tableau.

Figure 13 : Matrice de parcimonies

Supposons que les fenêtres i à j sont composées de sites recombinants alors (Voir IV 1.2) nous obtenons deux types de fenêtres :

- les fenêtres non recombinantes qui ont : o une parcimonie inférieure sur les arbres non recombinants (A1 à Ai-1 et Aj+1 à As). o une parcimonie supérieure sur les arbres recombinants (Ai à Aj).

- Les fenêtres recombinantes qui ont : o une parcimonie supérieure sur les arbres non recombinants (A1 à Ai-1 et Aj+1 à As). o une parcimonie inférieure sur les arbres recombinants (Ai à Aj).

- 19 -

A1

As

F1 Fs…

...

...

Fi …Fj…

...

...

Ai

Aj

<

<

<

< <

>

>

>

>

Figure 14 : Identification des sites recombinants à l’aide des scores de parcimonies

L’originalité de cette méthode vient de la structure mise en place. En effet, les deux types

de fenêtres impliquent qu’il existe aussi deux types arbres aux propriétés identiques (Voir figure 11). Ainsi, nous allons détecter les couples d’arbres et de fenêtres recombinants. Pour cela, nous avons besoin d’une méthode de classification. Nous avons choisi d’utiliser la méthode du k-means (J. MCQUEEN 1967 ; E. FORGY 1965) qui permet de répartir un ensemble de données en k classes homogènes. Cette méthode classe les couples lignes-colonnes en deux classes en cherchant à minimiser la variance dans ces deux classes.

Il nous reste à identifier chaque groupe. Les sites recombinants étant en général minoritaires, nous allons compter le nombre de sites dans chacun des groupes. Le groupe qui aura le moins de sites (resp. le plus de sites) sera identifié comme recombinant (resp. non recombinant).

3. Quelques précisions

Nous venons d’étudier le fonctionnement général de cette nouvelle méthode et les

résultats (voir V) nous permettant de savoir si nous sommes sur une bonne voie ou non. Mais avant d’aller plus loin, nous allons entrer un peu plus dans les détails des points clefs de cette méthode. Ainsi nous verrons les limites et quelques optimisations possibles, ce qui nous permettra une meilleure interprétation des résultats.

- 20 -

3.1. La taille des fenêtres

La taille des fenêtres est un paramètre très important pour le bon fonctionnement de la méthode. En effet une fenêtre trop petite ne contiendra pas assez d’informations de parcimonie, le cas échéant la recherche de l’arbre optimum ne s’éloignera pas suffisamment de l’arbre de départ (Voir 2.1). Dans la situation inverse, une fenêtre trop grande a plus de chance de posséder à la fois des sites recombinants et non recombinants. Dans cette situation, deux possibilités existent : soit on reste proche de l’arbre de départ, soit on s’éloigne de l’arbre des espèces et des arbres recombinants. Ainsi, les performances de cette méthode ont de grandes chances d’être influencées par la taille des fenêtres et il faudra en tester plusieurs avant d’interpréter les résultats.

3.2. Complexité

Un mouvement recombinant est équivalent à un mouvement SPR. De ce fait, nous avons décidé de ne pas utiliser les mouvements TBR, qui effectuent des mouvements plus complexes que nécessaire et auraient augmenté la complexité. L’identification des sites recombinants se fait en 5 étapes : (a) Calcule de l’arbre de départ. (b) Découpe des séquences en s fenêtres. (c) Estimation d’un arbre pour chaque fenêtre. (d) Calcule d’un score de parcimonie pour chaque arbre et chaque fenêtre. (e) Classification à l’aide du k-means.

L’étape (a) est réalisée à l’aide des réarrangements locaux NNI et SPR dont la complexité est de O(n²k), avec n le nombre de séquences et k le nombre de sites. L’étape (b) nécessite de parcourir tous les sites, O(k). L’étape (c) est réalisée à l’aide des réarrangements locaux NNI et SPR dont la complexité est de O(n²l), avec l la somme des sites de chaque fenêtre. Si les fenêtres ne se chevauchent pas, alors l = k. L’étape (d) calcule s² parcimonies. Le calcul de la parcimonie est réalisé en O(m) avec m le nombre de sites dans une fenêtre. Ainsi, la complexité de l’étape (d) est de O(s²m), soit O(sl). L’étape (e) parcourt la matrice carrée de taille s, soit O(s²).

La complexité totale est de O(n²k) + O(k) + O(n²l) + O(sl) + O(s²). Ainsi, notre méthode de fait en O(n²k) dans la plupart des cas, ou O(n²l) sinon. En effet, s² < n²k sinon la taille des fenêtres est beaucoup trop petite et les résultats obtenus sont faux.

- 21 -

V Simulation de jeux de données

1. Arbre des espèces

Nous allons décrire le processus qui génère des arbres respectant l’horloge moléculaire.

L’hypothèse de l’horloge moléculaire stipule que les mutations génétiques s’accumulent dans le génome à une vitesse globalement proportionnelle au temps géologique, ce qui sous entend que chaque espèce évolue à la même vitesse. Afin de générer un arbre de n espèces, nous allons utiliser le processus de spéciation décrit par KUHNER et FELSENSTEIN (1994).

Une nouvelle espèce est obtenue en scindant en deux une espèce existante. Le processus propose une probabilité constante dt qu’une espèce se scinde pendant le prochain intervalle de temps de longueur dt. Ainsi, si il existe k espèces alors, une nouvelle espèce apparaîtra dans un temps ti (avec 2 ≤ i ≤ k) déterminé à l’aide d’une distribution exponentielle d’espérance 1/k. L’espèce qui va se scinder en deux est choisie aléatoirement de façon uniforme sur l’ensemble des k espèces possibles. Ce processus est itéré jusqu'à obtenir n espèces.

Figure 15 : Arbre phylogénétique respectant l'horloge moléculaire

Dans la réalité, chaque espèce n’évolue pas à la même vitesse. En conséquence, nous

allons modifier l’arbre obtenu en multipliant chaque longueur de branche par (1 + X) où X suit une distribution exponentielle d’espéranceγ. Ainsi, γ représente l’écart entre l’arbre obtenu et l’arbre modifié, il est identique pour chaque branche d’un arbre. On calcul γ avec cette formule : 0.2/(0.001 + U) où U est tiré de façon uniforme sur [0,1]. Ainsi, plus U est petit, plus l’écart entre les deux arbres est grand. Nous allons donc obtenir un coefficient sur chaque branche appelé Cj avec 1 ≤ j ≤ (k-1) × 2. Enfin, nous devons redimensionner la taille de l’arbre en multipliant chaque longueur de branche par (0.4 + 0.8V) / T, où T est la longueur total de l’arbre et V est tiré uniformément sur [0,1] une fois pour chaque arbre. Ainsi nous obtiendrons des arbres dont la longueur totale sera uniformément distribuée sur [0.4, 9].

- 22 -

2. Arbre recombinant

Un mouvement recombinant est un mouvement SPR dont le sous arbre arraché est

composé uniquement d’une feuille. En d’autres termes, nous allons choisir une feuille qui sera arrachée de l’arbre pour être rebranchée sur une autre arête (branche). Pour cela, nous choisissons une feuille aléatoirement et une distance de recombinaison d. Ensuite, nous identifions toutes les arêtes à une distance d et nous en choisissons une aléatoirement. Enfin, il faut arracher la feuille puis la rebrancher et calculer les longueurs des nouvelles branches (voir figure 13).

Figure 16 : Calculs des longueurs de branches de l’arbre recombinant

Une fois que l’arbre recombinant est obtenu nous devons le redimensionner avec le même

procédé utilisé sur les arbres des espèces. Sauf que V n’est pas tiré uniformément sur [0,1], il est identique à celui utilisé sur l’arbre des espèces.

- 23 -

VI Résultats

Afin de tester notre nouvelle méthode, nous l’avons appliquée sur une collection composée de 10 alignements de séquences définies sur 40 taxons et 1000 sites (modèle Kimura avec un ratio transition/transversion = 2). Les sites sont générés à l’aide du logiciel SeqGen (RAMBAUT and GRASSLY 1997). Les diagrammes en bâtons suivants présentent les résultats préliminaires obtenus avec différents facteurs. Nous souhaitons vérifier si notre méthode élimine correctement les sites recombinants pour ne garder que les sites non recombinants. En effet, seuls les sites non recombinants sont nécessaires à la reconstruction de l’arbre des espèces.

Figure 17 : Diagramme en baton du taux de précision et de rappel des sites non

recombinants identifiés

- 24 -

Nous allons évaluer la performance de notre méthode à l’aide : - du taux de précision, soit le pourcentage de sites correctement identifiés comme non

recombinants parmi l’ensemble des sites identifiés ; - du taux de rappel, soit le pourcentage de sites non recombinants correctement identifié

parmi l’ensemble des sites non recombinants.

Nous avons décidé de dimensionner les fenêtres afin qu’elles possèdent une quantité identique d’informations de parcimonie. Par exemple si le score de parcimonie de toute la séquence est de 6000 et que la taille des fenêtres est de 10%, alors chaque fenêtre possède au maximum 600 points de parcimonie.

Dans un premier temps, regardons les résultats de la précision. Nous observons un taux

de précision moyen compris entre 0.9 et 1, quels que soient les différents facteurs testés. Selon une autre façon d’interpréter ce résultat, nous avons au maximum 10% des sites identifiés non recombinants qui sont en réalité des sites recombinants.

Passons maintenant aux résultats du taux de rappel. Nous observons un taux de rappel moyen très proche de 1 avec 1% et 10% de sites recombinant. Ce taux chute lorsque nous regardons les résultats possédant 50% de sites recombinants. En effet, avec 50% de sites recombinants, il est probable que les fenêtres possèdent à la fois des sites recombinants et non recombinants. Ainsi, il est plus délicat de déterminer deux groupes distincts à l’aide du k-means. Nous pouvons aussi remarquer que nous obtenons de meilleurs résultats lorsque la distance de recombinaison augmente. En effet, plus cette distance augmente, plus la topologie de l’arbre recombinant est différente de l’arbre des espèces. Ainsi, la variation des scores de parcimonies est plus grande et le k-means détermine plus facilement les sites recombinants.

Maintenant, regardons les performances moyennes obtenues avec différentes tailles de

fenêtres : 2%, 5%, 10% et 20% (voir Figure 15). En premier lieu, nous observons que les performances moyennes sont toujours très bonnes avec 1% et 10% de sites recombinants. Ensuite, nous pouvons remarquer que le taux de rappel avec 50% de sites recombinants est plus élevé. Cependant, cette augmentation du taux de rappel s’accompagne d’une petite baisse du taux de précision, en particulier avec une distance de recombinaison de 1. Ce qui confirme que les fenêtres possèdent à la fois des sites recombinants et non recombinants et c’est pour cette raison que les performances sont moins bonnes. Enfin, l’augmentation des performances, lorsque la distance de recombinaison augmente, est confirmée.

- 25 -

Figure 18 : Diagramme en baton du taux moyen de précision et de rappel des sites non

recombinants identifiés

Nous pouvons en conclure que nous obtenons de très bons résultats avec 1% et 10% de

sites recombinants. De plus, il est à souligner que nous obtenons de très bon résultats avec la plus faible distance de recombinaison possible (distance =1). Cependant, la méthode atteint ses limites lorsque le pourcentage de sites recombinants et non recombinants est équivalent. Toute fois, le taux de précision obtenu avec les fenêtres de 10% et le taux moyen de rappel obtenu avec différentes tailles de fenêtres, nous laisse à penser qu’une deuxième passe, en tenant compte des résultats de la première et en modifiant la taille des fenêtres, nous permettrait d’obtenir de meilleurs résultats.

- 26 -

VII Discussion

1.1. Conclusion

Dans ce rapport nous avons étudié la recombinaison et ses conséquences dans la modélisation de l’évolution des séquences génétiques. En effet, nous avons vu qu’un mouvement recombinant modifie le schéma évolutif (l’histoire évolutive) au sein d’un alignement de séquences. En conséquence, nous avons besoin de deux arbres phylogéniques : l’arbre des espèces et l’arbre recombinant. Par la suite, nous avons étudié les méthodes existantes et leurs performances. Ainsi, nous avons pu observer que les méthodes phylogénétiques obtenaient des performances inférieures aux autres méthodes. Malgré cela, elles ont l’avantage de découvrir des mouvements recombinants anciens, ce que les autres méthodes sont incapables de faire. Ainsi, nous avons décidé de développer une nouvelle méthode phylogénétique dans le but de rattraper les performances des autres méthodes et si possible de les dépasser.

Le principal inconvénient des méthodes phylogénétiques est de traiter chaque site indépendamment des autres. En effet, la recombinaison agit sur un groupe de sites mitoyens. C’est pour cette raison que nous avons choisi une approche à l’aide de fenêtres glissantes et de tenir compte des résultats obtenus sur l’ensemble de chaque fenêtre et non pas sur chaque site. Deuxième point, qui fait l’originalité de la méthode, nous détectons les parties recombinantes à l’aide de couples composés d’un arbre et d’un ensemble sites. Plus précisément, si un ensemble de sites est détecté comme recombinant alors l’arbre qui lui correspond est aussi détecté comme recombinant, l’un ne va pas sans l’autre. Enfin, nous avons décidé d’évaluer les arbres phylogénétiques à l’aide du critère de parcimonie. En effet, les méthodes qui utilisent ce critère ont une complexité polynomiale, ce qui permet d’obtenir des résultats dans un laps de temps assez court.

Nous avons implémenté cette méthode en JAVA et nous avons testé ces performances sur des données simulées. Les résultats préliminaires obtenus sont très encourageants. En effet, nous obtenons de très bons résultats en particulier dans des conditions difficiles : des pourcentages de sites recombinants et une distance de recombinaison très faibles. Nous avons pu aussi tester les limites de notre méthode, dont les performances chutent lorsque le pourcentage de sites recombinants est équivalent à celui des sites non recombinants. Cependant, notre méthode garde des caractéristiques étonnantes au niveau de la précision de la détection des sites non recombinants. Ce qui nous a convaincu d’être dans la bonne direction.

- 27 -

1.2. Perspectives

Une poursuite de ce stage nous amènerait à rechercher des améliorations de cette méthode. Nous allons en évoquer quelques une ici.

La première consiste à pondérer la matrice des parcimonies (voir V 2.2) à l’aide d’une

matrice des distances entre topologie d’arbres. Une matrice de distance permet d’évaluer la différence qu’il y a entre deux topologies d’arbres. Plus la distance est élevée plus les topologies sont différentes. Ainsi, si deux arbres sont presque identiques mais que nous observons une forte variation de leurs parcimonies alors, il parait judicieux de diminuer cette variation. A l’inverse si deux arbres ont des topologies très différentes mais qu’ils obtiennent une faible variation de leurs parcimonies, il est dans l’intérêt de la méthode d’augmenter cette variation. Nous avons implémenté cette amélioration et les premiers tests nous indiquent une forte amélioration des performances.

Une deuxième solution serait de réitérer le processus en modifiant les fenêtres glissantes,

à l’aide des résultats obtenus dans l’étape précédente, jusqu'à obtenir une solution identique à l’étape suivante (jusqu’à la stabilité du processus). En effet, dans notre méthode nous choisissons une taille de fenêtre fixe, ce qui découpe les séquences de façon arbitraire et pas forcement la plus optimisée. Les résultats préliminaires nous montrent que nous avons une précision de 100% dans la détection des sites recombinants. Ainsi, nous pouvons nous servir de cette information pour redimensionner les fenêtres et obtenir des résultats plus précis.

Enfin, une dernière solution envisagée à ce jour, qui rejoint la seconde proposition, serait

de réaliser dans un premier temps un k-means qui regroupe les couples dans 3 ou 4 groupes distincts. En effet, dans le cas où nos fenêtres chevauchent des sites recombinants et non recombinants, il parait judicieux de ne classer ces couples dans aucun des deux groupes (recombinants et non recombinants) mais dans un troisième groupe. De plus, autoriser plus de deux groupes distincts augmentent les contraintes de minimisation de la variance dans chacun des groupes et permet d’obtenir un résultat plus précis.

- 28 -

VIII Références bibliographiques AWADALLA , P., 2003 : The evolutionary genomics of pathogen recombination. Nat. Rev. Genet.

4(1):50-60. BRUEN TREVOR C., PHILIPPE HERVE and BRYANT DAVID , 2006 : A simple and robust statistical test for

detecting the presence of recombination. Genetics 172(4):2665-81. FITCH. W. M., 1971 : Toward defining the course of evolution : minimum change for a specified

tree topology. Systematic Zoology, 20:406-416. FOULDS, L. R., and GRAHAM, R., 1982 : The Steiner problem in phylogeny is NP-complete.

Advances in Applied Mathematics, 3 :43-49. FORGY, E., 1965 : Cluster analysis of multivariate data : Efficiency vs. interpretability of

classifications. Biometrics, 21:768. JAKOBSEN, I. B., and S. EASTEAL. 1996 : A program for calculating and displaying compatibility

matrices as an aid to determining reticulate evolution in molecular sequences. Comput. Appl. Biosci. 12:291-295.

KUHNER,M. K., and J. FELSENSTEIN. 1994.Asimulation comparison of phylogeny algorithms under equal and unequal evolutionary rates. Mol. Biol. Evol. 11:459–468.

MARTIN, D., and E. RYBICKI . 2000 : RDP : Detection of recombination amongst aligned sequences. Bioinformatics 16:562-563.

MAYNARD SMITH, J., 1992 : Analysing the mosaic structure of genes. J. Mol. Evol. 34(2):126-129. MAYNARD SMITH, J., 1999 : The detection and measurement of recombination from sequence data.

Genetics. 153:126-129. MAYNARD SMITH, J., and SMITH, N. H., 1998 : Detecting recombination from gene trees. Mol. Biol.

Evol. 15:590-599. MCQUEEN, J., 1967 : Some methods for classification and analysis of multivariate observations.

In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1:281-297.

POSADA, D., 2002 : Evaluation of methods for detecting recombination from DNA sequences : empirical data. Mol. Biol. Evol. 19(5):708-717.

POSADA, D., and K. A. CRANDALL , 2001 : Evaluation of methods for detecting recombination from DNA sequences : computer simulations. Proc. Natl. Acad. Sci. USA 98(24):13757-13762.

RAMBAUT , A. and GRASSLY, N. C., 1997 : An application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Comput. Appl. Biosci. 13:235-238.

SAWYER, S. A. 1999 : GENECONV: a computer package for the statistical detection of gene conversion. Distributed by the author, Department of Mathematics, Washington University in St. Louis, available at http://www.math.wustl.edu/~sawyer.

SWOFFORD, D.L., OLSEN, P.J., WADDELL, P.J. and HILLIS, D.M., 1996 : Molecular Systematics , Chapitre Phylogenetic Inférence, pages 407-514. Sinauer Associates, Sunderland, Massachusetts.

WEILLER, G. F. 1998 : Phylogenetic profiles : a graphical method for detecting genetic recombination in homologous sequences. Mol. Bio. Evol. 15:326-335.

WIUF, C., T. CHRISTENSEN, and J. HEIN. 2001 : A simulation study of the reliability of recombination detection methods. Mol. Biol.Evol. 18:1929-1939.