<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
MSets of Double and Triple Weights of Trees
Elena Rubei
Dipartimento di Matematica “U. Dini”, viale Morgagni 67/A, 50134 Firenze, Italia
Annals of Combinatorics 15 (4) pp.723-734 December, 2011
AMS Subject Classification: 05C05, 05C12, 92B05
Let T be a weighted tree with n leaves numbered by the set {1, . . . , n}. Let Di, j(T) be the distance between the leaves i and j. Let Di, j, k(T) = 1/2( Di, j(T) +Dj, k(T) +Di, 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 Di, j.
Keywords: trees, weights of trees, neighbour-joining algorithm


1.Bocci, C., Cools, F.: A tropical interpretation of m-dissimilarity maps. Appl. Math. Comput. 212(2), 349–356 (2009)

2. Buneman, P.: A note on the metric properties of trees. J. Combin. Theory Ser. B 17, 48–50 (1974)

3. 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)

4. 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)

5. Cools, F.: On the relations between weighted trees and tropical Grassmannians. J. Symbolic Comput. 44(8), 1079–1086 (2009)

6. Levy, D., Pachter, L., Yoshida, R.: Beyond pairwise distances: neighbor joining with phylogenetic diversity estimates. Mol. Biol. Evol. 23, 491–498 (2006)

7. Pachter, L., Speyer, D.: Reconstructing trees from subtree weights. Appl. Math. Lett. 17(6), 615–621 (2004)

8. Pachter, L., Sturmfels, B.: Algebraic Statistics for Computational Biology. Cambridge University Press, New York (2005)

9. Pachter, L., Sturmfels, B.: The mathematics of phylogenomics. SIAM Rev. 49(1), 3–31 (2007)

10. 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)

11. Saitou, N., Nei, M.: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol. Biol. Evol. 4(4), 406–425 (1987)

12. Speyer, D., Sturmfels, B.: The tropical Grassmannian. Adv. Geom. 4(3), 389–411 (2004)

13. Speyer, D., Sturmfels, B.: Tropical mathematics. Math. Mag. 82(3), 163–173 (2009)

14. 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)