Quantum-Classical Synergy: Enhancing De Novo Genome Assembly with Hybridized QUBO Optimization

The difficult computational task of de novo genome assembly is to piece together the original DNA sequence from a collection of overlapping pieces. The issue can be expressed as an NP-hard quadratic unconstrained binary optimization (QUBO) problem. To solve QUBO problems more effectively than conventional techniques, quantum computing presents a viable alternative. This is because quantum annealers and gate-based quantum algorithms may take advantage of quantum effects like superposition and entanglement. But there are drawbacks to quantum computing as well, such scalability, noise, and decoherence. In this work, we present a hybrid quantum-classical optimization algorithm that solves the QUBO problem of de novo genome assembly by utilizing the advantages of both paradigms. To find near-optimal solutions in the presence of defects and noise, our technique combines a classical local search heuristic with a quantum approximate optimization algorithm (QAOA). We assess our algorithm's performance against current quantum and conventional approaches using both artificial and actual data sets. We demonstrate that our algorithm can outperform the state-of-the-art methods in terms of accuracy and computing cost, and it has the potential to solve intricate and large-scale genome assembly challenges.