On cherry-picking and network containment

On cherry-picking and network containment

Janssen, R. (TU Delft Discrete Mathematics and Optimization)
Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization)

2021

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. In particular, one needs to distinguish different networks and determine whether one network is contained in another. In this paper, we introduce cherry-picking networks, a class of networks that can be reduced by a so-called cherry-picking sequence. We then show how to compare such networks using their sequences. We characterize reconstructible cherry-picking networks, which are the networks that are uniquely determined by the sequences that reduce them, making them distinguishable. Furthermore, we show that a cherry-picking network is contained in another cherry picking network if a sequence for the latter network reduces the former network, provided both networks can be reconstructed from their sequences in a similar way (i.e., they are in the same reconstructible class). Lastly, we show that the converse of the above statement holds for tree-child networks, thereby showing that NETWORK CONTAINMENT, the problem of checking whether a network is contained in another, can be solved by computing cherry picking sequences in linear time for tree-child networks.

Cherry-picking networks
Cherry-picking sequences
Linear-time algorithms
Network containment
Phylogenetic networks
Tree containment

http://resolver.tudelft.nl/uuid:6fdc6897-0883-4fc1-b3c3-f62477324d49

https://doi.org/10.1016/j.tcs.2020.12.031

0304-3975

Theoretical Computer Science, 856, 121-150

Institutional Repository

journal article

© 2021 R. Janssen, Yukihiro Murakami