Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/38919
Title: The maximum agreement of two nested phylogenetic networks
Authors: Jansson, J. 
Sung, W.-K. 
Issue Date: 2004
Source: Jansson, J.,Sung, W.-K. (2004). The maximum agreement of two nested phylogenetic networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3341 : 581-593. ScholarBank@NUS Repository.
Abstract: 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 N 1, N2. Its running time is O(|V(N1)| · |V(N2)| · (d1 + 1) · (d2 + 1)), where d1 and d2 denote the nesting depths of N1 and N2, respectively. In contrast, the previously fastest algorithm for this problem runs in O(|V(N1)| · |V(N2)| 4 f) time, where f ≥ max{d1, d2}. © Springer-Verlag 2004.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/38919
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

48
checked on Dec 8, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.