Navigation – Plan du site

About the largest subtree common to several X-trees

Sur le plus grand sous-arbre commun à plusieurs X-arbres
Alain Guénoche, Henri Garreta et Laurent Tichit
p. 115-124

Résumés

Sur le plus grand sous-arbre commun à plusieurs X-arbres

Étant donnés plusieursX-arbres, ou arbres phylogénétiques, sur le même ensembleX, nous cherchons à construire un plus grand sous-ensembleYXtel 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.

Given severalX-trees or unrooted phylogenetic trees on the same set of taxaX, we look for a largest subsetYXsuch that al l the partial trees reduced byYare topologically identical. This common subtree is called a MAST for Maximum Agreement SubTree. The problem has polynomial complexity when there are only two trees but generally it is NP-hard for more than two. We introduce a polynomial approximation algorithm for the multiple case, which is easy to implement, very efficient and which produces a maximal common subtree. It begins with the computation of an upper bound for its size and designates elements inXthat cannot belong to a common subtree of a given size. Simulations on random and real data have shown that this heuristic often provides an optimal solution as soon as the number of trees is larger than 5. Then, we develop a statistical study to evaluate the average size of a MAST corresponding to independent trees. The computed distribution allows to estimate the critical size of a MAST to reveal some congruence between trees.

Haut de page

Pour citer cet article

Référence électronique

Alain Guénoche, Henri Garreta et Laurent Tichit, « About the largest subtree common to several X-trees », Mathématiques et sciences humaines [En ligne], 190 | Eté 2010, mis en ligne le 16 octobre 2010, consulté le 30 avril 2017. URL : http://msh.revues.org/11751

Haut de page

Auteurs

Alain Guénoche

Institut de mathématiques de Luminy, UMR 6206, 163, avenue de Luminy, 13009 Marseille, guenoche@iml;univ-mrs.fr

Articles du même auteur

Henri Garreta

Laboratoire d’informatique fondamentale, 163, avenue de Luminy, Case 901, 13009 Marseille, garreta@univmed.fr

Laurent Tichit

Institut de mathématiques de Luminy, UMR 6206, 163, avenue de Luminy, 13009 Marseille, tichit@iml.univ-mrs.fr

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page