Abstract
The ease with which genomic data can now be generated using Next Generation Sequencing technologies combined with a wealth of legacy data holds great promise for exciting new insights into the evolutionary relationships between and within the kingdoms of life. At the subspecies level (e.g. varieties or strains) certain edge weighted rooted trees with leaf set the set $X$ of organisms under consideration are often used to represent them. Called Dendrograms, it is wellknown that they can be uniquely reconstructed from distances provided all distances on $X$ are known. More often than not, real biological datasets do not satisfy this assumption implying that the sought after dendrogram need not be uniquely determined anymore by the available distances with regards to topology, edgeweighting, or both. To better understand the structural properties a set $\cL\subseteq {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, that is, it is a topological lasso for it's underlying tree. We show that any setinclusion minimal topological lasso for such a tree $T$ can be transformed into a structurally nice minimal topological lasso for $T$. Calling such a lasso a distinguished minimal topological lasso for $T$ we characterize them in terms of the novel concept of a cluster marker map for $T$. In addition, we present novel results concerning the heritability of such lassos in the context of the subtree and supertree problems.
Original language  English 

Pages (fromto)  940–961 
Number of pages  22 
Journal  SIAM Journal on Discrete Mathematics 
Volume  29 
Issue number  2 
DOIs  
Publication status  Published  26 May 2015 
Keywords
 dendrogram
 block graph
 claw free
 topological lasso
 $X$tree
Profiles

Katharina Huber
 School of Computing Sciences  Associate Professor
 Computational Biology  Member
Person: Research Group Member, Academic, Teaching & Research