A 2-approximation algorithm for the softwired parsimony problem on binary, tree-child phylogenetic networks

Martin Frohn () and Steven Kelk ()
Additional contact information
Martin Frohn: Maastricht University
Steven Kelk: Maastricht University

Annals of Operations Research, 2025, vol. 345, issue 1, No 5, 125-145

Abstract: Abstract 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 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06452-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:345:y:2025:i:1:d:10.1007_s10479-024-06452-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06452-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().