CHAPITRE 4. MÉTHODOLOGIE ET
IMPLÉMENTATION
4.2.4.1 Définition du regroupement
Le regroupement appelé en anglais clustering [21] est
une méthode de classification non supervisée, l'objectif
étant de découvrir les regroupements naturels d'un ensemble de
motifs, de points ou d'objets quelconques, ou dans notre cas des
protéines. En pratique, la plupart des scientifiques décrivent un
groupe en tenant compte de son homogénéité interne et de
son hétérogénéité externe. En d'autres
termes, les motifs au sein du même groupe devraient être
similaires, tandis que les motifs dans différents groupes ne le
devraient pas. Le regroupement est utilisé pour grouper les
séquences de protéines en sous-familles en fonction de leurs
similarités, ce qui fournira par ailleurs des indices importants sur les
caractéristiques générales des familles de
protéines. Cette approche de regroupement est également utile
pour inférer la fonction biologique des protéines en
déterminant leur appartenance à des familles de protéines
bien connues et annotées.
4.2.4.2 Problème de regroupement dans le cas
présent
Le modèle de regroupement que nous proposons s'appuie
sur le modèle d'évolu-tion de protéines
présenté dans la section précédente. Nous
construisons un ensemble de groupes de protéines, tel que pour tout
groupe C, le plus proche ancêtre commun de deux protéines du
groupe ne doit jamais correspondre à une création dans l'arbre
des protéines étiqueté.
La figure 4.6 illustre un exemple d'arbre de protéines
étiqueté dans lequel le noeud 6 est une création de
protéines qui conduit à deux protéines (1 et 2)
appartenant au même gène A. À l'inverse, la création
au niveau du noeud 9 va produire des protéines qui appartiennent dans un
premier temps au même gène ancestral, mais par la suite de
l'évolution, à des gènes différents à cause
de la spéciation et de la duplication qui ont mené à trois
gènes différents. Les protéines 1, 2, 4 appartiennent donc
au même gène A, la protéine 3 au gène B, et les
protéines 5, 11 au gène C.
L'ensemble des groupes de taille maximum en termes d'inclusion
que l'on voudrait obtenir est {(1, 3, 11), (2, 3, 11), (4, 5)} dans lequel
chaque groupe contient au plus une protéine par gène.
Cependant, dans notre cas, l'arbre des protéines et son
étiquetage ne sont pas connus et nous cherchons à les
reconstruire, en même temps que l'arbre des gènes. Par
conséquent, nous simplifions le problème de regroupement des
protéines au problème qui consiste à former un
ensemble de groupes dans lesquels chaque groupe contient une seule
protéine par gène, tout en permettant qu'une protéine
puisse se retrouver dans plusieurs groupes. Ceci nous amène
donc à définir une méthode de regroupement avec
chevauchement 8 pour créer des groupes
8. le regroupement avec chevauchement est une technique de
regroupement qui permet qu'un
34
| 
