Inferring a level-1 phylogenetic network from a dense set of rooted triplets

Jesper Andreas Jansson, Wing Kin Sung

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

11 Citations (Scopus)

Abstract

Given a set T of rooted triplets with leaf set L, we consider the problem of determining whether there exists a phylogenetic network consistent with T, and if so, constructing one. If no restrictions are placed on the hybrid nodes in the solution, the problem is trivially solved in polynomial time by a simple sorting network-based construction. For the more interesting (and biologically more motivated) case where the solution is required to be a level-1 phylogenetic network, we present an algorithm solving the problem in O(n6) time when T is dense (i.e., contains at least one rooted triplet for each cardinality three subset of L), where n = |L|. Note that the size of the input is Θ(n3) if T is dense. We also give an O(n5)-time algorithm for finding the set of all phylogenetic networks having a single hybrid node attached to exactly one leaf (and having no other hybrid nodes) that are consistent with a given dense set of rooted triplets.
Original languageEnglish
Title of host publicationComputing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 2004 Proceedings
EditorsKyung-Yong Chwa, J. Ian Munro
Pages462-471
Number of pages10
Publication statusPublished - 2004
Externally publishedYes
Event10th Annual International Computing and Combinatorics Conference, COCOON 2004 - Jeju Island, Korea, Republic of
Duration: 17 Aug 200420 Aug 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
VolumeLNCS 3106
ISSN (Print)0302-9743

Conference

Conference10th Annual International Computing and Combinatorics Conference, COCOON 2004
Country/TerritoryKorea, Republic of
CityJeju Island
Period17/08/0420/08/04

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this