Algorithm for DNA sequence assembly by quantum annealing

• DOI: 10.1186/s12859-022-04661-7
• Publication Date: 2022-04-07T12:05:24Z
• Authors: Katarzyna Nałęcz-...; Robert M. Nowak
• Keywords: Sequence assembly

Abstract Background The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development next-generation (NGS) methods raises hopes for making whole-genome a fast reliable tool used, example, medical diagnostics. However, this hampered by slowness computational requirements current processing algorithms, which need to develop more efficient algorithms. One possible approach, still little explored, use quantum computing. Results We present proof concept de novo algorithm, using Genomic Signal Processing detecting overlaps between DNA reads calculating Pearson correlation coefficient formulating problem as optimization (Traveling Salesman Problem). Computations performed on classic computer were compared with results achieved hybrid method combining CPU QPU calculations. For purpose annealer D-Wave was used. experiments artificially generated data coming from simulator, actual organism used input sequences. To our knowledge, work one few where sequences study annealer. Conclusions Proof carried out us showed that (QA) might be promising alternative computations classical model. computing power available devices requires approach (combining computations). next may developing algorithm strictly dedicated task, its specificity (e.g. sparsity bounded degree overlap-layout-consensus graph).