Distinguished minimal topological lassos

Huber, Katharina T. and Kettleborough, George (2015) Distinguished minimal topological lassos. SIAM Journal on Discrete Mathematics, 29 (2). 940–961. ISSN 0895-4801

Preview

PDF (published-version) - Published Version Download (361kB) | Preview

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.

Item Type:	Article
Uncontrolled Keywords:	dendrogram,block graph,claw free,topological lasso,$x$-tree
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Groups > Computational Biology
Depositing User:	Pure Connector
Date Deposited:	13 Mar 2015 13:14
Last Modified:	14 Jun 2023 12:06
URI:	https://ueaeprints.uea.ac.uk/id/eprint/52607
DOI:	10.1137/130927644

Downloads

Actions (login required)

View Item