2013/08/12 by Katharina T. Huber, Huber, Katharina T., George Kettleborough +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05C05 #92D15 #Advanced Graph Neural Networks #Combinatorics #Combinatorics (math.CO) #Computer science #Dendrogram #Discrete mathematics #FOS: Biological sciences #FOS: Mathematics #Gene expression and cancer classification #Graph #Lasso (programming language) #Mathematics #Omega #Physics #Populations and Evolution (q-bio.PE) #Topological and Geometric Data Analysis #Topology (electrical circuits) #Tree (set theory) #math.CO #msc:05C05 #msc:92D15 #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1308.2537
published in arXiv (Cornell University) (Cornell University)
arxiv created 2013/08/12 · openalex publication_date 2013/08/12 · arxiv updated 2013/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 ω:E→ \mathbb R≥ 0) such that the distance D(T,ω) induced by (T,ω) on X is D. Moreover, algorithms that quickly reconstruct (T,ω) 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 \cL⊆ X\choose 2 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.