Access the full text.
Sign up today, get an introductory month for just $19.
D. Levy, R. Yoshida, L. Pachter (2006)
Beyond pairwise distances: neighbor-joining with phylogenetic diversity estimates.Molecular biology and evolution, 23 3
(1965)
Reconstruction of a Tree from the Distances Between Its Pendant Vertices,
P. Buneman (1971)
The Recovery of Trees from Measures of Dissimilarity
C. Bocci, Filip Cools (2008)
A tropical interpretation of m-dissimilarity mapsAppl. Math. Comput., 212
M. Steel (2005)
Phylogenetic diversity and the greedy algorithm.Systematic biology, 54 4
A Schrijver (1986)
Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics
L. Pachter, David Speyer (2003)
Reconstructing trees from subtree weightsAppl. Math. Lett., 17
J. Culberson, P. Rudnicki (1989)
A Fast Algorithm for Constructing Trees from Distance MatricesInf. Process. Lett., 30
Chikio Hayashi (1972)
Two dimensional quantification based on the measure of dissimilarity among three elementsAnnals of the Institute of Statistical Mathematics, 24
(2003)
Phylogenetics (Vol. 24), Oxford Lecture Series in Mathematics and Its Applications
S. Joly, G. Calvé (1995)
Three-way distancesJournal of Classification, 12
G. Soete (1983)
A least squares algorithm for fitting additive trees to proximity dataPsychometrika, 48
V. Chepoi, B. Fichet (2007)
A Note on Three-Way Dissimilarities and Their Relationship with Two-Way Dissimilarities
A. Dress, M. Steel (2007)
Phylogenetic Diversity Over an Abelian GroupAnnals of Combinatorics, 11
H. Williams (1989)
THEORY OF LINEAR AND INTEGER PROGRAMMING (Wiley-Interscience Series in Discrete Mathematics and Optimization)Bulletin of The London Mathematical Society, 21
M. Deza, I. Rosenberg (2000)
n-SemimetricsEur. J. Comb., 21
Elena Rubei (2007)
Sets of Double and Triple Weights of TreesAnnals of Combinatorics, 15
(2003)
Inferring Phylogenies, Sunderland, Massachusetts: Sinauer Associates
A. Gordon (1987)
A Review of Hierarchical Classification, 150
Matthijs Warrens (2010)
n-Way MetricsJournal of Classification, 27
Ye.A Smolenskii (1963)
A method for the linear recording of graphsUssr Computational Mathematics and Mathematical Physics, 2
AWM Dress, KT Huber, J Koolen, V Moulton, A Spillner (2011)
Basic Phylogenetic Combinatorics
W. Heiser, Mohammed Bennani (1997)
Triadic Distance Models: Axiomatization and Least Squares RepresentationJournal of mathematical psychology, 41 2
D. Faith (1992)
Conservation evaluation and phylogenetic diversityBiological Conservation, 61
H. Bandelt, A. Dress (1994)
An order theoretic framework for overlapping clusteringDiscret. Math., 136
H. Bandelt (1990)
Recognition of Tree MetricsSIAM J. Discret. Math., 3
J Felsenstein (2003)
Inferring Phylogenies
N. Grishin (1999)
A Novel Approach to Phylogeny Reconstruction from Protein SequencesJournal of Molecular Evolution, 48
A k-dissimilarity D on a finite set X, |X| ≥ k, is a map from the set of size k subsets of X to the real numbers. Such maps naturally arise from edgeweighted trees T with leaf-set X: Given a subset Y of X of size k, D(Y ) is defined to be the total length of the smallest subtree of T with leaf-set Y . In case k = 2, it is well-known that 2-dissimilarities arising in this way can be characterized by the so-called “4-point condition”. However, in case k > 2 Pachter and Speyer (2004) recently posed the following question: Given an arbitrary k-dissimilarity, how do we test whether this map comes from a tree? In this paper, we provide an answer to this question, showing that for k ≥ 3 a k-dissimilarity on a set X arises from a tree if and only if its restriction to every 2 k-element subset of X arises from some tree, and that 2 k is the least possible subset size to ensure that this is the case. As a corollary, we show that there exists a polynomial-time algorithm to determine when a k-dissimilarity arises from a tree. We also give a 6-point condition for determining when a 3-dissimilarity arises from a tree, that is similar to the aforementioned 4-point condition.
Journal of Classification – Springer Journals
Published: Sep 4, 2012
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.