Distinguished minimal topological lassos

DOI10.1137/130927644MaRDI QIDQ5265017zbMATH OpenOpenAlexFDO

Authors George Kettleborough, Katharina T. Huber

Publication date 21 July 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.2537, https://ueaeprints.uea.ac.uk/id/eprint/52607/6/published_version.pdf

zbMATH Keywords

\(X\)-treeblock graphclaw-free graphdendrogramtopological lasso

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory (05C90) Problems related to evolution (92D15)

Abstract: A classical result in distance based tree-reconstruction characterizes when for a distance $D$ on some finite set $X$ there exist a uniquely determined dendrogram on $X$ (essentially a rooted tree $T=(V,E)$ with leaf set $X$ and no degree two vertices but possibly the root and an edge weighting $omega:Eomathbb{R}_{geq0}$) such that the distance $D_{(T,omega)}$ induced by $(T,omega)$ on $X$ is $D$. Moreover, algorithms that quickly reconstruct $(T,omega)$ from $D$ in this case are known. However in many areas where dendrograms are being constructed such as Computational Biology not all distances on $X$ are always available implying that the sought after dendrogram need not be uniquely determined anymore by the available distances with regards to topology of the underlying tree, edge-weighting, or both. To better understand the structural properties a set $cLsubseteqXchoose2$ has to satisfy to overcome this problem, various types of lassos have been introduced. Here, we focus on the question of when a lasso uniquely determines the topology of a dendrogram's underlying tree, that is, it is a topological lasso for that tree. We show that any set-inclusion minimal topological lasso for such a tree $T$ can be transformed into a 'distinguished' minimal topological lasso $cL$ for $T$, that is, the graph $(X,cL)$ is a claw-free block graph. Furthermore, we characterize such lassos in terms of the novel concept of a cluster marker map for $T$ and present results concerning the heritability of such lassos in the context of the subtree and supertree problems.

Recommendations

• Lassoing and corralling rooted phylogenetic trees
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• A matroid associated with a phylogenetic tree
• Tree reconstruction from triplet cover distances
• Unique solvability of certain hybrid networks from their distances

Cites work

• \(k\)-domination and \(k\)-independence in graphs: A survey
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers
• A robust model for finding optimal evolutionary tree
• Basic phylogenetic combinatorics.
• Characterizing phylogenetically decisive taxon coverage
• Claw-free graphs---a survey
• scientific article; zbMATH DE number 53860 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Lassoing and corralling rooted phylogenetic trees
• More about singular line graphs of trees
• On the adjacency matrix of a block graph
• On the extension of a partial metric to a tree metric
• On the nullity of line graphs of trees
• Phylogenetic supertrees. Combining information to reveal the tree of life
• Simplicial Powers of Graphs
• The Two-Triangle Case of the Acquaintance Graph
• Tree reconstruction from triplet cover distances

Cited in

(2)

• Lassoing and corralling rooted phylogenetic trees
• `Lassoing' a phylogenetic tree. I: Basic properties, shellings, and covers

This page was built for publication: Distinguished minimal topological lassos

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