CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
et l'ensemble des sommets de T est noté
V(T). Étant donné un noeud x E V(T), le
sous-arbre complet5 de T enracinée en x est
notée T[x]. Le plus proche ancêtre commun (en
anglais, least common ancestor (lca)) d'un sous-ensemble L'
de £(T) dans T, notée
lcaT(L'), est l'ancêtre commun à toutes les
feuilles L' qui est le plus éloigné de la
racine de T. Étant donné un noeud interne x de
T, les deux enfants de x sont arbitrairement
désignés par xl et xr (pour left et
right, en anglais).
Arbres de protéines, gènes, et espèces :
Nous notons S un arbre des espèces pour l'ensemble S,
G est un arbre des gènes pour l'ensemble G, et P
un arbre des protéines pour l'ensemble P.
La fonction de correspondance s est étendue
pour devenir une fonction de V(G) E G vers V(S) comme suit :
si x est un noeud interne de G, alors s(x) =
lcaS({s(x') : x' E £(G[x])}), c'est à dire que
l'image d'un noeud x E V(G) dans V(S) est le plus proche
ancêtre commun, dans l'arbre S, de toutes les images des
feuilles du sous-arbre G[x].
De même, nous étendons la fonction de
correspondance g pour qu'elle devienne une fonction de V(P)
vers V(G) : si x est un noeud interne de P,
alors g(x) = lcaG({g(x') : x' E
£(P[x])}).
Réconciliation par LCA : Chaque noeud interne de
l'arbre G représente un gène ancestral au moment d'un
événement de spéciation (Spec) ou de duplication (Dup) de
gènes. La réconciliation par LCA de G avec
S est une fonction d'étiquetage lG : V(G) - £(G) ?
{Spec, Dup} tels que l'étiquette d'un noeud interne x de
G est lG(x) = Spec si s(x) =6 s(xl) et s(x) =6
s(xr), et sinon lG(x) = Dup.
Nous étendons la notion de réconciliation aux
arbres de protéines comme suit : chaque noeud interne de l'arbre P
représente une protéine ancestrale au moment d'un
événement de spéciation (Spec), de duplication (Dup) ou de
création (Creat) de protéines. La réconciliation par
LCA de P avec G est une fonction d'étiquetage
lP : V(P) - £(P) ? {Spec, Dup, Creat} tels que l'étiquette
d'un noeud interne x de P est lP (x) = Spec si
g(x) =6 g(xl) et g(x) =6 g(xr) et lG(g(x)) =
Spec, sinon lP (x) = Dup si g(x) =6 g(xl) et g(x) =6
g(xr) et lG(g(x)) = Dup, et sinon lG(x) = Creat
.
La figure 4.2 illustre la réconciliation de l'arbre des
protéines de la figure 4.1 (à considérer comme
non-étiqueté) avec l'arbre de gènes de la figure 4.3, ce
dernier ayant été réconcilié avec l'arbre
d'espèces illustré à la figure 4.4. Sur la figure 4.1, on
peut noter que, d'une part les créations de protéines
correspondent uniquement aux noeuds placés sur les branches de l'arbre
de gènes et d'autre part il n'y a que
5. Un sous-arbre enraciné en un noeud x d'un arbre T
est complet si il contient toutes les feuilles descendantes de x dans T.
28
| 
