Supertrees by Flipping

作者: D. Chen , O. Eulenstein , David Fernández-Baca , M. Sanderson

DOI: 10.1007/3-540-45655-4_42

关键词: Search treeTree (graph theory)Computer scienceApproximation algorithmBipartite graphSupertreeCombinatoricsDiscrete mathematicsPhylogenetic 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.

参考文章(26)
Assaf Natanzon, Ron Shamir, Roded Sharan, Complexity Classification of Some Edge Modification Problems workshop on graph theoretic concepts in computer science. ,vol. 113, pp. 65- 77 ,(1999) , 10.1016/S0166-218X(00)00391-7
David Bryant, John Tsang, Ming Li, Paul Kearney, Computing the quartet distance between evolutionary trees symposium on discrete algorithms. pp. 285- 286 ,(2000) , 10.5555/338219.338264
Andy Purvis, A Modification to Baum and Ragan's Method for Combining Phylogenetic Trees Systematic Biology. ,vol. 44, pp. 251- 255 ,(1995) , 10.1093/SYSBIO/44.2.251
John Tsang, Ming Li, Paul Kearney, Tao Jiang, Recovering branches on the tree of life: an approximation algorithm symposium on discrete algorithms. pp. 537- 546 ,(1999)
G.F. Estabrook, C.S. Johnson, F.R. Mc Morris, An idealized concept of the true cladistic character Bellman Prize in Mathematical Biosciences. ,vol. 23, pp. 263- 272 ,(1975) , 10.1016/0025-5564(75)90040-1
James S. Farris, On Comparing the Shapes of Taxonomic Trees Systematic Biology. ,vol. 22, pp. 50- 54 ,(1973) , 10.2307/2412378
Mihalis Yannakakis, Computing the Minimum Fill-in is NP^Complete Siam Journal on Algebraic and Discrete Methods. ,vol. 2, pp. 77- 79 ,(1981) , 10.1137/0602010
Charles Semple, Mike Steel, A supertree method for rooted trees Discrete Applied Mathematics. ,vol. 105, pp. 147- 158 ,(2000) , 10.1016/S0166-218X(00)00202-X