CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
4.2.7 Étape 7 : Construction de l'arbre de
protéines et de l'arbre des gènes
Disposant d'une forêt de l arbres pour l
groupes telle que l'un des arbres est considéré comme
l'arbre de référence (celui contenant une protéine pour
chacun des gènes), l'objectif de cette étape est de fusionner les
arbres en un seul arbre.
Les principales phases de l'algorithme de cette
étape sont :
1. Définir l'arbre de gènes G comme
égal à l'arbre de référence (contenant une
protéine pour chacun des gènes)
2. Initialiser le super-arbre de protéines P
comme égal à l'arbre de référence
3. De façon itérative jusqu'à fusionner
tous les arbres
~ Choisir l'arbre Tk avec k E [1,
l] tel que .C(Tk) n .C(P) est maximal.
~ Construire l'arbre induit T =
Tk|L(Tk)\L(P
~ Calculer le noeud de P, x =
lcaP{P1 E .C(P) | ?P2 E
(.C(Tk)\.C(P)),g(p1) =
g(p2)}
La figure 4.10 montre un exemple d'application de l'algorithme
glouton de concaténation d'une forêt d'arbres. L'arbre de
référence étant l'arbre ayant pour racine
étiqueté par 1.
| 
