Path lengths in tree-child time consistent hybridization networks

DOI10.1016/J.INS.2009.09.013zbMATH Open1180.92064arXiv0807.0087OpenAlexW2103656071MaRDI QIDQ845330FDOQ845330

Authors: Gabriel Cardona, Mercè Llabrés, Francesc Rosselló, Gabriel Valiente 

Publication date: 28 January 2010

Published in: Information Sciences (Search for Journal in Brave)

Abstract: Hybridization networks are representations of evolutionary histories that allow for the inclusion of reticulate events like recombinations, hybridizations, or lateral gene transfers. The recent growth in the number of hybridization network reconstruction algorithms has led to an increasing interest in the definition of metrics for their comparison that can be used to assess the accuracy or robustness of these methods. In this paper we establish some basic results that make it possible the generalization to tree-child time consistent (TCTC) hybridization networks of some of the oldest known metrics for phylogenetic trees: those based on the comparison of the vectors of path lengths between leaves. More specifically, we associate to each hybridization network a suitably defined vector of `splitted' path lengths between its leaves, and we prove that if two TCTC hybridization networks have the same such vectors, then they must be isomorphic. Thus, comparing these vectors by means of a metric for real-valued vectors defines a metric for TCTC hybridization networks. We also consider the case of fully resolved hybridization networks, where we prove that simpler, `non-splitted' vectors can be used.

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

Recommendations

• On the complexity of computing the temporal hybridization number for two phylogenies
• Route lengths in invariant spatial tree networks
• The space of tree-based phylogenetic networks
• Coalescent time distributions in trees of arbitrary size
• Locating a tree in a phylogenetic network in quadratic time
• The path-variance problem on tree networks
• On the complexity of average path length for biological networks and patterns
• Reconstruction of some hybrid phylogenetic networks with homoplasies from distances

zbMATH Keywords

nodal distancehybridization networktree-child time consistent hybridization network

Mathematics Subject Classification ID

Problems related to evolution (92D15) Systems biology, networks (92C42)

Cites Work

• The fine structure of galls in phylogenetic networks
• Title not available (Why is that?)
• Computing the maximum agreement of phylogenetic networks
• Newton's method and the computational complexity of the fundamental theorem of algebra
• Automatic learning of cost functions for graph edit distance
• Evolutionary design of oriented-tree networks using Cayley-type encodings
• A method for the linear recording of graphs
• Reconstruction of certain phylogenetic networks from the genomes at their leaves
• Tripartitions do not always discriminate phylogenetic networks
• Towards the development of computational tools for evaluating phylogenetic network reconstruction methods

Cited In (3)

• Trinets encode tree-child and level-2 phylogenetic networks
• Deciding the existence of a cherry-picking sequence is hard on two trees
• Classes of explicit phylogenetic networks and their biological and mathematical significance

Uses Software

• PhyloNetwork

This page was built for publication: Path lengths in tree-child time consistent hybridization networks

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