TY - GEN

T1 - The maximum agreement of two nested phylogenetic networks

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Given a set N of phylogenetic networks, the maximum agreement phylogenetic subnetwork problem (MASN) asks for a subnetwork contained in every Ni∈ N with as many leaves as possible. MASN can be used to identify shared branching structure among phylogenetic networks or to measure their similarity. In this paper, we prove that the general case of MASN is NP-hard already for two phylogenetic networks, but that the problem can be solved efficiently if the two given phylogenetic networks exhibit a nested structure. We first show that the total number of nodes |V(N)| in any nested phylogenetic network N with n leaves and nesting depth d is O(n(d + 1)). We then describe an algorithm for testing if a given phylogenetic network is nested, and if so, determining its nesting depth in O(|V(N)| · (d + 1)) time. Next, we present a polynomial-time algorithm for MASN for two nested phylogenetic networks N1, N2. Its running time is O(|V(N1)| · |V(N2)| · (d1+ 1) · (d2+ 1)), where d1and d2denote the nesting depths of N1and N2, respectively. In contrast, the previously fastest algorithm for this problem runs in O(|V(N1)| · |V(N2)| 4f) time, wheref≥ max{d1, d2}.

AB - Given a set N of phylogenetic networks, the maximum agreement phylogenetic subnetwork problem (MASN) asks for a subnetwork contained in every Ni∈ N with as many leaves as possible. MASN can be used to identify shared branching structure among phylogenetic networks or to measure their similarity. In this paper, we prove that the general case of MASN is NP-hard already for two phylogenetic networks, but that the problem can be solved efficiently if the two given phylogenetic networks exhibit a nested structure. We first show that the total number of nodes |V(N)| in any nested phylogenetic network N with n leaves and nesting depth d is O(n(d + 1)). We then describe an algorithm for testing if a given phylogenetic network is nested, and if so, determining its nesting depth in O(|V(N)| · (d + 1)) time. Next, we present a polynomial-time algorithm for MASN for two nested phylogenetic networks N1, N2. Its running time is O(|V(N1)| · |V(N2)| · (d1+ 1) · (d2+ 1)), where d1and d2denote the nesting depths of N1and N2, respectively. In contrast, the previously fastest algorithm for this problem runs in O(|V(N1)| · |V(N2)| 4f) time, wheref≥ max{d1, d2}.

UR - http://www.scopus.com/inward/record.url?scp=35048843750&partnerID=8YFLogxK

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 - 581

EP - 593

BT - Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004. Proceedings

A2 - Fleischer, Rudolf

A2 - Trippen, Gerhard

T2 - 15th International Symposium on Algorithms and Computation, ISAAC 2004

Y2 - 20 December 2004 through 22 December 2004

ER -