{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T21:30:02Z","timestamp":1781818202460,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>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.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>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.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>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).<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s12859-022-04661-7","type":"journal-article","created":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:05:24Z","timestamp":1649333124000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Algorithm for DNA sequence assembly by quantum annealing"],"prefix":"10.1186","volume":"23","author":[{"given":"Katarzyna","family":"Na\u0142\u0119cz-Charkiewicz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert M.","family":"Nowak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,7]]},"reference":[{"key":"4661_CR1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbw096","author":"J-I Sohn","year":"2016","unstructured":"Sohn J-I, Nam J-W. The present and future of de novo whole-genome assembly. Brief Bioinform. 2016. https:\/\/doi.org\/10.1093\/bib\/bbw096.","journal-title":"Brief Bioinform"},{"key":"4661_CR2","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD, editors. Complexity of computer computations. Boston: Springer; 1972. p. 85\u2013103. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9."},{"key":"4661_CR3","doi-asserted-by":"publisher","DOI":"10.5772\/12909","volume-title":"Traveling salesman problem, theory and applications","author":"R Matai","year":"2010","unstructured":"Matai R, Singh S, Lal M. Traveling salesman problem: an overview of applications, formulations, and solution approaches. In: Davendra D, editor. Traveling salesman problem, theory and applications. London: InTech Press; 2010. https:\/\/doi.org\/10.5772\/12909."},{"key":"4661_CR4","first-page":"223","volume":"9","author":"S-L Peng","year":"2008","unstructured":"Peng S-L, Chang C-S, Hunag J, Wang T-C. A grid-based TSP solver with applications to bioinformatics. J Internet Technol. 2008;9:223\u20138.","journal-title":"J Internet Technol"},{"issue":"5","key":"4661_CR5","doi-asserted-by":"publisher","first-page":"5355","DOI":"10.1103\/physreve.58.5355","volume":"58","author":"T Kadowaki","year":"1998","unstructured":"Kadowaki T, Nishimori H. Quantum annealing in the transverse Ising model. Phys Rev E. 1998;58(5):5355\u201363. https:\/\/doi.org\/10.1103\/physreve.58.5355.","journal-title":"Phys Rev E"},{"issue":"6","key":"4661_CR6","doi-asserted-by":"publisher","first-page":"061007","DOI":"10.7566\/jpsj.88.061007","volume":"88","author":"J King","year":"2019","unstructured":"King J, Yarkoni S, Raymond J, Ozfidan I, King AD, Nevisi MM, Hilton JP, McGeoch CC. Quantum annealing amid local ruggedness and global frustration. J Phys Soc Jpn. 2019;88(6):061007. https:\/\/doi.org\/10.7566\/jpsj.88.061007.","journal-title":"J Phys Soc Jpn"},{"key":"4661_CR7","doi-asserted-by":"publisher","DOI":"10.1103\/physrevx.6.031015","author":"VS Denchev","year":"2016","unstructured":"Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H. What is the computational value of finite-range tunneling? Phys Rev X. 2016. https:\/\/doi.org\/10.1103\/physrevx.6.031015.","journal-title":"Phys Rev X"},{"key":"4661_CR8","doi-asserted-by":"publisher","DOI":"10.3389\/fict.2019.00013","author":"S Feld","year":"2019","unstructured":"Feld S, Roch C, Gabor T, Seidel C, Neukart F, Galter I, Mauerer W, Linnhoff-Popien C. A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Front ICT. 2019. https:\/\/doi.org\/10.3389\/fict.2019.00013.","journal-title":"Front ICT"},{"key":"4661_CR9","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2021.760783","author":"S Jain","year":"2021","unstructured":"Jain S. Solving the traveling salesman problem on the d-wave quantum computer. Front Phys. 2021. https:\/\/doi.org\/10.3389\/fphy.2021.760783.","journal-title":"Front Phys"},{"key":"4661_CR10","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-88321-5","author":"AS Boev","year":"2021","unstructured":"Boev AS, Rakitko AS, Usmanov SR, Kobzeva AN, Popov IV, Ilinsky VV, Kiktenko EO, Fedorov AK. Genome assembly using quantum and quantum-inspired annealing. Sci Rep. 2021. https:\/\/doi.org\/10.1038\/s41598-021-88321-5.","journal-title":"Sci Rep"},{"issue":"4","key":"4661_CR11","doi-asserted-by":"publisher","first-page":"0249850","DOI":"10.1371\/journal.pone.0249850","volume":"16","author":"A Sarkar","year":"2021","unstructured":"Sarkar A, Al-Ars Z, Bertels K. QuASeR: quantum accelerated de novo DNA sequence reconstruction. PLoS ONE. 2021;16(4):0249850. https:\/\/doi.org\/10.1371\/journal.pone.0249850.","journal-title":"PLoS ONE"},{"key":"4661_CR12","doi-asserted-by":"publisher","unstructured":"Jugas R, Vitek M, Sedlar K, Skutkova H. Cross-correlation based detection of contigs overlaps. In: 41st International convention on information and communication technology, electronics and microelectronics (MIPRO), 2018; p. 0155\u20130158. https:\/\/doi.org\/10.23919\/MIPRO.2018.8400030.","DOI":"10.23919\/MIPRO.2018.8400030"},{"key":"4661_CR13","doi-asserted-by":"publisher","unstructured":"Cristea PD. Phase analysis of DNA genomic signals. In: Proceedings of the 2003 international symposium on circuits and systems, ISCAS \u201903, vol. 5, 2003. https:\/\/doi.org\/10.1109\/ISCAS.2003.1206163.","DOI":"10.1109\/ISCAS.2003.1206163"},{"issue":"2","key":"4661_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1111\/j.1582-4934.2002.tb00196.x","volume":"6","author":"PD Cristea","year":"2002","unstructured":"Cristea PD. Conversion of nucleotides sequences into genomic signals. J Cell Mol Med. 2002;6(2):279\u2013303. https:\/\/doi.org\/10.1111\/j.1582-4934.2002.tb00196.x.","journal-title":"J Cell Mol Med"},{"key":"4661_CR15","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1007\/978-1-4020-5614-7_2569","volume-title":"Pearson\u2019s correlation coefficient","author":"W Kirch","year":"2008","unstructured":"Kirch W. Pearson\u2019s correlation coefficient. Dordrecht: Springer; 2008. p. 1090\u20131. https:\/\/doi.org\/10.1007\/978-1-4020-5614-7_2569."},{"issue":"1\/2","key":"4661_CR16","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1023\/a:1022613513712","volume":"21","author":"RJ Parsons","year":"1995","unstructured":"Parsons RJ, Forrest S, Burks C. Genetic algorithms, operators, and DNA fragment assembly. Mach Learn. 1995;21(1\/2):11\u201333. https:\/\/doi.org\/10.1023\/a:1022613513712.","journal-title":"Mach Learn"},{"key":"4661_CR17","doi-asserted-by":"publisher","unstructured":"Mallen-Fullerton GM, Fernandez-Anaya G. DNA fragment assembly using optimization. In: IEEE Congress on Evolutionary Computation. IEEE; 2013. https:\/\/doi.org\/10.1109\/cec.2013.6557749.","DOI":"10.1109\/cec.2013.6557749"},{"key":"4661_CR18","unstructured":"Perron L, Furnon V. OR-Tools. https:\/\/developers.google.com\/optimization\/"},{"key":"4661_CR19","unstructured":"Perron L, Furnon V. Traveling salesperson problem. https:\/\/developers.google.com\/optimization\/routing\/tsp (2019). Accessed 12 Aug 2021."},{"key":"4661_CR20","doi-asserted-by":"crossref","unstructured":"Borowski M, Gora P, Karnas K, B\u0142ajda M, Kr\u00f3l K, Matyjasek A, Burczyk D, Szewczyk M, Kutwin M. New hybrid quantum annealing algorithms for solving vehicle routing problem. In: Krzhizhanovskaya VV, Z\u00e1vodszky G, Lees MH, Dongarra JJ, Sloot PMA, Brissos S, Teixeira J, editors. Computational Science\u2013ICCS 2020. Cham: Springer; 2020. p. 546\u201361.","DOI":"10.1007\/978-3-030-50433-5_42"},{"issue":"1","key":"4661_CR21","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig GB, Ramser JH. The truck dispatching problem. Manag Sci. 1959;6(1):80\u201391. https:\/\/doi.org\/10.1287\/mnsc.6.1.80.","journal-title":"Manag Sci"},{"key":"4661_CR22","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2014.00005","author":"A Lucas","year":"2014","unstructured":"Lucas A. Ising formulations of many NP problems. Front Phys. 2014. https:\/\/doi.org\/10.3389\/fphy.2014.00005.","journal-title":"Front Phys"},{"key":"4661_CR23","doi-asserted-by":"publisher","unstructured":"Grant E, Humble T, Stump B. Benchmarking quantum annealing controls with portfolio optimization. 2020. https:\/\/doi.org\/10.1103\/PhysRevApplied.15.014012. arXiv:2007.03005.","DOI":"10.1103\/PhysRevApplied.15.014012"},{"key":"4661_CR24","unstructured":"Bujel K, Lai F, Szczeci\u0144ski M, So W, Fernandez M. Solving high volume capacitated vehicle routing problem with time windows using recursive-DBSCAN clustering algorithm. 2018. arXiv:1812.02300"},{"issue":"6","key":"4661_CR25","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/s0168-9525(00)02024-2","volume":"16","author":"P Rice","year":"2000","unstructured":"Rice P, Longden I, Bleasby A. EMBOSS: the European molecular biology open software suite. Trends Genet. 2000;16(6):276\u20137. https:\/\/doi.org\/10.1016\/s0168-9525(00)02024-2.","journal-title":"Trends Genet"},{"key":"4661_CR26","unstructured":"Lee H. ReadSim 1.6-read simulator for long reads. http:\/\/sourceforge.net\/projects\/readsim\/."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-04661-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-022-04661-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-04661-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:06:33Z","timestamp":1649333193000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-022-04661-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,7]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["4661"],"URL":"https:\/\/doi.org\/10.1186\/s12859-022-04661-7","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,7]]},"assertion":[{"value":"8 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"122"}}