TY - GEN
T1 - Extracting conflict-free information from multi-labeled trees
AU - Deepak, Akshay
AU - Fernández-Baca, David
AU - McMahon, Michelle M.
N1 - Funding Information:
This work was supported in part by the National Science Foundation under grant DEB-0829674.
PY - 2012
Y1 - 2012
N2 - 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 among 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.
AB - 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 among 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.
UR - http://www.scopus.com/inward/record.url?scp=84866646398&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84866646398&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-33122-0_7
DO - 10.1007/978-3-642-33122-0_7
M3 - Conference contribution
AN - SCOPUS:84866646398
SN - 9783642331213
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 81
EP - 92
BT - Algorithms in Bioinformatics - 12th International Workshop, WABI 2012, Proceedings
T2 - 12th International Workshop on Algorithms in Bioinformatics, WABI 2012
Y2 - 10 September 2012 through 12 September 2012
ER -