About the largest subtree common to several X-trees

Mathématiques et sciences humaines. Mathematics and social sciences

Tichit, Laurent¹  Garreta, Henri¹  Guénoche, Alain¹ 

关键词: MAST;    MCT;    partial common tree;    phylogenetic tree;    X-tree;   

DOI  :  10.4000/msh.11751

学科分类：数学（综合）

来源: College de France * Ecole des Hautes Etudes en Sciences Sociales (E H E S S)

【 摘 要 】

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.

【 授权许可】

Unknown