Computing the maximum agreement of phylogenetic networks

Charles Choy, Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)

Abstract

We introduce the maximum agreement phylogenetic subnetwork problem (MASN) for finding 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 induces a subgraph of N containing at most f nodes with indegree 2. We also show how to extend our technique to yield a polynomial-time algorithm for any two level-f phylogenetic networks N1,N2 satisfying f=O(logn); more precisely, its running time is O(|V(N1)|·|V(N2)|·2f1+f2), where V(Ni) and fi denote the set of nodes in Ni and the level of Ni, respectively, for i∈{1,2}.
Original languageEnglish
Pages (from-to)93-107
Number of pages15
JournalTheoretical Computer Science
Volume335
Issue number1
DOIs
Publication statusPublished - 20 May 2005
Externally publishedYes

Keywords

  • Algorithm
  • Computational complexity
  • Maximum agreement subnetwork
  • Phylogenetic network comparison

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this