Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks

Yuki Murakami, Leo van Iersel, Remie Janssen, Mark Jones, Vincent Moulton

Research output: Contribution to journalArticleScientificpeer-review

11 Citations (Scopus)
89 Downloads (Pure)

Abstract

Network reconstruction lies at the heart of phylogenetic research. Two well-studied classes of phylogenetic networks include tree-child networks and level-k networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-k network, the maximum number of reticulations contained in a biconnected component is k. Here, we show that level-k tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if k≥ 2. Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with k reticulations.

Original languageEnglish
Pages (from-to)3823-3863
Number of pages41
JournalBulletin of Mathematical Biology
Volume81
Issue number10
DOIs
Publication statusPublished - 2019

Bibliographical note

green

Keywords

  • Network encoding
  • Phylogenetic network
  • Reticulate-edge-deleted subnetworks
  • Tree-child networks

Fingerprint

Dive into the research topics of 'Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks'. Together they form a unique fingerprint.

Cite this