On determining if tree-based networks contain fixed trees

DOI10.1007/S11538-016-0169-XzbMATH Open1348.92114arXiv1602.02739OpenAlexW2259553647WikidataQ36002292 ScholiaQ36002292MaRDI QIDQ309890FDOQ309890

Authors: Maria Anaya, Olga Anipchenko-Ulaj, Aisha Ashfaq, Joyce Chiu, Mahedi Kaiser, Max Shoji Ohsawa, Megan Owen, Ella Pavlechko, Katherine St. John, Shivam Suleria, Keith Thompson, Corrine Yap 

Publication date: 7 September 2016

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

Abstract: We address an open question of Francis and Steel about phylogenetic networks and trees. They give a polynomial time algorithm to decide if a phylogenetic network, N, is tree-based and pose the problem: given a fixed tree T and network N, is N based on T? We show that it is NP-hard to decide, by reduction from 3-Dimensional Matching (3DM), and further, that the problem is fixed parameter tractable.

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

Recommendations

• Locating a tree in a phylogenetic network
• Solving the tree containment problem for genetically stable networks in quadratic time
• Seeing the trees and their branches in the network is hard
• Solving the tree containment problem in linear time for nearly stable phylogenetic networks
• Locating a tree in a phylogenetic network in quadratic time

zbMATH Keywords

phylogenetic treeanalysis of algorithmsphylogenetic network3-dimensional matching

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15) Analysis of algorithms (68W40)

Cites Work

• Reducibility among combinatorial problems
• Phylogenetic networks with every embedded phylogenetic tree a base tree
• Locating a tree in a phylogenetic network
• Seeing the trees and their branches in the network is hard
• Optimal algorithms for comparing trees with labeled leaves
• On the existence of infinitely many universal tree-based networks

Cited In (12)

• A method of characterizing network topology based on the breadth-first search tree
• Tree-based networks: characterisations, metrics, and support trees
• A structure theorem for rooted binary phylogenetic networks and its implications for tree-based networks
• Non-essential arcs in phylogenetic networks
• New characterisations of tree-based networks and proximity measures
• Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• Phylogenetic Networks
• A universal tree-based network with the minimum number of reticulations
• On the existence of funneled orientations for classes of rooted phylogenetic networks
• Tree-based unrooted phylogenetic networks
• A QUBO formulation for the tree containment problem

This page was built for publication: On determining if tree-based networks contain fixed trees

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