Katarzyna Nałęcz-Charkiewicz
supervisor: Robert Nowak
De novo assembly is an inherent step in sequencing the genomes of new organisms and studying structural genomic changes. The currently used methods of assembling readings from sequencers by their computational requirements are currently a bottleneck in the entire processing process, implying the need to develop more efficient algorithms. One possible approach, which is still little explored, is the use of quantum computing.
We present the PoC of de novo assembly algorithm, using the formulation of the assembly problem as an optimization task. Namely, for each pair of DNA reads, previously converted to signals, the Pearson cross-correlation coefficient is computed. The problem of sequence assembly in such a defined task comes down to the problem of finding in the similarity matrix a path meeting the minimum distance criterion (Traveling Salesperson Problem). Computations performed for artificial and real DNA sequences on a classical computer were compared with the results obtained by a hybrid method combining CPU and QPU (quantum annealer by D-Wave company) calculations. The solution was scaled to the size of viral genomes.
The research results are promising and allow us to hope to use the quantum computing paradigm as an alternative to computing performed on the GPU or High Performance Computing.