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

Jesper Andreas Jansson, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

48 Citations (Scopus)


We consider the following problem: Given a set T of rooted triplets with leaf set L, determine whether there exists a phylogenetic network consistent with T, and if so, construct one. We show that 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 (| T |2) time when T is dense, i.e., when T contains at least one rooted triplet for each cardinality three subset of L. We also give an O (| T |5 / 3)-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
Pages (from-to)60-68
Number of pages9
JournalTheoretical Computer Science
Issue number1
Publication statusPublished - 25 Oct 2006
Externally publishedYes


  • Algorithm
  • Phylogenetic network construction
  • Rooted triplet
  • Sorting network

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'Inferring a level-1 phylogenetic network from a dense set of rooted triplets'. Together they form a unique fingerprint.

Cite this