@inproceedings{f2a7ebe761774a18ade8af8db1c34e3a,
title = "Linear Time Algorithm for Tree-Child Network Containment",
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.",
keywords = "Network Containment, Phylogenetics, Tree-child networks, Tree-child sequences",
author = "Remie Janssen and Yukihiro Murakami",
note = "Accepted author manuscript; 7th International Conference on Algorithms for Computational Biology, AlCoB 2020 ; Conference date: 13-04-2020 Through 15-04-2020",
year = "2020",
doi = "10.1007/978-3-030-42266-0_8",
language = "English",
isbn = "978-3-030-42265-3",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "93--107",
editor = "Carlos Mart{\'i}n-Vide and Vega-Rodr{\'i}guez, {Miguel A.} and Travis Wheeler",
booktitle = "Algorithms for Computational Biology",
}