CHAPITRE 2. GÉNOMIQUE
FIGURE 2.14 - Arbre de gènes étiquetés
extrait de la réconciliation de l'arbre de gène dans l'arbre
d'espèce
cessaires pour la compréhension du sujet. La
dernière partie du chapitre a présenté deux grands types
de traitement informatique sur les objets biologiques qui sont la recherche de
similarité entre séquences et l'évolution des
séquences biologiques.
Les concepts de base étant présentés, le
chapitre suivant va s'atteler à présenter un état de l'art
des méthodes computationnelles actuelles pour la construction des arbres
phylogénétiques, en présentant les limites de ces
approches pour lesquelles nous allons proposer de nouvelles solutions.
16
CHAPITRE TROIS
ÉTAT DE L' ART
Les différents processus biologiques sur lesquels
s'appuie la phylogénie ont été introduits au chapitre
précédent. Ce présent chapitre a pour objectif de faire un
état des lieux de l'art des solutions qui sont actuellement
utilisées pour reconstruire la phylogénie des
gènes.
Nous commencerons par présenter les approches
générales de construction d'arbres phylogénétiques
puis, plus spécifiquement, celles de construction des arbres de
gènes. Nous relèverons les limites des méthodes actuelles
qui seront corrigées par la suite.
Il faut cependant noter que dans ce chapitre, tous les arbres
phylogénétiques considérés seront binaires,
c'est-à-dire que tous les noeuds internes d'un arbre possèdent
deux enfants. Cette propriété ne constitue pas une limitation,
car, tout arbre non binaire pourra être approximé par un arbre
binaire.
3.1 Méthodes de construction d'arbres
phylogénétiques
Il existe plusieurs techniques de construction d'arbres
phylogénétiques. Ces méthodes basées sur des
problèmes d'optimisation reposent sur plusieurs critères à
savoir : (i) la distance entre les séquences, (ii) la parcimonie et
(iii) vraisemblance. Nous commencerons par présenter la méthode
naïve consistant à énumérer toutes les topologies
d'arbre possible, puis nous décrirons les trois méthodes
basées sur les critères ci-dessus.
3.1.1 Énumération des arbres
Cette méthode consiste à générer
toutes les topologies d'arbre possibles étant donné un ensemble
de gènes qui sont les feuilles de l'arbre, pour ensuite choisir parmi
ces topologies, un arbre minimisant un critère donné. Par
récurrence, on peut
17
| 
