TY - JOUR

T1 - How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks

AU - Fischer, Mareike

AU - Hamann, Tom Niklas

AU - Wicke, Kristina

N1 - Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2023/10/15

Y1 - 2023/10/15

N2 - Phylogenetic networks which are, as opposed to trees, suitable to describe processes like hybridization and horizontal gene transfer, play a substantial role in evolutionary research. However, while non-treelike events need to be taken into account, they are relatively rare, which implies that biologically relevant networks are often assumed to be similar to trees in the sense that they can be obtained by taking a tree and adding some additional edges. This observation led to the concept of so-called tree-based networks, which recently gained substantial interest in the literature. Unfortunately, though, identifying such networks in the unrooted case is an NP-complete problem. Therefore, classes of networks for which tree-basedness can be guaranteed are of the utmost interest. The most prominent such class is formed by so-called edge-based networks, which have a close relationship to generalized series–parallel graphs known from graph theory. They can be identified in linear time and are in some regards biologically more plausible than general tree-based networks. While concerning the latter proximity measures for general networks have already been introduced, such measures are not yet available for edge-basedness. This means that for an arbitrary unrooted network, the “distance” to the nearest edge-based network could so far not be determined. The present manuscript fills this gap by introducing two classes of proximity measures for edge-basedness, one based on the given network itself and one based on its so-called leaf shrink graph (LS graph). Both classes contain four different proximity measures, whose similarities and differences we study subsequently.

AB - Phylogenetic networks which are, as opposed to trees, suitable to describe processes like hybridization and horizontal gene transfer, play a substantial role in evolutionary research. However, while non-treelike events need to be taken into account, they are relatively rare, which implies that biologically relevant networks are often assumed to be similar to trees in the sense that they can be obtained by taking a tree and adding some additional edges. This observation led to the concept of so-called tree-based networks, which recently gained substantial interest in the literature. Unfortunately, though, identifying such networks in the unrooted case is an NP-complete problem. Therefore, classes of networks for which tree-basedness can be guaranteed are of the utmost interest. The most prominent such class is formed by so-called edge-based networks, which have a close relationship to generalized series–parallel graphs known from graph theory. They can be identified in linear time and are in some regards biologically more plausible than general tree-based networks. While concerning the latter proximity measures for general networks have already been introduced, such measures are not yet available for edge-basedness. This means that for an arbitrary unrooted network, the “distance” to the nearest edge-based network could so far not be determined. The present manuscript fills this gap by introducing two classes of proximity measures for edge-basedness, one based on the given network itself and one based on its so-called leaf shrink graph (LS graph). Both classes contain four different proximity measures, whose similarities and differences we study subsequently.

KW - Edge-based network

KW - GSP graph

KW - K-minor free graph

KW - Phylogenetic network

KW - Tree-based network

UR - http://www.scopus.com/inward/record.url?scp=85160433724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85160433724&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2023.04.026

DO - 10.1016/j.dam.2023.04.026

M3 - Article

AN - SCOPUS:85160433724

SN - 0166-218X

VL - 337

SP - 303

EP - 320

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -