.png){kind=icon}
.png){kind=icon}
Return
A 2-approximation algorithm for the softwired parsimony problem on binary, tree-child phylogenetic networks
.png){kind=icon}
OA
AI
DOI：10.1007/s10479-024-06452-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Finding the most parsimonious tree inside a phylogenetic network with respect to a given character is an NP-hard combinatorial optimization problem that for many network topologies is essentially inapproximable. In contrast, if the network is a rooted tree, then Fitch's well-known algorithm calculates an optimal parsimony score for that character in polynomial time. Drawing inspiration from this we here introduce a new extension of Fitch's algorithm which runs in polynomial time and ensures an approximation factor of 2 on binary, tree-child phylogenetic networks, a popular topologically-restricted subclass of phylogenetic networks in the literature. Specifically, we show that Fitch's algorithm can be seen as a primal-dual algorithm, how it can be extended to binary, tree-child networks and that the approximation guarantee of this extension is tight. These results for a classic problem in phylogenetics strengthens the link between polyhedral methods and phylogenetics and can aid in the study of other related optimization problems on phylogenetic networks.
Keywords:
Combinatorial optimization
Integer programming
Approximation algorithms
Phylogenetics
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W