Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods Article Swipe

PDF

Jiawei Zhang , Yibo Chen , Jun-Han Huang ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2508.00468

The maximum parsimony phylogenetic tree reconstruction problem is NP-hard, presenting a computational bottleneck for classical computing and motivating the exploration of emerging paradigms like quantum computing. To this end, we design three optimization models compatible with both classical and quantum solvers. Our method directly searches the complete solution space of all possible tree topologies and ancestral states, thereby avoiding the potential biases associated with pre-constructing candidate internal nodes. Among these models, the branch-based model drastically reduces the number of variables and explicit constraints through a specific variable definition, providing a novel modeling approach effective not only for phylogenetic tree building but also for other tree problems. The correctness of this model is validated with a classical solver, which obtains solutions that are generally better than those from heuristics on the GAPDH gene dataset. Moreover, our quantum simulations successfully find the exact optimal solutions for small-scale instances with rapid convergence, highlighting the potential of quantum computing to offer a new avenue for solving these intractable problems in evolutionary biology.

Related Topics

Statistical Inference

Paleocene–Eocene Thermal Maximum

Concepts

No concepts available.

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2508.00468
PDF: https://arxiv.org/pdf/2508.00468
OA Status: green
OpenAlex ID: https://openalex.org/W4416551351

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4416551351

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2508.00468

Digital Object Identifier
Title: Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-08-01

Full publication date if available
Authors: Jiawei Zhang, Yibo Chen, Jun-Han Huang

List of authors in order
Landing page: https://arxiv.org/abs/2508.00468

Publisher landing page
PDF URL: https://arxiv.org/pdf/2508.00468

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2508.00468

Direct OA link when available
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W4416551351
doi	https://doi.org/10.48550/arxiv.2508.00468
ids.doi	https://doi.org/10.48550/arxiv.2508.00468
ids.openalex	https://openalex.org/W4416551351
fwci
type	preprint
title	Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
language	en
locations[0].id	pmh:oai:arXiv.org:2508.00468
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2508.00468
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2508.00468
locations[1].id	doi:10.48550/arxiv.2508.00468
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2508.00468
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5100462839
authorships[0].author.orcid	https://orcid.org/0000-0002-7207-2965
authorships[0].author.display_name	Jiawei Zhang
authorships[0].author_position	first
authorships[0].raw_author_name	Zhang, Jiawei
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5100722128
authorships[1].author.orcid	https://orcid.org/0000-0002-0178-9715
authorships[1].author.display_name	Yibo Chen
authorships[1].author_position	middle
authorships[1].raw_author_name	Chen, Yibo
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5017886264
authorships[2].author.orcid	https://orcid.org/0000-0003-3654-861X
authorships[2].author.display_name	Jun-Han Huang
authorships[2].author_position	middle
authorships[2].raw_author_name	Huang, Jun-Han
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2508.00468
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods
has_fulltext	False
is_retracted	False
updated_date	2025-11-28T17:09:12.488805
primary_topic
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2508.00468
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2508.00468
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2508.00468
primary_location.id	pmh:oai:arXiv.org:2508.00468
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2508.00468
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2508.00468
publication_date	2025-08-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	10, 84, 89, 114, 157
abstract_inverted_index.To	26
abstract_inverted_index.in	165
abstract_inverted_index.is	7, 111
abstract_inverted_index.of	20, 49, 78, 108, 152
abstract_inverted_index.on	128
abstract_inverted_index.to	155
abstract_inverted_index.we	29
abstract_inverted_index.Our	41
abstract_inverted_index.The	0, 106
abstract_inverted_index.all	50
abstract_inverted_index.and	16, 38, 54, 80
abstract_inverted_index.are	121
abstract_inverted_index.but	100
abstract_inverted_index.for	13, 96, 102, 143, 160
abstract_inverted_index.new	158
abstract_inverted_index.not	94
abstract_inverted_index.our	134
abstract_inverted_index.the	18, 45, 59, 71, 76, 129, 139, 150
abstract_inverted_index.also	101
abstract_inverted_index.both	36
abstract_inverted_index.end,	28
abstract_inverted_index.find	138
abstract_inverted_index.from	126
abstract_inverted_index.gene	131
abstract_inverted_index.like	23
abstract_inverted_index.only	95
abstract_inverted_index.than	124
abstract_inverted_index.that	120
abstract_inverted_index.this	27, 109
abstract_inverted_index.tree	4, 52, 98, 104
abstract_inverted_index.with	35, 63, 113, 146
abstract_inverted_index.Among	68
abstract_inverted_index.GAPDH	130
abstract_inverted_index.exact	140
abstract_inverted_index.model	73, 110
abstract_inverted_index.novel	90
abstract_inverted_index.offer	156
abstract_inverted_index.other	103
abstract_inverted_index.rapid	147
abstract_inverted_index.space	48
abstract_inverted_index.these	69, 162
abstract_inverted_index.those	125
abstract_inverted_index.three	31
abstract_inverted_index.which	117
abstract_inverted_index.avenue	159
abstract_inverted_index.better	123
abstract_inverted_index.biases	61
abstract_inverted_index.design	30
abstract_inverted_index.method	42
abstract_inverted_index.models	33
abstract_inverted_index.nodes.	67
abstract_inverted_index.number	77
abstract_inverted_index.maximum	1
abstract_inverted_index.models,	70
abstract_inverted_index.obtains	118
abstract_inverted_index.optimal	141
abstract_inverted_index.problem	6
abstract_inverted_index.quantum	24, 39, 135, 153
abstract_inverted_index.reduces	75
abstract_inverted_index.solver,	116
abstract_inverted_index.solving	161
abstract_inverted_index.states,	56
abstract_inverted_index.thereby	57
abstract_inverted_index.through	83
abstract_inverted_index.NP-hard,	8
abstract_inverted_index.approach	92
abstract_inverted_index.avoiding	58
abstract_inverted_index.biology.	167
abstract_inverted_index.building	99
abstract_inverted_index.complete	46
abstract_inverted_index.dataset.	132
abstract_inverted_index.directly	43
abstract_inverted_index.emerging	21
abstract_inverted_index.explicit	81
abstract_inverted_index.internal	66
abstract_inverted_index.modeling	91
abstract_inverted_index.possible	51
abstract_inverted_index.problems	164
abstract_inverted_index.searches	44
abstract_inverted_index.solution	47
abstract_inverted_index.solvers.	40
abstract_inverted_index.specific	85
abstract_inverted_index.variable	86
abstract_inverted_index.Moreover,	133
abstract_inverted_index.ancestral	55
abstract_inverted_index.candidate	65
abstract_inverted_index.classical	14, 37, 115
abstract_inverted_index.computing	15, 154
abstract_inverted_index.effective	93
abstract_inverted_index.generally	122
abstract_inverted_index.instances	145
abstract_inverted_index.paradigms	22
abstract_inverted_index.parsimony	2
abstract_inverted_index.potential	60, 151
abstract_inverted_index.problems.	105
abstract_inverted_index.providing	88
abstract_inverted_index.solutions	119, 142
abstract_inverted_index.validated	112
abstract_inverted_index.variables	79
abstract_inverted_index.associated	62
abstract_inverted_index.bottleneck	12
abstract_inverted_index.compatible	34
abstract_inverted_index.computing.	25
abstract_inverted_index.heuristics	127
abstract_inverted_index.motivating	17
abstract_inverted_index.presenting	9
abstract_inverted_index.topologies	53
abstract_inverted_index.constraints	82
abstract_inverted_index.correctness	107
abstract_inverted_index.definition,	87
abstract_inverted_index.drastically	74
abstract_inverted_index.exploration	19
abstract_inverted_index.intractable	163
abstract_inverted_index.simulations	136
abstract_inverted_index.small-scale	144
abstract_inverted_index.branch-based	72
abstract_inverted_index.convergence,	148
abstract_inverted_index.evolutionary	166
abstract_inverted_index.highlighting	149
abstract_inverted_index.optimization	32
abstract_inverted_index.phylogenetic	3, 97
abstract_inverted_index.successfully	137
abstract_inverted_index.computational	11
abstract_inverted_index.reconstruction	5
abstract_inverted_index.pre-constructing	64
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile