Minimum evolution molecular clock: quantum annealing for guide tree construction in multiple sequence alignment
- 1Department of Chemistry, Yonsei University, Seoul, 03722 Republic of Korea
- 2Department of Semiconductor Convergence Engineering, Sungkyunkwan University, Suwon, 16419 Republic of Korea
- 3Department of Quantum Information, Yonsei University, Incheon, 21983 Republic of Korea
Abstract
Background: Multiple sequence alignment (MSA) reveals homology in biological sequences, which is crucial for phylogenetics, medicine, and molecular biology. Many heuristic MSA algorithms use guide trees to determine sequence alignment order, but finding an optimal guide tree is an NP-hard problem. Conventional guide tree algorithms are greedy heuristics designed for better scalability at the cost of accuracy. Due to the NP-hardness of guide tree construction, it is desirable to explore the utility of quantum algorithms such as quantum annealing.
Results: We propose a guide tree construction algorithm that utilizes quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we reformulate the minimum evolution problem as a traveling salesperson problem (TSP), which quantum annealing can target. The TSP solution enables the guide tree to be constructed with linear time overhead using the molecular clock. We used the Concorde TSP solver and D-Wave’s quantum-classical hybrid solvers to demonstrate the results instead of native QPU annealing alone, due to limitations in current quantum hardware. Benchmarking on BAliBASE 3.0 showed no statistically significant differences in alignment scores between our method and classical guide trees. When Concorde was used, the empirical wall-clock time scaling of our method was better than that of the textbook UPGMA implementation.
Conclusions: Classical TSP solvers allow practical implementation of our method for small-scale guide trees, while larger problems motivate the use of quantum annealing. Further performance analysis should be conducted on larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. This study highlights the potential of quantum algorithms for targeting computational bottlenecks in MSA.
Supplementary Information: The online version contains supplementary material available at https://doi.org/10.1186/s12859-026-06558-1.
Related
- ROMET-RNA benchmarks and selects RNA 3D structures using multiple predictors and alignment strategies
- From molecular evolution to biobricks and synthetic modules: a lesson by the bacterial flagellum.
- Evolution of KRAS molecular glues: from allele-selective to Pan-RAS and protein–protein interaction modulators
- Molecular Mechanisms of Natural Saponins in Treating Acute Lung Injury: Systemic Regulatory Roles Involving Multiple Cell Types and Signaling Pathways
- The assembled catalytic triad of Ideonella sakaiensis PETase is metastable in apo molecular dynamics simulations across multiple control conditions
BibTeX
@article{park2026minimum,
title = {{Minimum evolution molecular clock: quantum annealing for guide tree construction in multiple sequence alignment}},
author = {Youngjun Park and Juhyeon Kim and Joonsuk Huh},
journal = {BMC Bioinformatics},
year = {2026},
month = aug,
doi = {10.1186/s12859-026-06558-1},
url = {https://doi.org/10.1186/s12859-026-06558-1},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - JOUR
TI - Minimum evolution molecular clock: quantum annealing for guide tree construction in multiple sequence alignment
AU - Youngjun Park
AU - Juhyeon Kim
AU - Joonsuk Huh
PY - 2026
DA - 2026/08/01
JO - BMC Bioinformatics
DO - 10.1186/s12859-026-06558-1
UR - https://doi.org/10.1186/s12859-026-06558-1
AB - Background: Multiple sequence alignment (MSA) reveals homology in biological sequences, which is crucial for phylogenetics, medicine, and molecular biology. Many heuristic MSA algorithms use guide trees to determine sequence alignment order, but finding an optimal guide tree is an NP-hard problem. Conventional guide tree algorithms are greedy heuristics designed for better scalability at the cost of accuracy. Due to the NP-hardness of guide tree construction, it is desirable to explore the utility of quantum algorithms such as quantum annealing. Results: We propose a guide tree construction algorithm that utilizes quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we reformulate the minimum evolution problem as a traveling salesperson problem (TSP), which quantum annealing can target. The TSP solution enables the guide tree to be constructed with linear time overhead using the molecular clock. We used the Concorde TSP solver and D-Wave’s quantum-classical hybrid solvers to demonstrate the results instead of native QPU annealing alone, due to limitations in current quantum hardware. Benchmarking on BAliBASE 3.0 showed no statistically significant differences in alignment scores between our method and classical guide trees. When Concorde was used, the empirical wall-clock time scaling of our method was better than that of the textbook UPGMA implementation. Conclusions: Classical TSP solvers allow practical implementation of our method for small-scale guide trees, while larger problems motivate the use of quantum annealing. Further performance analysis should be conducted on larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. This study highlights the potential of quantum algorithms for targeting computational bottlenecks in MSA. Supplementary Information: The online version contains supplementary material available at https://doi.org/10.1186/s12859-026-06558-1.
SN - 1471-2105
ER -