Inferring phylogenetic relationships avoiding forbidden rooted triplets

Ying Jun He, Trinh N.D. Huynh, Jesper Andreas Jansson, Wing Kin Sung

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

1 Citation (Scopus)

Abstract

To construct a phylogenetic tree or phylogenetic network for describing the evolutionary history of a set of species is a well-studied problem in computational biology. One previously proposed method to infer a phylogenetic tree/network for a large set of species is by merging a collection of known smaller phylogenetic trees on overlapping sets of species so that no (or as little as possible) branching information is lost. However, little work has been done so far on inferring a phylogenetic tree/network from a specified set of trees when in addition, certain evolutionary relationships among the species are known to be highly unlikely. In this paper, we consider the problem of constructing a phylogenetic tree/network which is consistent with all of the rooted triplets in a given set T and none of the rooted triplets in another given set F. Although NP-hard in the general case, we provide some efficient exact and approximation algorithms for a number of biologically meaningful variants of the problem.
Original languageEnglish
Title of host publicationProceedings of the 3rd Asia-Pacific Bioinformatics Conference, APBC 2005
Pages339-348
Number of pages10
Volume1
Publication statusPublished - 1 Dec 2005
Externally publishedYes
Event3rd Asia-Pacific Bioinformatics Conference, APBC 2005 - Singapore, Singapore
Duration: 17 Jan 200521 Jan 2005

Conference

Conference3rd Asia-Pacific Bioinformatics Conference, APBC 2005
CountrySingapore
CitySingapore
Period17/01/0521/01/05

ASJC Scopus subject areas

  • Bioengineering
  • Information Systems

Cite this