16 octobre 2010
Ce document est lié à :
info:eu-repo/semantics/reference/issn/0987-6936
Ce document est lié à :
info:eu-repo/semantics/reference/issn/1950-6821
All rights reserved , info:eu-repo/semantics/openAccess
Alain Guénoche et al., « About the largest subtree common to several X-trees », Mathématiques et sciences humaines, ID : 10.4000/msh.11751
Étant donnés plusieursX-arbres, ou arbres phylogénétiques, sur le même ensembleX, nous cherchons à construire un plus grand sous-ensembleY⊂Xtel que les arbres partiels induits surYsoient identiques d’un point de vue topologique, c’est-à-dire indépendamment des longueurs des arêtes. Ce problème, connu sous le nom de MAST (Maximum Agreement SubTree), est NP-Difficile, dans le cas général, dès que le nombre deX-arbres est supérieur à 2. Nous présentons un algorithme approché qui construit un arbre partiel commun maximal. Il est facilement programmable et suffisamment efficace sur une centaine deX-arbres connectant une centaine d’éléments pour évaluer la taille moyenne d’un sous-arbre commun à desX-arbres indépendants. La distribution observée permet d’estimer la taille critique d’un sous-arbre commun et de mesurer la congruence de plusieurs arbres évolutifs.