作者: D. Chen , O. Eulenstein , David Fernández-Baca , M. Sanderson
关键词: Search tree 、 Tree (graph theory) 、 Computer science 、 Approximation algorithm 、 Bipartite graph 、 Supertree 、 Combinatorics 、 Discrete mathematics 、 Phylogenetic tree
摘要: The input to a supertree problem is collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal construct single tree retains as much possible information input. This task complicated by inconsistencies due errors. We consider case where source are rooted and represented clusters they exhibit. find minimum number flips needed resolve all inconsistencies, each flip moves taxon into or out cluster. prove NP-complete, but show it fixed-parameter tractable give an approximation algorithm for special case.