Do branch lengths help to locate a tree in a phylogenetic network?

DOI10.1007/S11538-016-0199-4zbMATH Open1352.92103arXiv1607.06285OpenAlexW2496112388WikidataQ39361059 ScholiaQ39361059MaRDI QIDQ347040FDOQ347040

Authors: Philippe Gambette, Leo Van Iersel, Steven Kelk, Fabio Pardi, Celine Scornavacca 

Publication date: 30 November 2016

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

Abstract: Phylogenetic networks are increasingly used in evolutionary biology to represent the history of species that have undergone reticulate events such as horizontal gene transfer, hybrid speciation and recombination. One of the most fundamental questions that arise in this context is whether the evolution of a gene with one copy in all species can be explained by a given network. In mathematical terms, this is often translated in the following way: is a given phylogenetic tree contained in a given phylogenetic network? Recently this tree containment problem has been widely investigated from a computational perspective, but most studies have only focused on the topology of the phylo- genies, ignoring a piece of information that, in the case of phylogenetic trees, is routinely inferred by evolutionary analyses: branch lengths. These measure the amount of change (e.g., nucleotide substitutions) that has occurred along each branch of the phylogeny. Here, we study a number of versions of the tree containment problem that explicitly account for branch lengths. We show that, although length information has the potential to locate more precisely a tree within a network, the problem is computationally hard in its most general form. On a positive note, for a number of special cases of biological relevance, we provide algorithms that solve this problem efficiently. This includes the case of networks of limited complexity, for which it is possible to recover, among the trees contained by the network with the same topology as the input tree, the closest one in terms of branch lengths.

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

Recommendations

• Seeing the trees and their branches in the network is hard
• Locating a tree in a phylogenetic network
• Computational Science – ICCS 2005
• Phylogenetic Networks: Properties and Relationship to Trees and Clusters
• Linear time algorithm for tree-child network containment

zbMATH Keywords

computational complexityphylogenetic networkbranch lengthsdisplayed treestree containment

Mathematics Subject Classification ID

Applications of graph theory (05C90) Problems related to evolution (92D15)

Cites Work

• Introduction to algorithms
• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Locating a tree in a phylogenetic network
• Seeing the trees and their branches in the network is hard
• The Structure of Level-k Phylogenetic Networks
• ReCombinatorics. The algorithmics of ancestral recombination graphs and explicit phylogenetic networks. With contributions from Charles H. Langley, Yun S. Song and Yufeng Wu
• An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
• Tree Compatibility and Inferring Evolutionary History
• Computing the maximum agreement of phylogenetic networks
• Trinets encode tree-child and level-2 phylogenetic networks
• Phylogenetic networks that display a tree twice
• Mathematical Foundations of Computer Science 2005
• Detecting hybrid speciation in the presence of incomplete lineage sorting using gene tree incongruence: a model
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets

Cited In (4)

• When is a phylogenetic network simply an amalgamation of two trees?
• On the complexity of optimising variants of phylogenetic diversity on phylogenetic networks
• Seeing the trees and their branches in the network is hard
• Counting phylogenetic networks of level 1 and 2

Uses Software

• PhyloNetwork

This page was built for publication: Do branch lengths help to locate a tree in a phylogenetic network?

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