Characterizing semi-directed phylogenetic networks and their multi-rootable variants

Holtgrefe, Niels, Huber, Katharina T., van Iersel, Leo, Jones, Mark and Moulton, Vincent (2025) Characterizing semi-directed phylogenetic networks and their multi-rootable variants. Theory in Biosciences. ISSN 1431-7613 (In Press)

PDF (semi_directed_characterizations) - Accepted Version Restricted to Repository staff only until 31 December 2099. Available under License Creative Commons Attribution No Derivatives. Request a copy

Abstract

In evolutionary biology, phylogenetic networks are graphs that provide a flexible framework for representing complex evolutionary histories that involve reticulate evolutionary events. Recently phylogenetic studies have started to focus on a special class of such networks called {\em semi-directed networks}. These graphs are defined as mixed graphs that can be obtained by de-orienting some of the arcs in some {\em rooted phylogenetic network}, that is, a directed acyclic graph whose leaves correspond to a collection of species and that has a single source or root vertex. However, this definition of semi-directed networks is implicit in nature since it is not clear when a mixed-graph enjoys this property or not. In this paper, we introduce novel, explicit mathematical characterizations of semi-directed networks, and also multi-semi-directed networks, that is mixed graphs that can be obtained from directed phylogenetic networks that may have more than one root. In addition, through extending foundational tools from the theory of rooted networks into the semi-directed setting — such as cherry picking sequences, omnians, and path partitions — we characterize when a (multi-)semi-directed network can be obtained by de-orienting some rooted network that is contained in one of the well-known classes of tree-child, orchard, tree-based or forest-based networks. These results address structural aspects of (multi-)semi-directed networks and pave the way to improved theoretical and computational analyses of such networks, for example, within the development of algebraic evolutionary models that are based on such networks.

Item Type:	Article
Uncontrolled Keywords:	mixed graph,semi-directed phylogenetic network,tree-based network,tree-child network,orchard network,path partitions
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
Depositing User:	LivePure Connector
Date Deposited:	18 Dec 2025 10:30
Last Modified:	18 Dec 2025 10:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/101460
DOI:	issn:1431-7613

Actions (login required)

View Item