Tree reconstruction from triplet cover distances

MaRDI QIDQ405205zbMATH OpenFDO

Authors Katharina T. Huber, Mike Steel

Publication date 4 September 2014

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

Full work available at URL https://arxiv.org/abs/1209.2391, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p15

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

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)

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.

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

Cites work

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

Cited in

(11)

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

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)