## Extracting Conflict-free Information from Multi-labeled Trees

Extracting Conflict-free Information from Multi-labeled Trees by Akshay Deepak, David Fernández-Baca, and Michelle M. McMahon.

Abstract:

A multi-labeled tree, or MUL-tree, is a phylogenetic tree where two or more leaves share a label, e.g., a species name. A MUL-tree can imply multiple conflicting phylogenetic relationships for the same set of taxa, but can also contain conflict-free information that is of interest and yet is not obvious. We define the information content of a MUL-tree T as the set of all conflict-free quartet topologies implied by T, and define the maximal reduced form of T as the smallest tree that can be obtained from T by pruning leaves and contracting edges while retaining the same information content. We show that any two MUL-trees with the same information content exhibit the same reduced form. This introduces an equivalence relation in MUL-trees with potential applications to comparing MUL-trees. We present an efficient algorithm to reduce a MUL-tree to its maximally reduced form and evaluate its performance on empirical datasets in terms of both quality of the reduced tree and the degree of data reduction achieved.

You may not agree with:

That is, for every MUL-tree $T$ there exists a singly-labeled tree that displays all the conflict-free quartets of $T$ — and possibly some other quartets as well. Motivated by this, we only view conflict-free quartet topologies as informative, and define the information content of a MUL-tree as the set of all conflict-free quartet topologies it implies.

Preferring to view conflicts as information content (I would) but each to his own.

I suspect “multi-labeled” trees are more common than one might expect.

Other examples?