Résumés
É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.
Given severalX-trees or unrooted phylogenetic trees on the same set of taxaX, we look for a largest subsetY⊂Xsuch 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
Texte intégral
Haut de page
Pour citer cet article
Référence papier
Alain Guénoche, Henri Garreta et Laurent Tichit, « About the largest subtree common to several X-trees », Mathématiques et sciences humaines, 190 | 2010, 115-124.
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 19 mars 2024. URL : http://journals.openedition.org/msh/11751 ; DOI : https://doi.org/10.4000/msh.11751
Haut de page
Auteurs
Institut de mathématiques de Luminy, UMR 6206, 163, avenue de Luminy, 13009 Marseille, guenoche@iml;univ-mrs.fr
Articles du même auteur
-
About consensus in free sorting task
-
Pavel A. Pevzner, « Bio-informatique moléculaire : une approche algorithmique », trad. Delphine Hachez, Springer, Coll. Iris, 2006
-
Kemeny winners and hard tournaments
-
Tree adjustments for partial distances
-
Partitions optimizing different criteria: evaluation and comparison
Laboratoire d’informatique fondamentale, 163, avenue de Luminy, Case 901, 13009 Marseille, garreta@univmed.fr
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
Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.
Haut de page