The parental parsimony problem on binary, tree-child phylogenetic networks

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.