[Submitted on 25 Jun 2026]

View PDF

Abstract:Phylogenetic reconstruction is one of the major challenges in computational biology. Among existing reconstruction methods for phylogenetic networks, an important subtask emerges in extending a leaf-labelling on a phylogenetic network to determine a most parsimonious tree inside the network. There exist different variants of this subtask depending on the biological model assumptions for which distinct evolutionary phenomena are captured by the network. In this article we assume that next to hybridization or recombination events, also allopolyploidy or incomplete lineage sorting are present. Then, finding the most parsimonious tree inside the network is called the parental parsimony score problem (PPS), a NP-hard combinatorial optimization problem. We provide the first constant-factor approximation for the PPS on arbitrary but fixed leaf labels and a class of networks on which the PPS remains NP-hard, namely binary, semi-simplex, tree-child phylogenetic networks. Furthermore, we introduce a novel exact solution algorithm for the PPS on binary, tree-child phylogenetic networks and analyze its performance on simulated data.

Submission history

From: Martin Frohn [view email]
[v1] Thu, 25 Jun 2026 11:57:03 UTC (5,431 KB)

Current browse context:

math.OC

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.