Path lengths in tree-child time consistent hybridization networks

DOI10.1016/J.INS.2009.09.013MaRDI QIDQ845330zbMATH OpenOpenAlexFDO

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

Publication date 28 January 2010

Published in Information Sciences (Search for Journal in Brave)

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

zbMATH Keywords

nodal distancehybridization networktree-child time consistent hybridization network

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)