Distinguished minimal topological lassos

Katharina T. Huber, George Kettleborough

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
12 Downloads (Pure)

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 sub-species 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 well-known 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, edge-weighting, 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 set-inclusion 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 languageEnglish
Pages (from-to)940–961
Number of pages22
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number2
DOIs
Publication statusPublished - 26 May 2015

Keywords

  • dendrogram
  • block graph
  • claw free
  • topological lasso
  • $X$-tree

Cite this