Abstract
Let T be a weighted tree with n leaves numbered by the set {1, . . . , n}. Let D i, j (T) be the distance between the leaves i and j. Let \({{D_{i,j,k}(T) = \frac{1}{2}(D_{i,j}(T)+D_{j,k}(T)+D_{i,k}(T))}}\) . We will call such numbers “triple weights” of the tree. In this paper, we give a characterization, different from the previous ones, for sets indexed by 2-subsets of a n-set to be double weights of a tree. By using the same ideas, we find also necessary and sufficient conditions for a set of real numbers indexed by 3-subsets of an n-set to be the set of the triple weights of a tree with n leaves. Besides we propose a slight modification of Saitou-Nei’s Neighbour-Joining algorithm to reconstruct trees from the data D i, j .
Similar content being viewed by others
References
Bocci C., Cools F.: A tropical interpretation of m-dissimilarity maps. Appl. Math. Comput. 212(2), 349–356 (2009)
Buneman P.: A note on the metric properties of trees. J. Combin. Theory Ser. B 17, 48–50 (1974)
Buneman P.: The recovery of trees from measures of dissimilarity. In: Kendall, D.G., Tautu, P. (eds) Mathematics in the Archeological and Historical Sciences, pp. 387–395. Edinburgh University Press, Edinburgh (1971)
Contois M., Levy D.: Small trees and generalized neighbor joining. In: Pachter, L., Sturmfels, B. (eds) Algebraic Statistics for Computational Biology, pp. 333–344. Cambridge University Press, New York (2005)
Cools F.: On the relations between weighted trees and tropical Grassmannians. J. Symbolic Comput. 44(8), 1079–1086 (2009)
Levy D., Pachter L., Yoshida R.: Beyond pairwise distances: neighbor joining with phylogenetic diversity estimates. Mol. Biol. Evol. 23, 491–498 (2006)
Pachter L., Speyer D.: Reconstructing trees from subtree weights. Appl. Math. Lett. 17(6), 615–621 (2004)
Pachter L., Sturmfels B.: Algebraic Statistics for Computational Biology. Cambridge University Press, New York (2005)
Pachter L., Sturmfels B.: The mathematics of phylogenomics. SIAM Rev. 49(1), 3–31 (2007)
Richter-Gebert J., Sturmfels B., Theobald T.: First steps in tropical geometry. In: Litvinov, G.L., Maslov, V.P. (eds) Idempotent Mathematics and Mathematical Physics, pp. 289–317. Amer. Math. Soc., Providence (2005)
Saitou N., Nei M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4(4), 406–425 (1987)
Speyer D., Sturmfels B.: The tropical Grassmannian. Adv. Geom. 4(3), 389–411 (2004)
Speyer D., Sturmfels B.: Tropical mathematics. Math. Mag. 82(3), 163–173 (2009)
Studier J.A., Keppler K.J.: A note on the neighbor-joining algorithm of Saitou and Nei. Mol. Biol. Evol. 5(6), 729–731 (1988)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rubei, E. Sets of Double and Triple Weights of Trees. Ann. Comb. 15, 723–734 (2011). https://doi.org/10.1007/s00026-011-0118-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-011-0118-1