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.WABI.2019.5
URN: urn:nbn:de:0030-drops-110355
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11035/
Go to the corresponding LIPIcs Volume Portal

Yamada, Kohei ; Chen, Zhi-Zhong ; Wang, Lusheng

Better Practical Algorithms for rSPR Distance and Hybridization Number

pdf-format:
LIPIcs-WABI-2019-5.pdf (0.5 MB)

Abstract

The problem of computing the rSPR distance of two phylogenetic trees (denoted by RDC) is NP-hard and so is the problem of computing the hybridization number of two phylogenetic trees (denoted by HNC). Since they are important problems in phylogenetics, they have been studied extensively in the literature. Indeed, quite a number of exact or approximation algorithms have been designed and implemented for them. In this paper, we design and implement one exact algorithm for HNC and several approximation algorithms for RDC and HNC. Our experimental results show that the resulting exact program is much faster (namely, more than 80 times faster for the easiest dataset used in the experiments) than the previous best and its superiority in speed becomes even more significant for more difficult instances. Moreover, the resulting approximation programs output much better results than the previous bests; indeed, the outputs are always nearly optimal and often optimal. Of particular interest is the usage of the Monte Carlo tree search (MCTS) method in the design of our approximation algorithms. Our experimental results show that with MCTS, we can often solve HNC exactly within short time.

BibTeX - Entry

@InProceedings{yamada_et_al:LIPIcs:2019:11035,
  author =	{Kohei Yamada and Zhi-Zhong Chen and Lusheng Wang},
  title =	{{Better Practical Algorithms for rSPR Distance and Hybridization Number}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Katharina T. Huber and Dan Gusfield},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11035},
  URN =		{urn:nbn:de:0030-drops-110355},
  doi =		{10.4230/LIPIcs.WABI.2019.5},
  annote =	{Keywords: phylogenetic tree, fixed-parameter algorithms, approximation algorithms, Monte Carlo tree search}
}

Keywords: phylogenetic tree, fixed-parameter algorithms, approximation algorithms, Monte Carlo tree search
Collection: 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Issue Date: 2019
Date of publication: 03.09.2019
Supplementary Material: Our programs are available at http://rnc.r.dendai.ac.jp/rsprHN.html.

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