CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
les arbres enracinés en un noeud de création qui
peuvent contenir deux protéines du même gène.
FIGURE 4.2 - Exemple de réconciliation d'arbres de
protéines avec arbre de gènes
Coût de réconciliation : Le
coût de réconciliation par LCA de l'arbre G avec l'arbre
S est le nombre de noeuds de duplication et d'événements de perte
de gènes dans G résultant de la réconciliation par LCA de
G avec S.
Par extension, le coût de réconciliation par
LCA de l'arbre P avec l'arbre G est le nombre de noeuds de création
et d'événements de perte de protéines dans P
résultant de la réconciliation par LCA de P avec G.
Le coût de double réconciliation de G
avec P et S est la somme du coût de réconciliation par LCA de G
avec S et du coût de réconciliation par LCA de P avec G.
Les définitions précédentes nous
permettent maintenant d'introduire le problème d'optimisation dont
l'objectif est de reconstruire un arbre de gènes optimal G, étant
donné l'arbre des protéines P et l'arbre d'espèces S.
Problème: MINDRGT (POUR "MINIMUM DOUBLE
RECONCILIATION GENETREE" EN ANGLAIS) :
Entrées : Un arbre d'espèce S pour
un ensemble d'espèces S ; un arbre de protéines P pour un
ensemble de protéines P
Sortie : Un arbre de gènes G pour G
= {g(x) : x E L(P)} tel que le
coût de double
29
CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
FIGURE 4.3 - Arbre de gènes étiqueté
FIGURE 4.4 - arbre d'espèces
30
CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
réconciliation de P vers G et S
est minimum.
Le problème d'optimisation MinDRGT suppose que l'arbre
des protéines P est connu. Dans le cas où l'arbre des
protéines n'est pas entièrement connu, mais un ensemble de
sous-arbres partiels P1. . . P, couvrant tout l'ensemble P
est connu, le problème devient :
Problème: MINDRPGT (POUR "MINIMUM
DOUBLE RECONCILIATION PROTEIN AND GENE TREES" EN ANGLAIS) :
Entrées : Un arbre d'espèce
S pour un ensemble d'espèces S ; un ensemble de sous-arbres de
protéines P1 . . . P, couvrant l'ensemble des
protéines P
Sortie : Un arbre de protéines P
tel que chaque Pi, 1 = i = k, est un sous-arbre
de P, et un arbre de gènes G pour G =
{g(x) : x E L(P)} tel que le coût de double
réconciliation de P vers G et S est
minimum.
La méthodologie de construction d'arbre de gènes
présentée dans la section suivante consiste à construire
un ensemble de sous-arbres P1 . . . P, couvrant l'ensemble
des protéines P, puis à utiliser une solution heuristique6
du problème MinDRPGT pour reconstruire l'arbre de protéines
P et l'arbre de gènes G.
4.2 Méthodologie : Processus à sept
étapes
L'approche méthodologique utilisée pour la
construction des arbres de gènes en tenant compte de toutes les
protéines de chaque gène est basée sur une solution
heuristique gloutonne pour résoudre le problème MinDRPGT.
L'approche méthodologique est résumée dans un processus
à sept étapes illustrées à la figure 4.5.
4.2.1 Étape 1 : Définition du jeu de
données
La première étape consiste à
définir l'ensemble des protéines de la famille de gènes
dont on veut reconstruire l'arbre. Par définition, une famille de
gène est composée d'un gène donné, tous ses
orthologues, ses paralogues intra-spécifiques (au sein de la même
espèce) et ses paralogues inter-spécifiques (dans des
espèces différentes). Puis, dans la famille de gène, nous
retenons uniquement les gènes produisant au moins une protéine.
Pour chaque protéine produite par un gène de la famille, nous
6. L'analyse de la complexité des problèmes
MinDRPT et MinDRPGT, et la conception de solution algorithmique exacte, le cas
échéant, seront approfondie dans le cadre d'une thèse de
doctorat.
3
4
| 
