Minimum evolution molecular clock: quantum annealing for guide tree construction in multiple sequence alignment

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. 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. 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.