Reconstructing an ultrametric galled phylogenetic network from a distance matrix

Ho Leung Chan, Jesper Andreas Jansson, Tak Wah Lam, Siu Ming Yiu

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

3 Citations (Scopus)

Abstract

Given a distance matrix M that specifies the pairwise evolutionary distances between n species, the phylogenetic tree reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies M, if one exists. We study some extensions of this problem to rooted phylogenetic networks. Our main result is an O(n2 log n)-time algorithm for determining whether there is an ultrametric galled network that satisfies M, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (hybrid nodes). We also prove that finding a largest possible submatrix M′ of M such that there exists an ultrametric galled network that satisfies M′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29-September 2, 2005. Proceedings
EditorsJoanna Jedrzejowicz, Andrzej Szepietowski
Pages224-235
Number of pages12
Publication statusPublished - 24 Oct 2005
Externally publishedYes
Event30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk, Poland
Duration: 29 Aug 20052 Sep 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
VolumeLNCS 3618
ISSN (Print)0302-9743

Conference

Conference30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005
Country/TerritoryPoland
CityGdansk
Period29/08/052/09/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this