Scalable Guide Tree Construction Using Quantum Annealing for 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. By utilizing quantum algorithms, such as quantum annealing, we can overcome the problem of local minima that occurs in greedy methods. We propose a scalable guide tree algorithm that achieves scalability through quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we directly map the minimum evolution problem to a traveling salesperson problem (TSP), which quantum annealing can solve efficiently. The TSP solution enables the guide tree to be constructed in linear time using the molecular clock. Even with only a single sample from a D-Wave hybrid solver, our guide tree generally performed comparably to classical trees on the BAliBASE 3.0 benchmark. With a single iterative refinement, no statistically significant performance differences were found between our method and classical guide trees. Our scalable guide tree algorithm is practical in the sense that only a single sampling can be enough for constructing a good guide tree. Further performance analysis requires larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. While the practical application of quantum algorithms in bioinformatics has been relatively overlooked, this study highlights the potential of quantum algorithms for targeting computational bottlenecks in the field.