About the largest subtree common to several X-trees

É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.

Vox Philosophiae vous recommande : - Mathématiques et sciences humaines