Sets of double and triple weights of trees

DOI10.1007/S00026-011-0118-1MaRDI QIDQ659656zbMATH OpenOpenAlexFDO

Authors Elena Rubei

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.3026

zbMATH Keywords

neighbour-joining algorithmweighted graph distanceweights of trees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) General biology and biomathematics (92B05)

Abstract: Let T be a weighted tree with n leaves. Let D_{i,j} be the distance between the leaves i and j. Let D_{i,j,k}= (D_{i,j} + D_{j,k} +D_{i,k})/2. 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}.

Review text

Let \(T\) be a weighted tree with \(n\) leaves labelled by \(\{1,\dots, n\}\). The numbers \(D_{i,j}(T)\), \(i,j\in\{1,\dots,n\}\), are defined as sums of weights of the edges contained in the \(ij\)-paths in \(T\). The numbers \(D_{i,j,k}(T)\) are defined as \(D_{i,j,k}(T)=\frac12(D_{i,j}(T)+D_{j,k}(T)+D_{i,k}(T))\) (the total weight of the smallest subtree of \(T\) connecting \(i,j,k\)). One of the purposes of the paper is to characterize collections of numbers \(\{D_{i,j}\}_{i,j=1}^n\) and \(\{D_{i,j,k}\}_{i,j,k=1}^n\) which can be obtained in the described way. Another purpose is to suggest a modified version of the algorithm of \textit{N. Saitou} and \textit{M. Nei} [Mol. Biol. Evol. 4(4), 406--425 (1987)], whose purpose is to reconstruct a tree from given \(\{D_{i,j}\}_{i,j=1}^n\).

Recommendations

• On dissimilarity vectors of general weighted trees
• Tree reconstruction from triplet cover distances
• A characterization of dissimilarity families of trees
• Treelike families of multiweights
• Reconstructing trees from subtree weights.

Cites work

• A note on the metric properties of trees
• A tropical interpretation of \(m\)-dissimilarity maps
• Algebraic Statistics for Computational Biology
• scientific article; zbMATH DE number 2221693 (Why is no real title available?)
• On the relation between weighted trees and tropical Grassmannians
• Reconstructing trees from subtree weights.
• Small Trees and Generalized Neighbor-Joining
• The Mathematics of Phylogenomics
• The tropical Grassmannian
• Tropical mathematics

Cited in

(17)

• Reconstructing trees from subtree weights.
• An algorithm for the fitting of a tree metric according to a weighted least-squares criterion
• Treelike families of multiweights
• Phylogenetic diversity over an abelian group
• Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
• Recognizing treelike k-dissimilarities
• Families of multiweights and pseudostars
• Weighted graphs with distances in given ranges
• scientific article; zbMATH DE number 3871410 (Why is no real title available?)
• On the weights of simple paths in weighted complete graphs
• scientific article; zbMATH DE number 91019 (Why is no real title available?)
• On graphlike \(k\)-dissimilarity vectors
• Tree reconstruction from triplet cover distances
• On dissimilarity vectors of general weighted trees
• A characterization of dissimilarity families of trees
• A matroid associated with a phylogenetic tree
• Moduli space of families of positive \((n - 1)\)-weights

This page was built for publication: Sets of double and triple weights of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659656)