Level-2 networks from shortest and longest distances

Huber, Katharina, van Iersel, Leo, Janssen, Remie, Jones, Mark, Moulton, Vincent ORCID: https://orcid.org/0000-0001-9371-6435 and Murakami, Yuki (2022) Level-2 networks from shortest and longest distances. Discrete Applied Mathematics, 306. pp. 138-165. ISSN 0166-218X

Preview

PDF (Published_Version) - Published Version Available under License Creative Commons Attribution. Download (758kB) | Preview

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 are reconstructible from their induced shortest distance matrix.

Item Type:	Article
Additional Information:	Funding Information: Research funded in part by The Netherlands Organization for Scientific Research (NWO) Vidi grant 639.072.602 and Klein grant OCENW.KLEIN.125, and partly by the 4TU Applied Mathematics Institute. Mark Jones was also supported by The Netherlands Organisation for Scientific Research (NWO) through Gravitation Programme Networks 024.002.003.
Uncontrolled Keywords:	distance matrix,level-k network,phylogenetic networks,reconstructibility,discrete mathematics and combinatorics,applied mathematics ,/dk/atira/pure/subjectarea/asjc/2600/2607
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	06 Oct 2021 01:59
Last Modified:	20 Apr 2023 22:36
URI:	https://ueaeprints.uea.ac.uk/id/eprint/81572
DOI:	10.1016/j.dam.2021.09.026

Downloads

Actions (login required)

View Item