Approche combinatoire des réseaux phylogénétiques 

Les réseaux phylogénétiques

   Il arrive cependant que certains transferts de matériel génétique aient lieu entre individus de deux espèces coexistantes différentes. Même si les hybrides sont généralement stériles pour les mammifères, il est fréquent que des poissons [Hubbs, 1955], et surtout des plantes [Grant, 1971], de deux espèces différentes, aient une descendance commune fertile, qui donne naissance à une nouvelle espèce par hybridation. Les transferts de matériel génétique entre individus d’espèces coexistantes sont également causés par d’autres mécanismes biologiques, en particulier le transfert horizontal chez les bactéries : soit par transmission directe d’une bactérie à une autre (conjugaison), soit par l’intermédiaire de l’environnement (transformation) ou d’un virus (transduction).

Définition des réseaux de niveau k

  Un réseau N de niveau k est un réseau enraciné explicite binaire dont chaque blob contient au plus k sommets hybrides. Il est strictement de niveau k s’il est de niveau k mais pas de niveau k−1. Plusieurs remarques s’imposent sur cette définition qui varie légèrement selon les articles et les contextes. Tout d’abord, les définitions utilisées classiquement n’évoquent pas les blobs, mais les blocs du réseau. Dans le cas où nous nous restreignons aux réseaux binaires (comme dans [Jansson et Sung, 2006] et la plupart des articles apparus depuis, mais contrairement à Choy et al. [2005] qui ne s’intéressaient pas à une problématique de reconstruction de réseaux), les deux concepts sont équivalents, excepté pour les isthmes, qui correspondent chacun à un bloc (car en supprimant un de leurs sommets, le sommet unique restant est un graphe connexe, deux sommets séparés par un isthme constituent donc un graphe biconnexe) mais à deux blobs triviaux. Toutefois, si nous autorisons les sommets de réticulation hybrides, comme nous l’avons vu en section 1.3.3, considérer les blocs consiste à dire que le réseau N de la figure 1.11(i) de la page 32 a deux blocs, qu’il est de niveau 1, et donc le rendre équivalent à son raffinement N1. Pour considérer que le sommet u représente une réelle incertitude et que N a également les raffinements N2 à N5, il faut prendre en compte le fait que les réseaux N2 à N5 sont de niveau 2, et donc utiliser le concept de blob dans la définition du réseau pour affirmer que N est de niveau Ainsi, cette définition peut s’étendre aux réseaux non binaires. En ce qui concerne les ajustements, rappelons que nous autorisons ici les feuilles hybrides, c’est-à-dire les sommets de degré entrant 2 et de degré sortant nul. Ce point sera un détail par la suite, sauf justement quand on étudiera l’unicité des réseaux qui contiennent un certain ensemble de triplets où, pour éviter les ambiguïtés inutiles, nous forcerons chaque feuille à n’avoir qu’un parent. Pour la même raison, dans les chapitres 2 et 3, nous considérerons également qu’un réseau de niveau k ne contient aucun blob à 2 ou 3 sommets 3 : en effet, dans ce cas on autoriserait le réseau de la figure 1.15(i), alors que celui-ci est moins parcimonieux (en termes de nombre d’arêtes et de sommets) que le réseau N0 de la figure 1.15(ii), qui contient exactement les mêmes arbres, clades souples et stricts, et triplets, et qu’on peut donc considérer comme tout aussi informatif biologiquement.

Classification des restrictions sur les réseaux phylogénétiques

   Les descriptions précédemment proposées dans la littérature de l’ensemble des diverses classes de réseaux phylogénétiques ont pris plusieurs formes. Les catalogues de méthodes (huit illustrées sur le même jeu de données dans [Posada et Crandall, 2001] et sept dans [Makarenkov et al., 2006]) laissent progressivement apparaître la distinction entre réseaux abstraits et explicites [Morrison, 2005, 2010]. Une hiérarchie récapitulative est proposée pour classer divers types de réseaux [Huson et Klöpper, 2005], organisée selon le type de méthodes et de données en entrée. Elle fait apparaître des classes comme les réseaux d’hybridation (des réseaux explicites enracinés construits à partir d’arbres en tentant de minimiser le nombre de sommets hybrides), ou les réseaux de recombinaison (des réseaux explicites enracinés construits à partir de séquences binaires indiquant la présence/absence d’un caractère, ou d’un allèle d’un gène) toutes deux contenues dans la classe des réseaux réticulés. Ces dénominations laissant planer un doute sur une organisation en fonction des types de réseaux ou des types de données pour leur reconstruction, le premier livre consacré aux réseaux phylogénétiques est organisé de façon explicite selon les types de données en entrée des algorithmes [Huson et al., 2011]. Nous choisissons donc ici de nous focaliser sur les types de réseaux, et proposons à la fin de cette section des diagrammes récapitulatifs des classes de réseaux phylogénétiques basés uniquement sur leurs propriétés topologiques et combinatoires, sans se préoccuper d’éventuels étiquetages ou des données utilisées pour les construire. Ces diagrammes sont des diagrammes de Hasse des classes de réseaux phylogénétiques, et leur intérêt est de faire apparaître distinctement des inclusions qui traduisent que les propriétés combinatoires d’une classe se transmettent à ses sous-classes. Des parallélismes entre les diagrammes permettent aussi de donner un éclairage différent sur des algorithmes existants pour la reconstruction de réseaux abstraits, et de les réutiliser pour construire des réseaux explicites, comme nous le verrons par exemple à la fin de la section 2.2.2.Quant à la classification en fonction du type de données utilisées en entrée, nous expliquerons dans la section 4.1.2 comment nous avons choisi d’organiser ces informations au sein d’une bibliographie interactive [Gambette, 2010] pour donner un panorama aussi complet et facile à visiter que possible de l’ensemble des méthodes de reconstruction ou de traitement des réseaux phylogénétiques. Mais avant de présenter les diagrammes récapitulatifs promis, montrons quelques liens entre des sous-classes de réseaux phylogénétiques explicites, et des sous-classes de réseaux abstraits, qui y apparaîtront.

Reconstruction à partir de triplets

   La première question algorithmique que l’on considère naturellement sur les triplets et les réseaux phylogénétiques explicites est de déterminer l’ensemble des triplets contenus dans un réseau, ce qui est fait en temps optimal O(n3 ) pour un réseau à n feuilles, par un algorithme de programmation dynamique [Byrka et al., 2010]. Citons également les algorithmes de reconstruction d’arbres à partir de triplets. Nous avons déjà évoqué l’algorithme de Aho et al. et ses diverses implémentations [Aho et al., 1981; Henzinger et al., 1999; Jansson et al., 2005]. Si l’ensemble de triplets en entrée est dense, un autre résultat intéressant est un algorithme certifiant de reconstruction en temps optimal O(n3 ): s’il existe un arbre qui contient les triplets alors on le reconstruit, sinon on exhibe un conflit qui implique un ensemble de triplets portant sur quatre feuilles [Guillemot et Berry, 2010]. La première garantie donnée sur la reconstruction de réseaux phylogénétiques explicites binaires enracinés à partir de triplets est qu’il est possible de reconstruire de tels réseaux pour tout ensemble de triplets [Jansson et Sung, 2006] car il existe un réseau phylogénétique explicite enraciné binaire sur n feuilles, construit à partir d’un réseau de tri de n éléments [Batcher, 1968], qui contient tous les triplets possibles sur ces n feuilles. Toutefois ce réseau a peu d’intérêt biologique puisqu’il contient justement tous les triplets possibles, et a un nombre très important de sommets hybrides. Le premier algorithme utile d’un point de vue phylogénétique est celui de reconstruction de réseaux de niveau 1 à partir d’un ensemble dense R de triplets. Il s’exécute en temps O(n6) [Jansson et Sung, 2006] et se base sur le concept des SN- ensembles : cet algorithme diviser-pour-régner consiste à identifier des sous-ensembles de feuilles L ⊆ X, appelés SNensembles, tels que pour tous a, b ∈ L et c 6∈ L, R|{a,b,c} = ab|c (le seul triplet sur les feuilles a,b,c est ab|c) . Ces SN-ensembles ont la particularité de former une famille laminaire (et donc d’être représentables par un SN-arbre enraciné) quand l’ensemble de triplets en entrée est dense. Le calcul du SN-arbre, intialement réalisé par un algorithme en temps O(n5 )[Jansson et Sung,2006], peut en fait s’effectuer en temps O(n3)[Jansson et al., 2006]. De plus, dans tout réseau N qui contient les triplets de R, tout SN-ensemble de R est l’ensemble des feuilles descendantes des cibles d’une union d’isthmes dont les sources appartiennent à un même blob B de N [van Iersel et al., 2009a].
R = {c|ab,d|ab,e|ab,a|cd,e|ac,a|de,b|cd,b|ce,b|de,e|cd}, dont le SN ensemble {c,d} est l’ensemble des feuilles sous l’isthme w, {a,b} est l’ensemble des feuilles sous u et v, et {a,b,c,d,e} est l’ensemble des feuilles sous tous les isthmes de B : u, v, w et x. Ainsi, on peut associer à tout SN-ensemble de R un blob B du réseau solution. Cette propriété explique le nom donné à ces ensembles : “SN” signifie ici “simple network” car pour tout blob du réseau, si l’on contracte, pour chacun de ses isthmes incidents, tous les sommets descendants de la cible de l’isthme, on obtient un réseau simple.

Algorithme de complexité paramétrée pour MCS-r

   Il existe un algorithme FPT en le nombre de conflits pour résoudre le problème MCT pour un ensemble d’arbres phylogénétiques enracinés sur X [Berry et Nicolas, 2006]. Cet algorithme peut également être utilisé pour résoudre le problème MCS-r en codant chaque clade C par un arbre phylogénétique qui le contient. Nous présentons maintenant l’algorithme FPT implémenté dans Dendroscope en septembre 2008 pour résoudre directement le problème MCS-r. Cet algorithme, appelé SeedGrowing fonctionne très bien en pratique. Pour toute paire de clades chevauchants A,B ∈ C, on définit la déclaration d’incompatibilité (A−B,A∩B,B−A). On note L la liste de toutes ces déclarations d’incompatibilité pour l’ensemble de clades C (voir figure 2.18(b) page 95). Pour résoudre le problème MCS-r, on doit trouver un ensemble minimum de taxons R ⊆ X qui résout toutes les déclarations d’incompatibilité dans L, c’est-à-dire que pour chacune d’entre elles, au moins un de ses trois termes est contenu dans R. L’algorithme SeedGrowing, décrit en pseudo-code en figure 2.16, fonctionne en construisant un ensemble S de solutions candidates, appelées graines, dont il essaie d’étendre celle de taille minimale qui résout le plus de déclarations d’incompatibilité, jusqu’à en trouver une qui résout toutes les déclarations d’incompatibilités.

Table des matières

Remerciements
Préambule
Introduction
Les arbres phylogénétiques
Les réseaux phylogénétiques
Problématiques
Plan de la thèse
Publications issues de cette thèse
I Approche combinatoire des réseaux phylogénétiques 
1 Arbres et réseaux comme objets combinatoires 
1.1 Premières définitions
1.1.1 Réseaux et graphes orientés
1.1.2 Arbres phylogénétiques
1.2 Propriétés combinatoires des arbres
1.2.1 Une richesse mathématique
1.2.2 Décompositions en sous-ensembles de feuilles
1.3 Propriétés combinatoires des réseaux
1.3.1 Réseaux abstraits et explicites
1.3.2 Réseaux et sous-ensembles de feuilles
1.3.3 Multifurcations et multiréticulations
1.4 Restrictions sur les modèles de réseaux
1.4.1 Restrictions sur les ensembles de clades et de bipartitions
1.4.2 Réseaux à une couche de réticulation
1.4.3 Réseaux de niveau k
1.4.4 Réseaux non enracinés de niveau k
1.4.5 Autres restrictions de réseaux phylogénétiques explicites
1.5 Classification des restrictions sur les réseaux phylogénétiques
1.5.1 Hiérarchies faibles, pyramides et niveau 1
1.5.2 Ensembles circulaires de bipartitions et niveau 1
1.5.3 Diagrammes récapitulatifs des inclusions de sous-classes
2 Algorithmes combinatoires de reconstruction 
2.1 Méthodes et algorithmes existants
2.1.1 Panorama des diverses méthodes
2.1.2 Reconstruction à partir de triplets
2.2 Reconstruction à partir de quadruplets
2.2.1 Extraction des quadruplets d’un réseau
2.2.2 Difficulté de la reconstruction dans le cas général
2.2.3 Structure arborée depuis un ensemble dense de quadruplets
2.2.4 Reconstruction dans des cas restreints
2.3 Reconstruction à partir de clades
2.3.1 Test de compatibilité
2.3.2 Décomposition des réseaux phylogénétiques
2.3.3 Recherche d’un ensemble maximum de taxons compatibles
2.3.4 Ajout des réticulations
II Utilisation pratique des méthodes combinatoires 
3 Limites des méthodes combinatoires 
3.1 Bruit et silence dans les données
3.1.1 Bruit et corrections d’erreurs sur les triplets
3.1.2 Silence et inférence des données manquantes
3.2 Explosion de complexité en fonction du niveau
3.2.1 Bornes sur le nombre de générateurs
3.2.2 Algorithme de construction des générateurs de niveau k
3.2.3 Niveau élevé de réseaux simulés
3.3 Fiabilité des réseaux obtenus par les méthodes combinatoires
3.3.1 Encodage des réseaux simples de niveau 1
3.3.2 Encodage des réseaux de niveau 1
3.3.3 Encodage des réseaux de niveau 2 et plus
4 Les méthodes combinatoires sur des données réelles
4.1 Sélection et prétraitement des données
4.1.1 Possibilités de types de données en entrée
4.1.2 Choix de la méthode de reconstruction
4.1.3 Problème de choix des gènes et des espèces dans un phylome
4.1.4 Interface de sélection semi-automatique d’arbres et d’espèces
4.2 Exemples sur des données réelles
4.2.1 Outils utilisés
4.2.2 Utilisation sur les données HOGENOM
Conclusion et perspectives
Problèmes ouverts
Perspectives sur les méthodes combinatoires en phylogénie réticulée
Annexes
Bibliographie
Glossaire français-anglais
Index
Table des figures
Liste des tableaux
Publications en marge du sujet de thèse
Algorithmique des graphes
Traitement automatique des langues naturelles

Télécharger le rapport complet