IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0249850.html
   My bibliography  Save this article

QuASeR: Quantum Accelerated de novo DNA sequence reconstruction

Author

Listed:
  • Aritra Sarkar
  • Zaid Al-Ars
  • Koen Bertels

Abstract

In this article, we present QuASeR, a reference-free DNA sequence reconstruction implementation via de novo assembly on both gate-based and quantum annealing platforms. This is the first time this important application in bioinformatics is modeled using quantum computation. Each one of the four steps of the implementation (TSP, QUBO, Hamiltonians and QAOA) is explained with a proof-of-concept example to target both the genomics research community and quantum application developers in a self-contained manner. The implementation and results on executing the algorithm from a set of DNA reads to a reconstructed sequence, on a gate-based quantum simulator, the D-Wave quantum annealing simulator and hardware are detailed. We also highlight the limitations of current classical simulation and available quantum hardware systems. The implementation is open-source and can be found on https://github.com/QE-Lab/QuASeR.

Suggested Citation

  • Aritra Sarkar & Zaid Al-Ars & Koen Bertels, 2021. "QuASeR: Quantum Accelerated de novo DNA sequence reconstruction," PLOS ONE, Public Library of Science, vol. 16(4), pages 1-23, April.
    • Handle: RePEc:plo:pone00:0249850
    DOI: 10.1371/journal.pone.0249850
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0249850
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0249850&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0249850?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    2. Jarrod R. McClean & Sergio Boixo & Vadim N. Smelyanskiy & Ryan Babbush & Hartmut Neven, 2018. "Barren plateaus in quantum neural network training landscapes," Nature Communications, Nature, vol. 9(1), pages 1-6, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ajagekar, Akshay & You, Fengqi, 2022. "Quantum computing and quantum artificial intelligence for renewable and sustainable energy: A emerging prospect towards climate neutrality," Renewable and Sustainable Energy Reviews, Elsevier, vol. 165(C).
    2. Byron Tasseff & Tameem Albash & Zachary Morrell & Marc Vuffray & Andrey Y. Lokhov & Sidhant Misra & Carleton Coffrin, 2024. "On the emerging potential of quantum annealing hardware for combinatorial optimization," Journal of Heuristics, Springer, vol. 30(5), pages 325-358, December.
    3. Takayuki Sakuma, 2020. "Application of deep quantum neural networks to finance," Papers 2011.07319, arXiv.org, revised May 2022.
    4. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    5. Iris Cong & Nishad Maskara & Minh C. Tran & Hannes Pichler & Giulia Semeghini & Susanne F. Yelin & Soonwon Choi & Mikhail D. Lukin, 2024. "Enhancing detection of topological order by local error correction," Nature Communications, Nature, vol. 15(1), pages 1-14, December.
    6. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    7. Eric R. Anschuetz & Bobak T. Kiani, 2022. "Quantum variational algorithms are swamped with traps," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    8. Alen Senanian & Sridhar Prabhu & Vladimir Kremenetski & Saswata Roy & Yingkang Cao & Jeremy Kline & Tatsuhiro Onodera & Logan G. Wright & Xiaodi Wu & Valla Fatemi & Peter L. McMahon, 2024. "Microwave signal processing using an analog quantum reservoir computer," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    9. Enrico Fontana & Dylan Herman & Shouvanik Chakrabarti & Niraj Kumar & Romina Yalovetzky & Jamie Heredge & Shree Hari Sureshbabu & Marco Pistoia, 2024. "Characterizing barren plateaus in quantum ansätze with the adjoint representation," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    10. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    11. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    12. Juan S. Borrero & Colin Gillen & Oleg A. Prokopyev, 2017. "Fractional 0–1 programming: applications and algorithms," Journal of Global Optimization, Springer, vol. 69(1), pages 255-282, September.
    13. Kevin Wils & Boyang Chen, 2023. "A Symbolic Approach to Discrete Structural Optimization Using Quantum Annealing," Mathematics, MDPI, vol. 11(16), pages 1-29, August.
    14. Wei-Ming Li & Shi-Ju Ran, 2022. "Non-Parametric Semi-Supervised Learning in Many-Body Hilbert Space with Rescaled Logarithmic Fidelity," Mathematics, MDPI, vol. 10(6), pages 1-15, March.
    15. Yitian Qian & Shaohua Pan & Shujun Bi, 2023. "A matrix nonconvex relaxation approach to unconstrained binary polynomial programs," Computational Optimization and Applications, Springer, vol. 84(3), pages 875-919, April.
    16. Michael Ragone & Bojko N. Bakalov & Frédéric Sauvage & Alexander F. Kemper & Carlos Ortiz Marrero & Martín Larocca & M. Cerezo, 2024. "A Lie algebraic theory of barren plateaus for deep parameterized quantum circuits," Nature Communications, Nature, vol. 15(1), pages 1-10, December.
    17. El Amine Cherrat & Snehal Raj & Iordanis Kerenidis & Abhishek Shekhar & Ben Wood & Jon Dee & Shouvanik Chakrabarti & Richard Chen & Dylan Herman & Shaohan Hu & Pierre Minssen & Ruslan Shaydulin & Yue , 2023. "Quantum Deep Hedging," Papers 2303.16585, arXiv.org, revised Nov 2023.
    18. Fred Glover & Gary Kochenberger & Yu Du, 2019. "Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models," 4OR, Springer, vol. 17(4), pages 335-371, December.
    19. Martin Vesely, 2023. "Finding the Optimal Currency Composition of Foreign Exchange Reserves with a Quantum Computer," Papers 2303.01909, arXiv.org.
    20. Pinaki Sen & Amandeep Singh Bhatia & Kamalpreet Singh Bhangu & Ahmed Elbeltagi, 2022. "Variational quantum classifiers through the lens of the Hessian," PLOS ONE, Public Library of Science, vol. 17(1), pages 1-17, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0249850. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.