article

Minimum-Flip Supertrees: Complexity and Algorithms

Authors:

Oliver Eulenstein,

David Fernandez-Baca,

Michael SandersonAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 3, Issue 2

Pages 165 - 173

https://doi.org/10.1109/TCBB.2006.26

Published: 01 April 2006 Publication History

Abstract

The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is {\cal NP}{\hbox{-}}{\rm complete}, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

References

[1]

{1} D.H. Huson, S.M. Nettles, and T.J. Warnow, "Disk-Covering, a Fast-Converging Method for Phylogenetic Tree Reconstruction," J. Computational Biology, vol. 6, nos. 3-4, pp. 369-386, 1999.]]

[2]

{2} Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, O.R.P. Bininda-Emonds, ed. Kluwer Academic, 2004.]]

[3]

{3} A.D. Gordon, "Consensus Supertrees: The Synthesis of Rooted Trees Containing Overlapping Sets of Labelled Leaves," J. Classification, vol. 9, pp. 335-348, 1986.]]

[4]

{4} M.A. Steel, "The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees," J. Classification, vol. 9, pp. 91-116, 1992.]]

[5]

{5} M.J. Sanderson, A. Purvis, and C. Henze, "Phylogenetic Supertrees: Assembling the Trees of Life," Trends Ecological Evolution, vol. 13, pp. 105-109, 1998.]]

[6]

{6} C. Semple and M.A. Steel, "A Supertree Method for Rooted Trees," Discrete Applied Math., vol. 105, pp. 147-158, 2000.]]

Digital Library

[7]

{7} M.A. Steel, A.W.M. Dress, and S. Böcker, "Simple but Fundamental Limitations on Supertree and Consensus Tree Methods," Systematic Biology, vol. 49, pp. 363-368, 2000.]]

[8]

{8} M.J. Donoghue, "Phylogenies and the Analysis of Evolutionary Sequences, with Examples from Seed Plants," Evolution, vol. 43, pp. 1137-1156, 1989.]]

[9]

{9} A. Ortolani, "Spots, Stripes, Tail Tips and Dark Eyes: Predicting the Function of Carnivore Colour Patterns Using the Comparative Method," Biological J. Linnean Soc., vol. 67, pp. 433-476, 1999.]]

[10]

{10} A. Purvis, "A Modification to Baum and Ragan's Method for Combining Phylogenetic Trees," Systematic Biology, vol. 44, pp. 251-255, 1995.]]

[11]

{11} O.R.P. Bininda-Emonds, J.L. Gittleman, and A. Purvis, "Building Large Trees by Combining Phylogenetic Information: A Complete Phylogeny of the Extant Carnivora (Mammalia)," Biological Rev., vol. 74, pp. 143-175, 1999.]]

[12]

{12} M.F. Wojciechowski, M.J. Sanderson, K.P. Steele, and A. Liston, "Molecular Phylogeny of the 'Temperate Herbaceous Tribes' of Papilionoid Legumes: A Supertree Approach," Advances in Legume Systematics, P. Herendeen and A. Bruneau, eds., vol. 9, pp. 277- 298, 2000.]]

[13]

{13} F.G.R. Liu, M.M. Miyamoto, N.P. Freire, P.Q. Ong, M.R. Tennant, T.S. Young, and K.F. Gugel, "Molecular and Morphological Supertrees for Eutherian (Placental) Mammals," Science, vol. 291, pp. 1786-1789, 2001.]]

[14]

{14} T.J. Davies, T.G. Barraclough, M.W. Chase, P.S. Soltis, D.E. Soltis, and V. Savolainen, "Darwin's Abominable Mystery: Insights from a Supertree of the Angiosperms," Proc. Nat'l Academy Sciences USA, vol. 101, pp. 1904-1909, 2004.]]

[15]

{15} E. Grotkopp, M. Rejmanek, M.J. Sanderson, and T.L. Rost, "Evolution of Genome Size in Pines (Pinus) and Its Life-History Correlates: Supertree Analyses," Evolution, pp. 1705-1729, 2004.]]

[16]

{16} D.R. Brooks, "Hennig's Parasitological Method: A Proposed Solution," Systems Zoology, vol. 30, pp. 325-331, 1981.]]

[17]

{17} B.R. Baum, "Combining Trees as a Way of Combining Data Sets for Phylogenetic Inference, and the Desirability of Combining Gene Trees," Taxon, vol. 41, pp. 3-10, 1992.]]

[18]

{18} M.A. Ragan, "Phylogenetic Inference Based on Matrix Representation of Trees," Molecular Phylogenetics and Evolution, vol. 1, pp. 53-58, 1992.]]

[19]

{19} O. Eulenstein, D. Chen, J.G. Burleigh, D. Fernández-Baca, and M.J. Sanderson, "Performance of Flip Supertree Construction with a Heuristic Algorithm," Systematic Biology, vol. 53, pp. 299-308, 2003.]]

[20]

{20} S. Kannan, T. Warnow, and S. Yooseph, "Computing the Local Consensus of Trees," Proc. Symp. Discrete Algorithms, pp. 68-77, 1995.]]

Digital Library

[21]

{21} P. Kearney, M. Li, J. Tsang, and T. Jiang, "Recovering Branches on the Tree of Life: An Approximation Algorithm," Proc. Symp. Discrete Algorithms, pp. 537-546, 1999.]]

Digital Library

[22]

{22} D. Bryant, J. Tsang, P.E. Kearney, and M. Li, "Computing the Quartet Distance between Evolutionary Trees," Proc. Symp. Discrete Algorithms, pp. 285-286, 2000.]]

Digital Library

[23]

{23} A.V. Aho, Y. Sagiv, T.G. Szymanski, and J.D. Ullman, "Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions," SIAM J. Computing, vol. 10, no. 3, pp. 405-421, 1981.]]

Digital Library

[24]

{24} M.R. Henzinger, V. King, and T. Warnow, "Constructing a Tree From Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology," Algorithmica, vol. 24, pp. 1-13, 1999.]]

[25]

{25} R.D.M. Page, "Modified Mincut Supertrees," Proc. Int'l Workshop Algorithms in Bioinformatics (WABI), D. Gusfield and R. Guigó, eds., pp. 300-315, Sept. 2002.]]

Digital Library

[26]

{26} R.L. Graham and L.R. Foulds, "Unlikelihood that Minimal Phylogenies for a Realistic Biological Study Can Be Constructed in Reasonable Computation Time," Math. Bioscience, vol. 60, pp. 133-142, 1982.]]

[27]

{27} J. Felsenstein, "PHYLIP," http://evolution.genetics.washington. edu/phylip.html, 2006.]]

[28]

{28} I. Pe'er, R. Shamir, and R. Sharan, "Incomplete Directed Perfect Phylogeny," Combinatorial Pattern Matching, R. Giancarlo and D. Sankoff, eds., Springer-Verlag, pp. 143-153, 2000.]]

Digital Library

[29]

{29} G.F. Estabrook, C. Johnson, and F.R. McMorris, "An Idealized Concept of the True Cladistic Character?" Math. Bioscience, vol. 23, pp. 263-272, 1975.]]

[30]

{30} D. Gusfield, Algorithms on Strings, Trees, and Sequences. New York: Cambridge Univ. Press, 1997.]]

Digital Library

[31]

{31} J.S. Farris, "On Comparing the Shapes of Taxonomic Trees," Systematic Zoology, vol. 22, pp. 50-54, 1976.]]

[32]

{32} D.L. Swofford, G.J. Olsen, P.J. Waddel, and D.M. Hillis, "Phylogenetic Inference," Molecular Systematics, D.M. Hillis, C. Moritz, and B.K. Mable, eds., pp. 407-509. Sunderland, Mass.: Sinauer Assoc., 1996.]]

[33]

{33} M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman, 1979.]]

Digital Library

[34]

{34} M. Yannakakis, "Computing the Minimum Fill-In Is NP-Complete," SIAM J. Algebraic and Discrete Methods, vol. 2, no. 1, pp. 77- 79, 1981.]]

Digital Library

[35]

{35} M. Yannakakis, "Node-Deletion Problems on Bipartite Graphs," SIAM J. Computing, vol. 10, pp. 310-326, 1981.]]

Digital Library

[36]

{36} A. Natanzon, R. Shamir, and R. Sharan, "Complexity Classification of Some Edge Modification Problems," Discrete Applied Math., vol. 113, no. 1, pp. 109-128, 2001.]]

[37]

{37} R.G. Downey and M.R. Fellows, Parameterized Complexity. Springer, 1997.]]

[38]

{38} L. Cai, "Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties," Information Processing Letters, vol. 58, pp. 171-176, 1996.]]

Digital Library

[39]

{39} D. Gusfield, "Efficient Algorithms for Inferring Evolutionary History," Networks, vol. 21, pp. 19-28, 1992.]]

[40]

{40} J.G. Burleigh, D. Chen, O. Eulenstein, D. Fernández-Baca, and M.J. Sanderson, "Minimum Flip Supertrees," Phylogenetic Supertrees: The Book, Kluwer, to appear.]]

[41]

{41} D. Chen, L. Diao, O. Eulenstein, D. Fernández-Baca, and M.J. Sanderson, "Flipping: A Supertree Construction Method," Bioconsensus, DIMACS: Series in Discrete Math. and Theoretic Computer Science, vol. 61, pp. 135-160, Providence, R.I.: Am. Math. Soc., 2003.]]

[42]

{42} D. Chen, O. Eulenstein, and D. Fernández-Baca, "Rainbow: A Toolbox for Phylogenetic Supertree Construction and Analysis," Bioinformatics Advance Access, 2004.]]

Digital Library

Cited By

Bhattacharyya SMukherjee J(2015)COSPEDTreeIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2014.236677812:3(590-603)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TCBB.2014.2366778
Bhattacharyya SMukhopadhyay JBaldi PWang W(2014)Couplet supertree by equivalence partitioning of taxa set and DAG formationProceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/2649387.2649388(259-268)Online publication date: 20-Sep-2014
https://dl.acm.org/doi/10.1145/2649387.2649388
Neves DWarnow TSobral JPingali KOssowski SLecca P(2012)Parallelizing SuperFineProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2231992(1361-1367)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2231992
Show More Cited By

Index Terms

Minimum-Flip Supertrees: Complexity and Algorithms

Recommendations

Reconstructing Phylogenetic Trees from Multipartite Quartet Systems
Abstract
A phylogenetic tree is a graphical representation of an evolutionary history of taxa in which the leaves correspond to the taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a ...
Algorithms for knowledge-enhanced supertrees
ISBRA'12: Proceedings of the 8th international conference on Bioinformatics Research and Applications

Supertree algorithms combine smaller phylogenetic trees into a single, comprehensive phylogeny, or supertree. Most supertree problems are NP-hard, and often heuristics identify supertrees with anomalous or unwanted relationships. We introduce knowledge-...
Exact ILP solutions for phylogenetic minimum flip problems
BCB '10: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology

In computational phylogenetics, the problem of constructing a consensus tree or supertree of a given set of rooted input trees can be formalized in different ways. We consider the Minimum Flip Consensus Tree and Minimum Flip Supertree problem, where ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 3, Issue 2

April 2006

95 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 April 2006

Published in TCBB Volume 3, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
342
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhattacharyya SMukherjee J(2015)COSPEDTreeIEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)10.1109/TCBB.2014.236677812:3(590-603)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TCBB.2014.2366778
Bhattacharyya SMukhopadhyay JBaldi PWang W(2014)Couplet supertree by equivalence partitioning of taxa set and DAG formationProceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics10.1145/2649387.2649388(259-268)Online publication date: 20-Sep-2014
https://dl.acm.org/doi/10.1145/2649387.2649388
Neves DWarnow TSobral JPingali KOssowski SLecca P(2012)Parallelizing SuperFineProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2231992(1361-1367)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2231992
Böcker SBui QTruss A(2012)Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus TreesACM Transactions on Algorithms10.1145/2071379.20713868:1(1-17)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1145/2071379.2071386
Brinkmeyer MGriebel TBöcker S(2011)FlipCut supertreesProceedings of the 17th annual international conference on Computing and combinatorics10.5555/2033094.2033098(37-48)Online publication date: 14-Aug-2011
https://dl.acm.org/doi/10.5555/2033094.2033098
Liu EZhang ZWang WApte CGhosh JSmyth P(2011)Clustering with relative constraintsProceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2020408.2020564(947-955)Online publication date: 21-Aug-2011
https://dl.acm.org/doi/10.1145/2020408.2020564
Brinkmeyer MGriebel TBöcker S(2010)Polynomial supertree methods revisitedProceedings of the 5th IAPR international conference on Pattern recognition in bioinformatics10.5555/1887854.1887872(183-194)Online publication date: 22-Sep-2010
https://dl.acm.org/doi/10.5555/1887854.1887872
Chimani MRahmann SBöcker SZhang ABorodovsky MOzsoyoglu GMikler A(2010)Exact ILP solutions for phylogenetic minimum flip problemsProceedings of the First ACM International Conference on Bioinformatics and Computational Biology10.1145/1854776.1854800(147-153)Online publication date: 2-Aug-2010
https://dl.acm.org/doi/10.1145/1854776.1854800
Böcker SBui QTruss A(2008)An improved fixed-parameter algorithm for minimum-flip consensus treesProceedings of the 3rd international conference on Parameterized and exact computation10.5555/1789694.1789700(43-54)Online publication date: 14-May-2008
https://dl.acm.org/doi/10.5555/1789694.1789700

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents