TY - GEN

T1 - Rooted maximum agreement supertrees

AU - Jansson, Jesper Andreas

AU - Ng, Joseph H K

AU - Sadakane, Kunihiko

AU - Sung, Wing Kin

PY - 2004

Y1 - 2004

N2 - Given a set τ rooted, unordered trees, where each Ti ∈ τ is distinctly leaf-labeled by a set Λ(Ti) and where the sets Λ(Ti) may overlap, the maximum agreement supertree problem(MASP) is to construct a distinctly leaf-labeled tree script Q sign with leaf set Λ(script Q sign) ⊆ ∪Ti ∈ τ Λ(Ti) such that |Λ(script Q sign)| is maximized and for each Ti ∈ Τ, the topological restriction of Ti to Λ(script Q sign) is isomorphic to the topological restriction of script Q sign to Λ(Ti). Let n = |∪Ti ∈ τ Λ(Ti)|, k = |Τ|, and D = maxTi ∈ Τ {deg(Ti)}. We first show that MASP with k = 2 can be solved in O(√Dn log (2n/D)) time, which is O(n log n) when D = O(1) and O(n 1.5) when D is unrestricted. We then present an algorithm for MASP with D = 2 whose running time is polynomial if k = O(1). On the other hand, we prove that MASP is NP-hard for any fixed k ≥ 3 when D is unrestricted, and also NP-hard for any fixed D ≥ 2 when k is unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time (n/log n)-approximation algorithm for MASP.

AB - Given a set τ rooted, unordered trees, where each Ti ∈ τ is distinctly leaf-labeled by a set Λ(Ti) and where the sets Λ(Ti) may overlap, the maximum agreement supertree problem(MASP) is to construct a distinctly leaf-labeled tree script Q sign with leaf set Λ(script Q sign) ⊆ ∪Ti ∈ τ Λ(Ti) such that |Λ(script Q sign)| is maximized and for each Ti ∈ Τ, the topological restriction of Ti to Λ(script Q sign) is isomorphic to the topological restriction of script Q sign to Λ(Ti). Let n = |∪Ti ∈ τ Λ(Ti)|, k = |Τ|, and D = maxTi ∈ Τ {deg(Ti)}. We first show that MASP with k = 2 can be solved in O(√Dn log (2n/D)) time, which is O(n log n) when D = O(1) and O(n 1.5) when D is unrestricted. We then present an algorithm for MASP with D = 2 whose running time is polynomial if k = O(1). On the other hand, we prove that MASP is NP-hard for any fixed k ≥ 3 when D is unrestricted, and also NP-hard for any fixed D ≥ 2 when k is unrestricted even if each input tree is required to contain at most three leaves. Finally, we describe a polynomial-time (n/log n)-approximation algorithm for MASP.

KW - Algorithm

KW - Computational complexity

KW - Maximum agreement supertree

KW - Phylogenetic tree

KW - Rooted triplet

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-21144433769&origin=resultslist&sort=plf-f&src=s&sid=34de6aa52b629d27e2b3e66852e1b01b&sot=autdocs&sdt=autdocs&sl=18&s=AU-ID%2810439175200%29&relpos=98&citeCnt=6&searchTerm=

U2 - 10.1007/s00453-004-1147-5

DO - 10.1007/s00453-004-1147-5

M3 - Conference article published in proceeding or book

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 499

EP - 508

BT - LATIN 2004: Theoretical Informatics, 6th Latin American Syposium, Buenos Aires, Argentina, April 2004 Proceedings

A2 - Farach-Colton, Martin

T2 - 6th Latin American Symposium on Theoretical Informatics, LATIN 2004

Y2 - 5 April 2004 through 8 April 2004

ER -