Extracting Conflict-free Information from Multi-labeled Trees

Autor:	Deepak, Akshay, Fernández-Baca, David, McMahon, Michelle M.
Rok vydání:	2012
Předmět:	Computer Science - Data Structures and Algorithms Quantitative Biology - Populations and Evolution
Druh dokumentu:	Working Paper
Popis:	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. Comment: Submitted in Workshop on Algorithms in Bioinformatics 2012 (http://algo12.fri.uni-lj.si/?file=wabi)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1205.6359 Zobrazit plný text záznamu View this record from Arxiv