Displaying trees across two phylogenetic networks

DOI10.1016/J.TCS.2019.09.003zbMATH Open1435.68231arXiv1901.06612OpenAlexW2914009758MaRDI QIDQ2333792FDOQ2333792

Authors: Janosch Döcker, Simone Linz, Charles Semple 

Publication date: 13 November 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Phylogenetic networks are a generalization of phylogenetic trees to leaf-labeled directed acyclic graphs that represent ancestral relationships between species whose past includes non-tree-like events such as hybridization and horizontal gene transfer. Indeed, each phylogenetic network embeds a collection of phylogenetic trees. Referring to the collection of trees that a given phylogenetic network $N$ embeds as the display set of $N$, several questions in the context of the display set of $N$ have recently been analyzed. For example, the widely studied Tree-Containment problem asks if a given phylogenetic tree is contained in the display set of a given network. The focus of this paper are two questions that naturally arise in comparing the display sets of two phylogenetic networks. First, we analyze the problem of deciding if the display sets of two phylogenetic networks have a tree in common. Surprisingly, this problem turns out to be NP-complete even for two temporal normal networks. Second, we investigate the question of whether or not the display sets of two phylogenetic networks are equal. While we recently showed that this problem is polynomial-time solvable for a normal and a tree-child network, it is computationally hard in the general case. In establishing hardness, we show that the problem is contained in the second level of the polynomial-time hierarchy. Specifically, it is $P{i}_2^P$-complete. Along the way, we show that two other problems are also $P{i}_2^P$-complete, one of which being a generalization of Tree-Containment.

Full work available at URL: https://arxiv.org/abs/1901.06612

Recommendations

• Display sets of normal and tree-child networks
• Locating a tree in a phylogenetic network
• Computational Science – ICCS 2005
• Phylogenetic Networks: Properties and Relationship to Trees and Clusters
• Seeing the trees and their branches in the network is hard

zbMATH Keywords

phylogenetic networktemporal networkpolynomial-time hierarchynormal network\textsc{tree-containment}display set

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Phylogenetic networks with every embedded phylogenetic tree a base tree
• Locating a tree in a phylogenetic network
• Reticulation-visible networks
• Seeing the trees and their branches in the network is hard
• The polynomial-time hierarchy
• Counting phylogenetic networks
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Properties of normal phylogenetic networks
• A decomposition theorem and two algorithms for reticulation-visible networks
• Display sets of normal and tree-child networks

Cited In (8)

• When is a phylogenetic network simply an amalgamation of two trees?
• Non-essential arcs in phylogenetic networks
• Display sets of normal and tree-child networks
• Locating a tree in a phylogenetic network
• Computational Science – ICCS 2005
• Phylogenetic Networks: Properties and Relationship to Trees and Clusters
• Phylogenetic networks that display a tree twice
• A QUBO formulation for the tree containment problem

This page was built for publication: Displaying trees across two phylogenetic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333792)