TY - GEN
T1 - Computing the maximum agreement of phylogenetic networks
AU - Choy, Charles
AU - Jansson, Jesper Andreas
AU - Sadakane, Kunihiko
AU - Sung, Wing Kin
PY - 2004/2/16
Y1 - 2004/2/16
N2 - We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomial-time algorithm for two level-f phylogenetic networks N1,N2for any f which is upper-bounded by a constant; more precisely, its running time is O(|V(N1)|·|V(N2)|·4f), where V(Ni) denotes the set of nodes of Ni.
AB - We introduce the maximum agreement phylogenetic subnetwork problem (MASN) of finding a branching structure shared by a set of phylogenetic networks. We prove that the problem is NP-hard even if restricted to three phylogenetic networks and give an O(n2)-time algorithm for the special case of two level-1 phylogenetic networks, where n is the number of leaves in the input networks and where N is called a level-f phylogenetic network if every biconnected component in the underlying undirected graph contains at most f nodes having indegree 2 in N. Our algorithm can be extended to yield a polynomial-time algorithm for two level-f phylogenetic networks N1,N2for any f which is upper-bounded by a constant; more precisely, its running time is O(|V(N1)|·|V(N2)|·4f), where V(Ni) denotes the set of nodes of Ni.
KW - Algorithm
KW - Computational complexity
KW - Maximum agreement subnetwork
KW - Phylogenetic network comparison
UR - http://www.scopus.com/inward/record.url?scp=18944380445&partnerID=8YFLogxK
U2 - 10.1016/j.entcs.2003.12.009
DO - 10.1016/j.entcs.2003.12.009
M3 - Conference article published in proceeding or book
T3 - Electronic Notes in Theoretical Computer Science
SP - 134
EP - 147
BT - Proceedings of Computing: The Australasian Theory Symposium (CATS 2004)
A2 - Atkinson, Mike D.
T2 - Proceedings of Computing: The Australasian Theory Symposium (CATS)
Y2 - 19 January 2004 through 20 January 2004
ER -