Tree reconstruction from triplet cover distances

zbMATH Open1300.05182arXiv1209.2391MaRDI QIDQ405205FDOQ405205

Authors: Katharina T. Huber, Mike Steel 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: It is a classical result that any finite tree with positively weighted edges, and without vertices of degree 2, is uniquely determined by the weighted path distance between each pair of leaves. Moreover, it is possible for a (small) strict subset $cl$ of leaf pairs to suffice for reconstructing the tree and its edge weights, given just the distances between the leaf pairs in $cl$. It is known that any set $cl$ with this property for a tree in which all interior vertices have degree 3 must form a {em cover} for $T$ -- that is, for each interior vertex $v$ of $T$, $cl$ must contain a pair of leaves from each pair of the three components of $T-v$. Here we provide a partial converse of this result by showing that if a set $cl$ of leaf pairs forms a cover of a certain type for such a tree $T$ then $T$ and its edge weights can be uniquely determined from the distances between the pairs of leaves in $cl$. Moreover, there is a polynomial-time algorithm for achieving this reconstruction. The result establishes a special case of a recent question concerning `triplet covers', and is relevant to a problem arising in evolutionary genomics.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Combinatorial properties of triplet covers for binary trees
• Minimum triplet covers of binary phylogenetic \(X\)-trees
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• Sets of double and triple weights of trees
• scientific article; zbMATH DE number 3871410

zbMATH Keywords

tree metricshellabilitytree reconstructiontriplet coverX-tree

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• A robust model for finding optimal evolutionary tree
• Title not available (Why is that?)
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• Patching up \(X\)-trees
• On the extension of a partial metric to a tree metric
• Minimum spanning trees for tree metrics: Abridgements and adjustments
• Title not available (Why is that?)
• A k-Tree Generalization that Characterizes Consistency of Dimensioned Engineering Drawings
• An Optimal Diagonal Tree Code

Cited In (11)

• Title not available (Why is that?)
• Sets of double and triple weights of trees
• An optimal algorithm to reconstruct trees from additive distance data
• Combinatorial properties of triplet covers for binary trees
• Minimum triplet covers of binary phylogenetic \(X\)-trees
• Reconstructing trees from subtree weights.
• Distinguished minimal topological lassos
• Recovering Trees with Convex Clustering
• Recovering a tree from the lengths of subtrees spanned by a randomly chosen sequence of leaves
• Lassoing and corralling rooted phylogenetic trees
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers

This page was built for publication: Tree reconstruction from triplet cover distances

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