Algorithm for DNA sequence assembly by quantum annealing
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 of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2022-04-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s12859-022-04661-7 |
| _version_ | 1811290462213898240 |
|---|---|
| author | Katarzyna Nałęcz-Charkiewicz Robert M. Nowak |
| author_facet | Katarzyna Nałęcz-Charkiewicz Robert M. Nowak |
| author_sort | Katarzyna Nałęcz-Charkiewicz |
| collection | DOAJ |
| description | 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 of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. Results We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. Conclusions Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph). |
| first_indexed | 2024-04-13T04:13:17Z |
| format | Article |
| id | doaj.art-839d47f6b18e47e5a2bce09ba40fdb44 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-13T04:13:17Z |
| publishDate | 2022-04-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-839d47f6b18e47e5a2bce09ba40fdb442022-12-22T03:03:03ZengBMCBMC Bioinformatics1471-21052022-04-0123111710.1186/s12859-022-04661-7Algorithm for DNA sequence assembly by quantum annealingKatarzyna Nałęcz-Charkiewicz0Robert M. Nowak1Institute of Computer Science, Warsaw University of TechnologyInstitute of Computer Science, Warsaw University of TechnologyAbstract 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 of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. Results We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. Conclusions Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).https://doi.org/10.1186/s12859-022-04661-7De novo assemblyQuantum annealingHybrid algorithmTravelling salesman problemTSPVehicle routing problem |
| spellingShingle | Katarzyna Nałęcz-Charkiewicz Robert M. Nowak Algorithm for DNA sequence assembly by quantum annealing BMC Bioinformatics De novo assembly Quantum annealing Hybrid algorithm Travelling salesman problem TSP Vehicle routing problem |
| title | Algorithm for DNA sequence assembly by quantum annealing |
| title_full | Algorithm for DNA sequence assembly by quantum annealing |
| title_fullStr | Algorithm for DNA sequence assembly by quantum annealing |
| title_full_unstemmed | Algorithm for DNA sequence assembly by quantum annealing |
| title_short | Algorithm for DNA sequence assembly by quantum annealing |
| title_sort | algorithm for dna sequence assembly by quantum annealing |
| topic | De novo assembly Quantum annealing Hybrid algorithm Travelling salesman problem TSP Vehicle routing problem |
| url | https://doi.org/10.1186/s12859-022-04661-7 |
| work_keys_str_mv | AT katarzynanałeczcharkiewicz algorithmfordnasequenceassemblybyquantumannealing AT robertmnowak algorithmfordnasequenceassemblybyquantumannealing |