About the largest subtree common to several X-trees

Etant donnes plusieursX-arbres, ou arbres phylogenetiques, sur le meme ensembleX, nous cherchons a construire un plus grand sous-ensembleY⊂Xtel que les arbres partiels induits surYsoient identiques d’un point de vue topologique, c’est-a-dire independamment des longueurs des aretes. Ce probleme, connu sous le nom de MAST (Maximum Agreement SubTree), est NP-Difficile, dans le cas general, des que le nombre deX-arbres est superieur a 2. Nous presentons un algorithme approche qui construit un arbre partiel commun maximal. Il est facilement programmable et suffisamment efficace sur une centaine deX-arbres connectant une centaine d’elements pour evaluer la taille moyenne d’un sous-arbre commun a desX-arbres independants. La distribution observee permet d’estimer la taille critique d’un sous-arbre commun et de mesurer la congruence de plusieurs arbres evolutifs.