On cherry-picking and network containment

Remie Janssen, Yukihiro Murakami*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Citations (Scopus)
45 Downloads (Pure)

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. 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.

Original languageEnglish
Pages (from-to)121-150
Number of pages30
JournalTheoretical Computer Science
Volume856
DOIs
Publication statusPublished - 2021

Keywords

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

Fingerprint

Dive into the research topics of 'On cherry-picking and network containment'. Together they form a unique fingerprint.

Cite this