Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
Abstract
Maximum compatibility provides a criterion for phylogenetic reconstruction in which the objective is to retain a maximum set of mutually compatible characters. For binary characters, pairwise compatibility can be represented by a weighted graph whose vertices correspond to characters and whose edges connect compatible pairs. A leading algorithm by Cherry [BMC Bioinformatics, 18(1):127, 2017] uses this representation to identify maximum compatible character sets as maximum weight cliques. We formulate the problem as maximum weight independent set enumeration on the complement graph and use deterministic postprocessing to map sampled bit strings to maximal feasible solutions. To explore the prospects of quantum computational advantage, we further construct bespoke correction-in-the-loop Quantum Approximate Optimisation Algorithm instances and find that traditional Lagrange multiplier choices may not be optimal for the enumeration problem on noisy devices. We also introduce lossless graph reductions with reconstruction rules that preserve the complete set of optimal solutions. Our results indicate that graph reduction and sampling can be effectively combined to address the enumeration bottleneck in maximum compatibility phylogeny, while retaining exact reconstruction when the residual optimum set is completely resolved. We enhance Cherry's approach to maximum compatibility by introducing graph reduction techniques and quantum sampling. Our classical benchmarks show a clear difference between finding one optimum and recovering the optimum set in practice. We demonstrate the utility of our methods on graphs constructed from SARS-CoV-2 sequences.
Related
- Phylogeny of Termites Inferred from Mitogenomic Data with a Large Taxon Sampling
- Lossless compression of protein databases for efficient and accurate metagenomic sequence classification with Centrifuger
- Phylogeny is not taxonomy: lessons on higher classification from turtle and whale barnacles (Cirripedia: Coronuloidea)
- State of knowledge on the diversity, phylogeny and distribution of Inocybaceae in Africa
- Phylogeny of Mastigitae sheds light on a hundred‐million‐year‐long morphological stasis of the extant genus Clidicus Laporte (Coleoptera: Staphylinidae: Scydmaeninae)
BibTeX
@misc{ye2026lossless,
title = {{Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion}},
author = {Orson Ye and James Bonfield and Joshua Cudby and Richard Durbin and Sergii Strelchuk},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18029},
eprint = {2610.18029},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18029},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
AU - Orson Ye
AU - James Bonfield
AU - Joshua Cudby
AU - Richard Durbin
AU - Sergii Strelchuk
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18029
UR - https://arxiv.org/abs/2610.18029
AB - Maximum compatibility provides a criterion for phylogenetic reconstruction in which the objective is to retain a maximum set of mutually compatible characters. For binary characters, pairwise compatibility can be represented by a weighted graph whose vertices correspond to characters and whose edges connect compatible pairs. A leading algorithm by Cherry [BMC Bioinformatics, 18(1):127, 2017] uses this representation to identify maximum compatible character sets as maximum weight cliques. We formulate the problem as maximum weight independent set enumeration on the complement graph and use deterministic postprocessing to map sampled bit strings to maximal feasible solutions. To explore the prospects of quantum computational advantage, we further construct bespoke correction-in-the-loop Quantum Approximate Optimisation Algorithm instances and find that traditional Lagrange multiplier choices may not be optimal for the enumeration problem on noisy devices. We also introduce lossless graph reductions with reconstruction rules that preserve the complete set of optimal solutions. Our results indicate that graph reduction and sampling can be effectively combined to address the enumeration bottleneck in maximum compatibility phylogeny, while retaining exact reconstruction when the residual optimum set is completely resolved. We enhance Cherry's approach to maximum compatibility by introducing graph reduction techniques and quantum sampling. Our classical benchmarks show a clear difference between finding one optimum and recovering the optimum set in practice. We demonstrate the utility of our methods on graphs constructed from SARS-CoV-2 sequences.
ER -