Linear Time Algorithm for Tree-Child Network Containment

Conference paper (2020)

Authors

R. Janssen Discrete Mathematics and Optimization - EEMCS
Yukihiro Murakami Discrete Mathematics and Optimization - EEMCS
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2020 R. Janssen, Yukihiro Murakami
DOI: https://doi.org/10.1007/978-3-030-42266-0_8
Phylogenetics Tree-child networks Network Containment Tree-child sequences
More Info
expand_more

Published Date

2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

Phylogenetic networks are used to represent evolutionary scenarios in biology and linguistics. To find the most probable scenario, it may be necessary to compare candidate networks, to distinguish different networks, and to see when one network is embedded in another. Here, we consider the Network Containment problem, which asks whether a given network is contained in another network. We give a linear-time algorithm to this problem for the class of tree-child networks using the recently introduced tree-child sequences by Linz and Semple. We implement this algorithm in Python and show that the linear-time theoretical bound on the input size is achievable in practice.