Displaying trees across two phylogenetic networks

DOI10.1016/J.TCS.2019.09.003MaRDI QIDQ2333792zbMATH OpenOpenAlexFDO

Authors Janosch Döcker, Simone Linz, Charles Semple

Publication date 13 November 2019

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

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

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)

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.

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

Cites work

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

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)