Embedding Phylogenetic Trees in Networks of Low Treewidth

Conference paper (2022)

Authors

L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
M.E.L. Jones Discrete Mathematics and Optimization - EEMCS
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2022 L.J.J. van Iersel, M.E.L. Jones, Mathias Weller
DOI: https://doi.org/10.4230/LIPIcs.ESA.2022.69
Phylogenetic network Phylogenetic tree Embedding Tree containment Fixed-parameter tractability Display graph Treewidth
More Info
expand_more

Published Date

2022

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.