A 2-approximation algorithm for the softwired parsimony problem on binary, tree-child phylogenetic networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
Bounding the softwired parsimony score of a phylogenetic network
In comparison to phylogenetic trees, phylogenetic networks are more suitable to represent complex evolutionary histories of species whose past includes reticulation such as hybridisation or lateral gene transfer. However…
Defining binary phylogenetic trees using parsimony
Phylogenetic (i.e. leaf-labeled) trees play a fundamental role in evolutionary research. A typical problem is to reconstruct such trees from data like DNA alignments (whose columns are often referred to as characters), a…
A linear bound on the number of states in optimal convex characters for maximum parsimony distance
Given two phylogenetic trees on the same set of taxa X, the maximum parsimony distance d_MP is defined as the maximum, ranging over all characters c on X, of the absolute difference in parsimony score induced by c on the…
External Clustering Validation by the Homogeneity-Parsimony Trade-off
Scalar metrics are often used to evaluate clusterings against known classes, but they can obscure a fundamental trade-off: clusterings should be informative about class labels while avoiding unnecessary fragmentation. He…
Defining binary phylogenetic trees using parsimony: new bounds
Phylogenetic trees are frequently used to model evolution. Such trees are typically reconstructed from data like DNA, RNA, or protein alignments using methods based on criteria like maximum parsimony (amongst others). Ma…
2k4k