On determining if tree-based networks contain fixed trees

DOI10.1007/S11538-016-0169-XMaRDI QIDQ309890zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(12)

• A method of characterizing network topology based on the breadth-first search tree
• Tree-based networks: characterisations, metrics, and support trees
• Non-essential arcs in phylogenetic networks
• A structure theorem for rooted binary phylogenetic networks and its implications for tree-based networks
• New characterisations of tree-based networks and proximity measures
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings
• 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)