License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.57
URN: urn:nbn:de:0030-drops-100056
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10005/
Go to the corresponding LIPIcs Volume Portal

Hirai, Hiroshi ; Iwamasa, Yuni

Reconstructing Phylogenetic Tree From Multipartite Quartet System

pdf-format:
LIPIcs-ISAAC-2018-57.pdf (2 MB)

Abstract

A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses.
In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.

BibTeX - Entry

@InProceedings{hirai_et_al:LIPIcs:2018:10005,
  author =	{Hiroshi Hirai and Yuni Iwamasa},
  title =	{{Reconstructing Phylogenetic Tree From Multipartite Quartet System}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{57:1--57:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10005},
  URN =		{urn:nbn:de:0030-drops-100056},
  doi =		{10.4230/LIPIcs.ISAAC.2018.57},
  annote =	{Keywords: phylogenetic tree, quartet system, reconstruction}
}

Keywords: phylogenetic tree, quartet system, reconstruction
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI