Computing the maximum agreement of phylogenetic networks

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of Computing: The Australasian Theory Symposium (CATS 2004)
EditorsMike D. Atkinson
Pages134-147
Number of pages14
DOIs
Publication statusPublished - 16 Feb 2004
Externally publishedYes
EventProceedings of Computing: The Australasian Theory Symposium (CATS) - Dunedin, New Zealand
Duration: 19 Jan 200420 Jan 2004

Publication series

NameElectronic Notes in Theoretical Computer Science
PublisherElsevier
Volume91
ISSN (Print)1571-0661

Conference

ConferenceProceedings of Computing: The Australasian Theory Symposium (CATS)
Country/TerritoryNew Zealand
CityDunedin
Period19/01/0420/01/04

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this