License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2021.6
URN: urn:nbn:de:0030-drops-143591
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14359/
Go to the corresponding LIPIcs Volume Portal

Scornavacca, Celine ; Weller, Mathias

Treewidth-Based Algorithms for the Small Parsimony Problem on Networks

pdf-format:
LIPIcs-WABI-2021-6.pdf (0.9 MB)

Abstract

Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states to its leaves, assign states to the internal nodes of T such as to minimize the parsimony score, that is, the number of edges of T connecting nodes with different states. While this problem is polynomial-time solvable on trees, the matter is more complicated if T contains reticulate events such as hybridizations or recombinations, i.e. when T is a network. Indeed, three different versions of the parsimony score on networks have been proposed and each of them is NP-hard to decide. Existing parameterized algorithms focus on combining the number of possible character-states with the number of reticulate events (per biconnected component). Here, we consider the treewidth of the undirected graph underlying the input network as parameter, presenting dynamic programming algorithms for (slight generalizations of) all three versions of the parsimony problem on networks. Our algorithms use a formulation of the treewidth that may facilitate formalizing treewidth-based dynamic programming algorithms on phylogenetic networks for other problems.

BibTeX - Entry

@InProceedings{scornavacca_et_al:LIPIcs.WABI.2021.6,
  author =	{Scornavacca, Celine and Weller, Mathias},
  title =	{{Treewidth-Based Algorithms for the Small Parsimony Problem on Networks}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{6:1--6:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14359},
  URN =		{urn:nbn:de:0030-drops-143591},
  doi =		{10.4230/LIPIcs.WABI.2021.6},
  annote =	{Keywords: Phylogenetics, parsimony, phylogenetic networks, parameterized complexity, dynamic programming, treewidth}
}

Keywords: Phylogenetics, parsimony, phylogenetic networks, parameterized complexity, dynamic programming, treewidth
Collection: 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Issue Date: 2021
Date of publication: 22.07.2021

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