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

DOI10.1007/S11538-016-0199-4MaRDI QIDQ347040zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

computational complexityphylogenetic networkbranch lengthsdisplayed treestree containment

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)