Navigation – Plan du site

AccueilNuméros190About the largest subtree common ...

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

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

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 28 octobre 2021. URL : http://journals.openedition.org/msh/11751 ; DOI : https://doi.org/10.4000/msh.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
  • OpenEdition Journals
Search OpenEdition Search

You will be redirected to OpenEdition Search