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.
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.
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.
We propose a modified MSA algorithm on quantum annealers with applications in areas of bioinformatics and genetic sequencing.To understand the human genome, researchers compare extensive sets of these genetic sequences -or their protein counterparts -to identify patterns.This comparison begins with the alignment of the set of (multiple) sequences.However, this alignment problem is considered nondeterministically-polynomial time complete and, thus, current classical algorithms at best rely on brute force or heuristic methods to find solutions.Quantum annealing algorithms are able to bypass this need for sheer brute force due to their use of quantum mechanical properties.However, due to the novelty of these algorithms, many are rudimentary in nature and limited by hardware restrictions.We apply progressive alignment techniques to modify annealing algorithms, achieving a linear reduction in spin usage whilst introducing more complex heuristics to the algorithm.This opens the door for further exploration into quantum computing-based bioinformatics, potentially allowing for a deeper understanding of disease detection and monitoring.
Abstract Quantum computing applies principles of quantum mechanics, such as superposition and entanglement, to process information with exponential parallelism. This paradigm offers significant computational advantages over classical methods, particularly for NP-hard problems like phylogenetic tree reconstruction in evolutionary biology. Phylogenetic trees model the evolutionary relationships among species or genes, and their reconstruction is computationally challenging as the number of possible topologies grows exponentially with the number of taxa. To address this, biologists often rely on heuristic methods; however, recent work has shown that recursive graph-cut techniques can achieve high accuracy in phylogenetic inference, though at high computational cost. In this study, we present a quantum algorithm based on the normalized cut ( Ncut N cut ) criterion, enabling efficient recursive graph partitioning. Implemented using Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), demonstrating promising results on real quantum hardware for complex bioinformatics tasks.
Bioinformatics workloads -- including protein structure prediction, molecular dynamics simulation, genomic sequencealignment, and phylogenetic tree reconstruction -- are among the most computationally intensive problems in science,with many exhibiting exponential or combinatorial scaling that overwhelms classical high-performance computing.Quantum computing, leveraging superposition and entanglement to explore exponentially large solution spaces,promises polynomial or exponential speedups for specific bioinformatics tasks. However, current noisyintermediate-scale quantum (NISQ) devices (50-1,000+ qubits, high error rates) are far from fault-tolerant quantumcomputers, and the practical quantum advantage for bioinformatics remains undemonstrated. This study systematicallybenchmarked five computational approaches -- classical exact algorithms, classical heuristics (genetic algorithm,simulated annealing), GPU-accelerated methods, variational quantum algorithms (VQE, QAOA) on NISQ hardware, anda proposed hybrid quantum-classical bioinformatics pipeline (HQC-Bio) combining quantum subroutines for combinatorialsubproblems with classical pre/post-processing -- across four bioinformatics tasks: multiple sequence alignment (MSA, n= 500 protein families), protein folding on lattice models (HP model, chains 20-60 residues), molecular docking scoring(1,000 ligand-receptor pairs), and phylogenetic tree search (taxa sets 10-50). HQC-Bio achieved the highest solutionquality for protein folding (optimal energy found in 84.6% of 40-residue instances vs 62.4% for simulated annealing; p <0.001) and phylogenetic search (log-likelihood within 0.2% of exact ML for 30-taxa trees vs 1.8% for RAxML heuristic).However, quantum wall-clock time exceeded classical GPU by 12-340x due to NISQ hardware overhead (circuitcompilation, shot noise, error mitigation), establishing that current quantum advantage is in solution quality rather thanspeed. Resource estimation projects that fault-tolerant quantum computers with 10,000-100,000 logical qubits couldachieve genuine speedups of 10-1,000x for these tasks within 10-15 years.
Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. However, Benchmarking processes most often vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms additionally poses a challenge, especially in the comparison to classical algorithms. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. Finally, the proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
Combinatorial optimization is a foundation of numerous scientific, industrial, and social decision-making questions, but its usefulness is mostly restricted by the exponential complexity of the problem of classical computability. The quantum annealing (QA) has become one of the leading analogue quantum systems to address such problems, whereby optimization problems are converted into physical energy structures and quantum fluctuations are utilized to perform systematic exploration. It provides a critical, synthesized, and comprehensive review of quantum annealing as applied to combinatorial optimization, including the theoretical basis, hardware designs, algorithm methods, issues of embedding and encoding, benchmarking procedures, applications, and integration with quantum algorithms based on gates and solvers on a classical computer. We build a comprehensive taxonomy between adiabatic dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to state-of-the-art flux-qubit annealers, new architectures, and hybrid quantum classical pipelines. We show that the overhead of embedding and encoding and the benchmarking approach taken are the most significant factors in determining scalability and performance, but not the raw number of qubits. Transportation, energy systems, robotics, finance, pharmacological discovery, and machine learning are just some examples of the domain-specific case studies that use QA with minimal empirical utility as a hybrid refinement engine and not an independent solver. Moreover, we introduce a stringent evaluation of the existing benchmarking culture, clarify the causal links between QA and QAOA as well as between VQE and structural predicaments, and reveal the institutional roots of the existing restrictions. We conclude by identifying a research roadmap in the future, focusing on the annealing hardness characterization, Stoquastic control manipulation, embedding rules automation, architecture design, and development of principled quantum advantage. It creates a benchmark reference to those in the field and research and deployment of scalable, reliable, and application-relevant quantum optimization