Embedding Phylogenetic Trees in Networks of Low Treewidth

Leo Van Iersel, Mark Jones, Mathias Weller

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
42 Downloads (Pure)

Abstract

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2O(t2) |N| time and space.

Original languageEnglish
Title of host publication30th Annual European Symposium on Algorithms, ESA 2022
EditorsShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages69:1-69:14
Number of pages14
ISBN (Electronic)9783959772471
DOIs
Publication statusPublished - 2022
Event30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany
Duration: 5 Sept 20229 Sept 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume244
ISSN (Print)1868-8969

Conference

Conference30th Annual European Symposium on Algorithms, ESA 2022
Country/TerritoryGermany
CityBerlin/Potsdam
Period5/09/229/09/22

Keywords

  • display graph
  • embedding
  • fixed-parameter tractability
  • phylogenetic network
  • phylogenetic tree
  • tree containment
  • treewidth

Fingerprint

Dive into the research topics of 'Embedding Phylogenetic Trees in Networks of Low Treewidth'. Together they form a unique fingerprint.

Cite this