Computing rooted and unrooted maximum consistent supertrees

L.J.J. Iersel, van, M. Mnich

Research output: Book/ReportReportAcademic

Abstract

A chief problem in phylogenetics and database theory is the computation of a maximum consistent tree from a set of rooted or unrooted trees. A standard input are triplets, rooted binary trees on three leaves, or quartets, unrooted binary trees on four leaves. We give exact algorithms constructing rooted and unrooted maximum consistent supertrees in time O(2nn5m2 logm) for a set of m triplets (quartets), each one distinctly leaf-labeled by some subset of n labels. The algorithms extend to weighted triplets (quartets). We further present fast exact algorithms for constructing rooted and unrooted maximum consistent trees in polynomial space. Finally, for a set T of m rooted or unrooted trees with maximum degree D and distinctly leaf-labeled by some subset of a set L of n labels, we compute, in O(2mDnmm5n6 logm) time, a tree distinctly leaf-labeled by a maximum-size subset X C L that all trees in T , when restricted to X, are consistent with.
Original languageEnglish
Publishers.n.
Number of pages28
Publication statusPublished - 2009

Publication series

NamearXiv.org [cs.DM]
Volume0901.3299

Fingerprint Dive into the research topics of 'Computing rooted and unrooted maximum consistent supertrees'. Together they form a unique fingerprint.

Cite this