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, conn...
সংরক্ষণ করুন:
| প্রকাশিত: | URI:https://journals.openedition.org/msh, |
|---|---|
| প্রধান লেখক: | , , |
| বিন্যাস: | Article ou chapitre numérique |
| ভাষা: | Français |
| প্রকাশিত: |
Mathématiques et sciences humaines
2010
|
| বিষয়গুলি: | |
| অনলাইন ব্যবহার করুন: | Accès Université d'Orléans et IFPM Accès Université d'Orléans et IFPM |
| সংক্ষিপ্ত: | É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. |
|---|