A near-linear kernel for bounded-state parsimony distance

Elise Deen; Leo van Iersel; Remie Janssen; Mark Jones; Yukihiro Murakami; Norbert Zeh

doi:10.1016/j.jcss.2023.103477

A near-linear kernel for bounded-state parsimony distance

Elise Deen, Leo van Iersel, Remie Janssen, Mark Jones^*, Yukihiro Murakami, Norbert Zeh

^*Corresponding author for this work

Discrete Mathematics and Optimization

Research output: Contribution to journal › Article › Scientific › peer-review

24 Downloads (Pure)

Abstract

The maximum parsimony distance d_MP(T₁,T₂) and the bounded-state maximum parsimony distance d_MP^t(T₁,T₂) measure the difference between two phylogenetic trees T₁,T₂ in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of d_MP^t(T₁,T₂)). While computing d_MP(T₁,T₂) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for d_MP^t(T₁,T₂). In this paper, we prove that computing d_MP^t(T₁,T₂) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(klg⁡k), where k=d_MP^t(T₁,T₂). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.

Original language	English
Article number	103477
Number of pages	21
Journal	Journal of Computer and System Sciences
Volume	140
DOIs	https://doi.org/10.1016/j.jcss.2023.103477
Publication status	Published - 2024

Keywords

Distance measure
Kernelization
Maximum parsimony distance
Parameterized complexity
Parsimony
Phylogenetic tree
Phylogenetics

Access to Document

10.1016/j.jcss.2023.103477

1-s2.0-S002200002300082X-mainFinal published version, 669 KBLicence: CC BY

Cite this

@article{53f5717cd13d4b44a7da498d6d2b7c6d,

title = "A near-linear kernel for bounded-state parsimony distance",

abstract = "The maximum parsimony distance dMP(T1,T2) and the bounded-state maximum parsimony distance dMPt(T1,T2) measure the difference between two phylogenetic trees T1,T2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of dMPt(T1,T2)). While computing dMP(T1,T2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for dMPt(T1,T2). In this paper, we prove that computing dMPt(T1,T2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(klg⁡k), where k=dMPt(T1,T2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.",

keywords = "Distance measure, Kernelization, Maximum parsimony distance, Parameterized complexity, Parsimony, Phylogenetic tree, Phylogenetics",

author = "Elise Deen and {van Iersel}, Leo and Remie Janssen and Mark Jones and Yukihiro Murakami and Norbert Zeh",

year = "2024",

doi = "10.1016/j.jcss.2023.103477",

language = "English",

volume = "140",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press",

}

TY - JOUR

T1 - A near-linear kernel for bounded-state parsimony distance

AU - Deen, Elise

AU - van Iersel, Leo

AU - Janssen, Remie

AU - Jones, Mark

AU - Murakami, Yukihiro

AU - Zeh, Norbert

PY - 2024

Y1 - 2024

N2 - The maximum parsimony distance dMP(T1,T2) and the bounded-state maximum parsimony distance dMPt(T1,T2) measure the difference between two phylogenetic trees T1,T2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of dMPt(T1,T2)). While computing dMP(T1,T2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for dMPt(T1,T2). In this paper, we prove that computing dMPt(T1,T2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(klg⁡k), where k=dMPt(T1,T2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.

AB - The maximum parsimony distance dMP(T1,T2) and the bounded-state maximum parsimony distance dMPt(T1,T2) measure the difference between two phylogenetic trees T1,T2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of dMPt(T1,T2)). While computing dMP(T1,T2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for dMPt(T1,T2). In this paper, we prove that computing dMPt(T1,T2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(klg⁡k), where k=dMPt(T1,T2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.

KW - Distance measure

KW - Kernelization

KW - Maximum parsimony distance

KW - Parameterized complexity

KW - Parsimony

KW - Phylogenetic tree

KW - Phylogenetics

UR - http://www.scopus.com/inward/record.url?scp=85173513897&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2023.103477

DO - 10.1016/j.jcss.2023.103477

M3 - Article

AN - SCOPUS:85173513897

SN - 0022-0000

VL - 140

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

M1 - 103477

ER -

A near-linear kernel for bounded-state parsimony distance

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this