.Supposant connues toutes les distances entre des objets pris deux à deux dans un ensemble fini, l'algorithme décrit ici classe ces objets dans un ordre de similarité qui rapproche les objets qui se ressemblent le plus. Ceci peut constituer une étape d'une analyse typologique.
Il fournit également l'ordre de construction du classement. Dans le cas où les objets sont des séquences génomiques ou protéiniques, celui-ci qui pourrait - par exemple - être utile dans une approche comme celle employée par CLUSTAL pour effectuer un alignement multiple progressif par paires, sans avoir à élaborer d'arbre guide.
Le programme en C++ fourni à la fin de cette page est volontairement simpliste et privilégie la lisibilité au détriment de l'efficacité. Il N'EST PAS optimisé informatiquement en termes de vitesse ni d'emploi de la mémoire.
On part de la matrice de distances Dij entre les N objets. Comme Dii = 0 et Dji = Dij, seules sont fournies les N(N-1)/2 distances Dij pour j = 1, ..., N et i = j+1, ..., N.
On classe d'abord toutes les distances dans l'ordre croissant et on range le résultat dans deux vecteurs ELM_1 et ELM_2 contenant les deux objets qui sont les éléments de la ième paire pour i=1 à imax=N(N-1)/2 et on leur associe un tableau PRIS de booléens pour noter si chaque paire a été prise en compte au cours de l'algorithme suivant. Ce tableau est initialisé à FAUX.
Rang |
Élément 1 |
Élément 2 |
Pris |
1 |
I1 |
J1 |
FAUX |
2 |
I2 |
J2 |
FAUX |
... |
... |
... |
FAUX |
imax=N(N-1)/2 |
Iimax |
Jimax |
FAUX |
Tableau des paires
On va ensuite dérouler un processus qui va attribuer à chaque objet un numéro d'ordre rangé dans un tableau ORDRE en agrégeant les objets les plus voisins par coalescence à droite ou à gauche en exploitant le tableau des paires.
La première paire placée est la première du tableau des paires, qui contient les plus proches voisins dans l'absolu. Le placement droite / gauche de ces deux éléments est indifférent (résultat final déterminé à une symétrie près sans signification). Le numéro d'ordre (ne pas confondre avec le rang de la paire) 0 est attribué à l'objet I1 et le numéro d'ordre 1 à J1. Ce numéro d'ordre est rangé dans le tableau ORDRE des numéros d'ordre des objets.
objet s |
N° = ORDRE[s] |
1 |
|
... |
|
I1 |
0 |
... |
|
J1 |
1 |
... |
|
N |
|
Tableau des numéros d'ordre
En même temps, on passe PRIS[1] à VRAI (pour marquer que la première paire est prise), on note que l'élément le plus à gauche du classement est GAUCHE=I1 et que le plus à droite est DROITE=J1 et on note que le plus petit numéro d'ordre attribué est ORDREMIN=0 et le plus grand ORDREMAX=1. ORDREMIN correspond à la position la plus à gauche et ORDREMAX à la plus à droite.
L'initialisation a placé 2 objets parmi N, l'étape suivante est donc une boucle répétée autant de fois qu'il reste d'objets, c'est-à-dire pour SBOUCLE=3 à N.
A chaque passage dans la boucle, en partant du haut du tableau des paires, on cherche dans celui-ci la première paire P non prise qui contient GAUCHE ou DROITE, on la note comme prise (PRIS[P]=VRAI) et, selon le cas,
si ELM_1[P]=GAUCHE, alors on note son autre élément ELM_2[P] comme NOUVEAU_GAUCHE, ou si ELM_2[P]=GAUCHE, alors on note son autre élément ELM_1[P] comme NOUVEAU_GAUCHE, puis on marque comme prises toutes les autres paires qui contiennent GAUCHE ainsi que toutes les paires qui sont formées de 2 objets déjà utilisés, puis on met NOUVEAU_GAUCHE dans GAUCHE et enfin on décrémente ORDREMIN d'une unité (ORDREMIN=ORDREMIN-1) avant de l'attribuer à l'objet GAUCHE : ORDRE[GAUCHE]=ORDREMIN;
si ELM_1[P]=DROITE, alors on note son autre élément ELM_2[P] comme NOUVEAU_DROITE, ou si ELM_2[P]=DROITE, alors on note son autre élément ELM_1[P] comme NOUVEAU_DROITE, puis on marque comme prises toutes les autres paires qui contiennent DROITE ainsi que toutes les paires qui sont formées de 2 objets déjà utilisés, puis on met NOUVEAU_ DROITE dans DROITE et enfin on incrémente ORDREMAX d'une unité (ORDREMAX=ORDREMAX+1) avant de l'attribuer à l'objet DROITE : ORDRE[DROITE]=ORDREMAX.
Lorsque la boucle est terminée, tous les objets ont reçu un numéro d'ordre qui va de ORDREMIN (négatif ou nul) à ORDREMAX (supérieur ou égal à 1). Pour les numéroter de 1 à N, il suffit d'ajouter 1-ORDREMIN à tous les numéros d'ordre: ORDRE[S]=ORDRE[S]+1-ORDREMIN.
Pour les ranger dans un tableau CLASSEMENT dans l'ordre, il suffit de faire pour tous les S:
CLASSEMENT[ORDRE[S]] = S.
CLASSEMENT contient le résultat cherché.
Comme dit plus haut, sans optimisation, le programme joint a une valeur illustrative. A noter: l'algorithme n'effectue pas de calculs, seulement des tris, tests logiques et affectations de valeurs.
Liste c++ au format pdf et au format texte (cpp).
Jeu imaginaire de données de distances pour 5 objets, fichier distance.txt à placer dans le même dossier que l'exécutable.
Sortie du programme pour ce jeu de distances sous Windows et Linux :
.
Le programme produit dans son dossier un fichier Resultat.txt et un fichier qui trace l'élaboration du classement : Range.log