| Titre | About the largest subtree common to several X-trees | |
|---|---|---|
| Auteur | Alain Guénoche, Henri Garreta, Laurent Tichit | |
 |
Revue | Mathématiques et sciences humaines |
| Numéro | no 190, été 2010 Mathématiques discrètes : théories et usages. Numéro en hommage à Bruno Leclerc | |
| Page | 115-124 | |
| Résumé |
Étant donnés plusieurs X-arbres, ou arbres phylogénétiques, sur le même ensemble X, nous cherchons à construire un plus grand sous-ensemble Y⊂X tel que les arbres partiels induits sur Y soient 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 de X-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 de X-arbres connectant une centaine d'éléments pour évaluer la taille moyenne d'un sous-arbre commun à des X-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. Source : Éditeur (via OpenEdition Journals) |
|
| Résumé anglais |
Given several X-trees or unrooted phylogenetic trees on the same set of taxa X, we look for a largest subset Y⊂X such that al l the partial trees reduced by Y are 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 in X that 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. Source : Éditeur (via OpenEdition Journals) |
|
| Article en ligne | http://msh.revues.org/11751 |
