Phylogénie
Sommaire
Principe
La phylogénie ou reconstruction phylogénétique peut être définie comme la reconstruction de l'histoire évolutionnaire d'un ensemble d'espèces. L'évolution entre les espèces est représentée sous forme d'un arbre (phylogénétique) dont les branches indiquent le degré de proximité entre les espèces
Il existe deux façons de caractériser les espèces :
- soit en se basant sur leurs phénotypes, c'est à dire l'ensemble des caractèristiques qu'elles expriment (suivant leur apparence),
- soit en se basant sur leurs génotypes, c'est à dire l'ensemble des caractéristiques comprisent dans leurs génomes et qu'elles peuvent éventuellement exprimer.
Le premier genre d'approche basé sur les phénotypes est utilisée lorsqu'on ne dispose d'aucune information sur les génomes des espèces. Depuis le lancement des différents programmes de séquençage des génomes on a de plus en plus tendance à utilisé le second type d'approche.
Ici nous ne nous focaliserons que sur le second type de caractérisation. Nous utiliserons des séquences nucléotidiques (ou d'acides aminés) pour distinguer les espèces entre elles.
Il existe 3 types d'approches pour s'attaquer au problème de reconstruction phylogénétique :
- les approches basées sur les distances utilisent une mesure de distance ou de similarité afin de regrouper des séquences proches, en anglais on parle de clustering. Ces approches sont très efficaces car elles sont basées sur un algorithme de complexité polynomiale ce qui les rend particulièrement adaptées pour des études à grande échelle.
- les approches axées sur les caractères cherchent le meilleur arbre possible dans une topologie d'arbre étant donné un critère d'optimalité. Le critère le plus largement utilisé est le critère de maximum de parcimonie (Maximum Parsimony Criterion) pour lequel on considère que le meilleur arbre est celui qui requiert le minimum de changements. Le problème de maximum de parcimonie est un problème NP-dur dans le cas général, il est donc nécessaire de faire appel à des techniques heuristiques et d'optimisation afin de le traiter efficacement dans un temps raisonnable.
- enfin, les approches statistiques principalement basées sur la méthode de maximum de vraisemblance (Maximum Likelihood) et l'approche bayésienne.
Chacune de ces méthodes possède des avantages et des inconvénients. Faisant partie d'une équipe de recherche travaillant en optimisation combinatoire, nous avons choisi de nous intéresser à la recherche du Maximum de Parcimonie.
Méthodes
Dans le cadre de nos recherches au laboratoire LERIA, nous nous intéressons aux méthodes de caractères basées sur le critère de Maximum de Parcimonie avec modèle d'évaluation de Fitch, pour lequel les changements sont équivalents, i.e. possèdent le même coût.
Hydra (2006)
Nous avons mis au point un premier logiciel baptisé Hydra qui est une implantation d'un algorithme mémétique (algorithme génétique + recherche locale). Hydra introduit plusieurs nouveaux concepts (cf [2]) :
- définition d'une distance dite topologique qui permet de calculer une distance entre noeuds et notamment entre feuilles de manière à établir une matrice de distances
- utilisation de cette distance pour établir un opérateur de croisement DiBIP (Distance-based Information Preservation tree crossover) entre arbres
- utilisation de cette distance pour la création d'un nouveau voisinage dit progressif (Progressive Neighborhood, en fait on pourrait le qualifier de régressif), dont le but est d'autoriser les changements les plus importants au début de la recherche pour finalement ne permettre que des changements mineurs à la fin de la recherche
SAMPARS (2012)
Un deuxième logiciel nommé SAMPARS (Simulated Annealing for Maximum PARSimony [1]) a été créé. Il se base sur un recuit simulé avec une amélioration de la fonction de sélection du prochain voisin et intègre des résultats du travail de Karla Vazquez-Ortiz étudiante de Master sous la direction d'Eduardo Rodriguez-Tello [5]. Ce logiciel offre des résultats bien meilleurs que LVB écrit par Daniel Barker (fondé également sur un recuit simulé) et a permis d'améliorer les résultats d'Hydra pour 10 problèmes du jeux de tests de C. C. Ribeiro.
Jeux de données
Les jeux de données sont les suivants :
- set1: ANGI, CARP, GOLO, ..., TENU
- set2: tst01 à tst20
- set3: jeux issus de treebase.org (m0808, m0972, ...)
- set4: jeux issus d'un article de Morrison [6]
Résultats
Les expériences ont été conduites sur des jeux de test aléatoires de [4]. Nous avons pris la valeur minimum pour 30 exécutions de SAMPARS. Pour de plus amples renseignements concernant les conditions expérimentales et le paramètrage de SAMPARS, lire [1]. La description des colonnes de la table ci-après est la suivante :
- problem : nom du problème
- n : nombre de séquences
- k : longueur d'une séquence
- LVB : meilleur score obtenu par LVB pour 30 exécutions
- Hydra : meilleur score reporté dans [3]
- SAMPARS : meilleur score trouvé par SAMPARS
- diff : différence entre score de Hydra et celui de SAMPARS, si la valeur est négative alors SAMPARS est meilleur qu'Hydra.
| problem | n | k | LVB | Hydra | SAMPARS | diff. |
| tst01 | 45 | 61 | 549 | 545 | 545 | 0 |
| tst02 | 47 | 151 | 1365 | 1354 | 1354 | 0 |
| tst03 | 49 | 111 | 840 | 833 | 833 | 0 |
| tst04 | 50 | 97 | 594 | 588 | 587 | -1 |
| tst05 | 52 | 75 | 793 | 789 | 789 | 0 |
| tst06 | 54 | 65 | 605 | 596 | 596 | 0 |
| tst07 | 56 | 143 | 1280 | 1269 | 1269 | 0 |
| tst08 | 57 | 119 | 867 | 852 | 852 | 0 |
| tst09 | 59 | 93 | 1153 | 1144 | 1141 | -3 |
| tst10 | 60 | 71 | 727 | 721 | 720 | -1 |
| tst11 | 62 | 63 | 549 | 542 | 540 | -2 |
| tst12 | 64 | 147 | 1240 | 1211 | 1208 | -3 |
| tst13 | 65 | 113 | 1532 | 1515 | 1515 | 0 |
| tst14 | 67 | 99 | 1175 | 1160 | 1160 | 0 |
| tst15 | 69 | 77 | 770 | 752 | 752 | 0 |
| tst16 | 70 | 69 | 547 | 529 | 527 | -2 |
| tst17 | 71 | 159 | 2463 | 2453 | 2450 | -3 |
| tst18 | 73 | 117 | 1552 | 1522 | 1521 | -1 |
| tst19 | 74 | 95 | 1031 | 1013 | 1012 | -1 |
| tst20 | 75 | 79 | 688 | 661 | 659 | -2 |
| sum | n/a | n/a | 20320 | 20049 | 20030 | -19 |
SAMPARS permet d'améliorer 10 des meilleurs résultats de [3].
Outils
Arbalet
Arbalet est un outil dédié à l'affichage et la gestion des arbres phylogénétiques avec Maximum de Parcimonie.
Bibliographie
- [1] Jean-Michel Richer, Eduardo Rodriguez-Tello, Karla Esmeralda Vazquez-Ortiz, Maximum Parsimony Phylogenetic Inference Using Simulated Annealing, EVOLVE 2012, Mexico City, Mexico, August 7 - 9, 2012
- [2] Chapter 26 in Algorithms in Computational Molecular Biology, Wiley, Series: Bioinformatics: Computational Techniques and Engineering, Edited by Mourad Elloumi, Albert Y. Zomaya. 2011, ISBN 978-0-470-50519-9
- [3] Adrien Goëffon, Nouvelles heuristiques de voisinage et mémétiques pour le problème Maximum de Parcimonie, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers, Cedex 1, France, 2006
- [4] C. C. Ribeiro and D. S. Vianna. A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure. International Transactions in Operational Research 12:1-14, 2005
- [5] Karla E. Vazquez-Ortiz and Eduardo Rodriguez-Tello, Metaheuristics for the Maximum Parsimony Problem, Proceedings of the Sixth IASTED CIB 2011, Pittsburgh, PA, USA, pp. 105-113, ACTA Press, November 2011
- [6] David A. Morrison, Increasing the Efficiency of Searches for the Maximum Likelihood Tree in a Phylogenetic Analysis of up to 150 Nucleotide Sequences, Systematic Biology, 56(6), 988--1010, 2007, DOI: 10.1080/10635150701779808.