Level-2 networks from shortest and longest distances

DOI10.1016/J.DAM.2021.09.026MaRDI QIDQ2243145zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 11 November 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

distance matrixlevel-k networkphylogenetic networksreconstructibility

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Taxonomy, cladistics, statistics in mathematical biology (92B10) Problems related to evolution (92D15)

Abstract: Recently it was shown that a certain class of phylogenetic networks, called level-$2$ networks, cannot be reconstructed from their associated distance matrices. In this paper, we show that they can be reconstructed from their induced shortest and longest distance matrices. That is, if two level-$2$ networks induce the same shortest and longest distance matrices, then they must be isomorphic. We further show that level-$2$ networks are reconstructible from their shortest distance matrices if and only if they do not contain a subgraph from a family of graphs. A generator of a network is the graph obtained by deleting all pendant subtrees and suppressing degree-$2$ vertices. We also show that networks with a leaf on every generator side is reconstructible from their induced shortest distance matrix, regardless of level.

Recommendations

• Reconstructibility of unrooted level-k phylogenetic networks from distances
• Recovering normal networks from shortest inter-taxa distance information
• On encodings of phylogenetic networks of bounded level
• Reconstruction of certain phylogenetic networks from their tree-average distances
• Constructing tree-child networks from distance matrices

Cites work

• An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances
• Constructing tree-child networks from distance matrices
• Determining phylogenetic networks from inter-taxa distances
• Diagonal tree codes
• Distance matrix of a graph and its realizability
• Free trees and bidirectional trees as representations of psychological distance
• Reconstructibility of unrooted level-k phylogenetic networks from distances
• Recovering normal networks from shortest inter-taxa distance information
• Unique reconstruction of tree-like phylogenetic networks from distances between leaves

Cited in

(1)

• On encodings of phylogenetic networks of bounded level

This page was built for publication: Level-\(2\) networks from shortest and longest distances

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