article

Extension Operations on Sets of Leaf-Labeled Trees

Authors:

M. SteelAuthors Info & Claims

Advances in Applied Mathematics, Volume 16, Issue 4

Pages 425 - 453

https://doi.org/10.1006/aama.1995.1020

Published: 01 December 1995 Publication History

Abstract

A fundamental problem in classification is how to combine collections of trees having overlapping sets of leaves. The requirement that such a collection of trees is realized by at least one parent tree determines uniquely some additional subtrees not in the original collection. We analyze the ''rules'' that arise in this way by defining a closure operator for sets of trees. In particular we show that there exist rules of arbitrarily high order which cannot be reduced to repeated application of lower-order rules.

References

[1]

E. N. Adams, N-trees as nestings: Complexity, similarity and consensus, J. Classification 3 (1986), 299-317.

[2]

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. Comput. 10, No. 3 (1981), 405-421.

Digital Library

[3]

A. Amir and D. Keselman, Maximum agreement subtree in a set of evolutionary trees, in "Proceedings 35th IEEE FOCS, Sante Fe, 1994."

[4]

H.-J. Bandelt and A. W. M. Dress, Reconstructing the shape of a tree from observed dissimilarity data, Adv. in Appl. Math. 7 (1986), 309-343.

Digital Library

[5]

R. L. Cann, M. Stoneking, and A. C. Wilson, Mitochodrial DNA and human evolution. Nature 325 (1987), 31-36.

[6]

M. Constantinescu and D. Sankoff, An efficient algorithm for supertrees, J. Classification 12 (1995), 101-112.

[7]

M. C. H. Dekker, "Reconstruction Methods for Derivation Trees," Masters thesis, University of Amsterdam, 1986.

[8]

A. W. M. Dress and M. A. Steel, Convex tree realizations of partitions, Appl. Math. Lett. 5, No. 3 (1992), 3-6.

[9]

N. Eldredge and J. Cracraft, "Phylogenetic Patterns and the Evolutionary Process," Columbia University Press, New York, 1980.

[10]

S. K. Kannan and T. J. Warnow, Inferring evolutionary history from DNA sequences, SIAM J. Compul. 23, No. 4 (1994), 713-737.

Digital Library

[11]

D. R. Maddison, African origin of human mitochondrial DNA reexamined, Syst. Zool. 40, No. 3 (1991), 355-393.

[12]

M. P. Ng and N. C. Wormald, Reconstruction of rooted trees from subtrees, Discrete Appl. Math., in press.

[13]

M. A. Steel, "Distributions on Bicoloured Evolutionary Trees," Ph.D. thesis, Massey University, Palmerston North, New Zealand, 1989.

[14]

M. A. Steel, The complexity of reconstructing trees from qualitative characters and subtrees, J. Classification 9 (1992), 91-116.

[15]

M. A. Steel, Decompositions of leaf-coloured binary trees, Adv. in Appl. Math. 14 (1993), 1-24.

[16]

W. Vach, Preserving consensus hierarchies, J. Classification 11 (1994), 59-77.

[17]

T. J. Warnow, "Combinatorial Algorithms for Constructing Phylogenetic Trees," Ph.D. thesis, University of California, Berkeley, CA, 1991.

[18]

T. J. Warnow, Tree compatibility and inferring evolutionary history, J. Algorithms 16 (1994), 388-407.

Digital Library

[19]

D. J. A. Welsh, "Matroid Theory," Academic Press, London, 1976.

[20]

M. Wilkinson, Common cladistic information and its consensus representation: Reduced Adams and reduced cladistic consensus trees and profiles, Syst. Biol. 43, No. 3 (1994), 343-368.

Cited By

Korchmaros ASchaller DHellmuth MStadler P(2023)Quasi-best match graphsDiscrete Applied Mathematics10.1016/j.dam.2023.01.015331:C(104-125)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.01.015
Hirai HIwamasa Y(2022)Reconstructing Phylogenetic Trees from Multipartite Quartet SystemsAlgorithmica10.1007/s00453-022-00945-984:7(1875-1896)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00453-022-00945-9
Schaller DGeiß MHellmuth MStadler P(2021)Best Match Graphs with Binary TreesAlgorithms for Computational Biology10.1007/978-3-030-74432-8_6(82-93)Online publication date: 7-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-74432-8_6
Show More Cited By

Index Terms

Extension Operations on Sets of Leaf-Labeled Trees
1. Applied computing
  1. Life and medical sciences
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

On Graph Powers for Leaf-Labeled Trees

We extend the well-studied concept of a graph power to that of a k-leaf powerG of a tree T: G is formed by creating a node for each leaf in the tree and an edge between a pair of nodes if and only if the associated leaves are connected by a path of ...
Frequent subsplit representation of leaf-labelled trees
EvoBIO'08: Proceedings of the 6th European conference on Evolutionary computation, machine learning and data mining in bioinformatics

In this paper we propose an innovative method of representing common knowledge in leaf-labelled trees as a set of frequent subsplits, together with its interpretation. Our technique is suitable for trees built on the same leafset as well as for trees ...
On Graph Powers for Leaf-Labeled Trees
SWAT '00: Proceedings of the 7th Scandinavian Workshop on Algorithm Theory

We extend the well-studied concept of a graph power to that of a k-leaf power G of a tree T: G is formed by creating a node for each leaf in the tree and an edge between a pair of nodes if and only if the associated leaves are connected by a path of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Advances in Applied Mathematics

Advances in Applied Mathematics Volume 16, Issue 4

Dec. 1995

133 pages

ISSN:0196-8858

Editor:
Gian-Carlo Rota
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Copyright © Academic Press © 1995.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 December 1995

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Korchmaros ASchaller DHellmuth MStadler P(2023)Quasi-best match graphsDiscrete Applied Mathematics10.1016/j.dam.2023.01.015331:C(104-125)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1016/j.dam.2023.01.015
Hirai HIwamasa Y(2022)Reconstructing Phylogenetic Trees from Multipartite Quartet SystemsAlgorithmica10.1007/s00453-022-00945-984:7(1875-1896)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00453-022-00945-9
Schaller DGeiß MHellmuth MStadler P(2021)Best Match Graphs with Binary TreesAlgorithms for Computational Biology10.1007/978-3-030-74432-8_6(82-93)Online publication date: 7-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-74432-8_6
Bodirsky MJonsson PPham T(2017)The Complexity of Phylogeny Constraint Satisfaction ProblemsACM Transactions on Computational Logic10.1145/310590718:3(1-42)Online publication date: 2-Aug-2017
https://dl.acm.org/doi/10.1145/3105907
Baldisserri ARubei E(2017)A characterization of dissimilarity families of treesDiscrete Applied Mathematics10.1016/j.dam.2016.12.007220:C(35-45)Online publication date: 31-Mar-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.12.007
Alon NSnir SYuster RChekuri C(2014)On the compatibility of quartet treesProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634114(535-545)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634114
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
Bonet MLinz SSt. John K(2012)The Complexity of Finding Multiple Solutions to Betweenness and Quartet CompatibilityIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2011.1089:1(273-285)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1109/TCBB.2011.108
Shutters BVakati SFernández-Baca D(2012)Improved lower bounds on the compatibility of quartets, triplets, and multi-state charactersProceedings of the 12th international conference on Algorithms in Bioinformatics10.1007/978-3-642-33122-0_15(190-200)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33122-0_15
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
Show More Cited By

View Options

View options

Get Access

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents