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

Leaves
Computing
Binary Tree
Exact Algorithms
Subset
Rooted Trees
Phylogenetics
Maximum Degree
Fast Algorithm
Polynomial

Cite this

Iersel, van, L. J. J., & Mnich, M. (2009). Computing rooted and unrooted maximum consistent supertrees. (arXiv.org [cs.DM]; Vol. 0901.3299). s.n.
Iersel, van, L.J.J. ; Mnich, M. / Computing rooted and unrooted maximum consistent supertrees. s.n., 2009. 28 p. (arXiv.org [cs.DM]).
@book{86c13c2dd5ea423498fa2aa3c54389d5,
title = "Computing rooted and unrooted maximum consistent supertrees",
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.",
author = "{Iersel, van}, L.J.J. and M. Mnich",
year = "2009",
language = "English",
series = "arXiv.org [cs.DM]",
publisher = "s.n.",

}

Iersel, van, LJJ & Mnich, M 2009, Computing rooted and unrooted maximum consistent supertrees. arXiv.org [cs.DM], vol. 0901.3299, s.n.

Computing rooted and unrooted maximum consistent supertrees. / Iersel, van, L.J.J.; Mnich, M.

s.n., 2009. 28 p. (arXiv.org [cs.DM]; Vol. 0901.3299).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - Computing rooted and unrooted maximum consistent supertrees

AU - Iersel, van, L.J.J.

AU - Mnich, M.

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

M3 - Report

T3 - arXiv.org [cs.DM]

BT - Computing rooted and unrooted maximum consistent supertrees

PB - s.n.

ER -

Iersel, van LJJ, Mnich M. Computing rooted and unrooted maximum consistent supertrees. s.n., 2009. 28 p. (arXiv.org [cs.DM]).