Leo van Iersel ; Mark Jones ; Mathias Weller - Embedding phylogenetic trees in networks of low treewidth

dmtcs:10116 - Discrete Mathematics & Theoretical Computer Science, October 2, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.10116
Embedding phylogenetic trees in networks of low treewidthArticle

Authors: Leo van Iersel ; Mark Jones ; Mathias Weller

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

    https://doi.org/10.46298/dmtcs.10116
    Source: arXiv.org:2207.00574
    Volume: vol. 25:2
    Section: Discrete Algorithms
    Published on: October 2, 2023
    Accepted on: June 21, 2023
    Submitted on: October 3, 2022
    Keywords: Quantitative Biology - Populations and Evolution, Computer Science - Discrete Mathematics
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • Encoding, reconstructing and comparing complex evolutionary scenarios; Code: 639.072.602

    Share and export

    Consultation statistics

    This page has been seen 864 times.
    This article's PDF has been downloaded 628 times.