{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T06:46:22Z","timestamp":1747291582797,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031206429"},{"type":"electronic","value":"9783031206436"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-20643-6_22","type":"book-chapter","created":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:18:09Z","timestamp":1667222289000},"page":"303-314","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Quantum Time Complexity and\u00a0Algorithms for\u00a0Pattern Matching on\u00a0Labeled Graphs"],"prefix":"10.1007","author":[{"given":"Parisa","family":"Darbari","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Gibney","sequence":"additional","affiliation":[]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,1]]},"reference":[{"key":"22_CR1","unstructured":"Pangaia, November 2020. https:\/\/www.pangenome.eu\/"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Grier, D., Schaeffer, L.: A quantum query complexity trichotomy for regular languages. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 942\u2013965. IEEE (2019)","DOI":"10.1109\/FOCS.2019.00061"},{"key":"22_CR3","doi-asserted-by":"publisher","unstructured":"Akmal, S., Jin, C.: Near-optimal quantum algorithms for string problems. In: Naor, J.S., Buchbinder, N. (eds.) Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference\/Alexandria, VA, USA, 9\u201312 January 2022, pp. 2791\u20132832. SIAM (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.109","DOI":"10.1137\/1.9781611977073.109"},{"key":"22_CR4","doi-asserted-by":"publisher","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., Prezza, N.: Regular languages meet prefix sorting. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020, pp. 911\u2013930. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.55","DOI":"10.1137\/1.9781611975994.55"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.1999.1063","volume":"35","author":"A Amir","year":"2000","unstructured":"Amir, A., Lewenstein, M., Lewenstein, N.: Pattern matching in hypertext. J. Algorithms 35(1), 82\u201399 (2000). https:\/\/doi.org\/10.1006\/jagm.1999.1063","journal-title":"J. Algorithms"},{"issue":"5","key":"22_CR6","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995)","journal-title":"Phys. Rev. A"},{"key":"22_CR7","doi-asserted-by":"publisher","unstructured":"Buhrman, H., Loff, B., Patro, S., Speelman, F.: Memory compression with quantum random-access gates. CoRR abs\/2203.05599 (2022). https:\/\/doi.org\/10.48550\/arXiv.2203.05599","DOI":"10.48550\/arXiv.2203.05599"},{"key":"22_CR8","doi-asserted-by":"publisher","unstructured":"Buhrman, H., Patro, S., Speelman, F.: A framework of quantum strong exponential-time hypotheses. In: Bl\u00e4ser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, Saarbr\u00fccken, Germany, 16\u201319 March 2021 (Virtual Conference). LIPIcs, vol. 187, pp. 19:1\u201319:19. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.19","DOI":"10.4230\/LIPIcs.STACS.2021.19"},{"issue":"1","key":"22_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-019-1909-7","volume":"20","author":"S Chen","year":"2019","unstructured":"Chen, S., Krusche, P., Dolzhenko, E., Sherman, R.M., Petrovski, R., Schlesinger, F., Kirsche, M., Bentley, D.R., Schatz, M.C., Sedlazeck, F.J., et al.: Paragraph: a graph-based structural variant genotyper for short-read sequence data. Genome Biol. 20(1), 1\u201313 (2019). https:\/\/doi.org\/10.1186\/s13059-019-1909-7","journal-title":"Genome Biol."},{"key":"22_CR10","unstructured":"The Computational Pan-Genomics Consortium: Computational pan-genomics: status, promises and challenges. Briefings Bioinform. 19(1), 118\u2013135 (2018)"},{"issue":"6","key":"22_CR11","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/050644719","volume":"35","author":"C D\u00fcrr","year":"2006","unstructured":"D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. Comput. 35(6), 1310\u20131328 (2006). https:\/\/doi.org\/10.1137\/050644719","journal-title":"SIAM J. Comput."},{"issue":"1","key":"22_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-019-13341-9","volume":"10","author":"HP Eggertsson","year":"2019","unstructured":"Eggertsson, H.P., et al.: GraphTyper2 enables population-scale genotyping of structural variation using pangenome graphs. Nat. Commun. 10(1), 1\u20138 (2019)","journal-title":"Nat. Commun."},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1146\/annurev-genom-120219-080406","volume":"21","author":"JM Eizenga","year":"2020","unstructured":"Eizenga, J.M., et al.: Pangenome graphs. Ann. Rev. Genomics Hum. Genet. 21, 139\u2013162 (2020)","journal-title":"Ann. Rev. Genomics Hum. Genet."},{"key":"22_CR14","unstructured":"Equi, M., de Griend, A.M., M\u00e4kinen, V.: From bit-parallelism to quantum: breaking the quadratic barrier. CoRR abs\/2112.13005 (2021). https:\/\/arxiv.org\/abs\/2112.13005"},{"key":"22_CR15","unstructured":"Equi, M., Grossi, R., M\u00e4kinen, V., Tomescu, A., et al.: On the complexity of string matching for graphs. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2017.06.016","volume":"698","author":"T Gagie","year":"2017","unstructured":"Gagie, T., Manzini, G., Sir\u00e9n, J.: Wheeler graphs: a framework for BWT-based data structures. Theor. Comput. Sci. 698, 67\u201378 (2017). https:\/\/doi.org\/10.1016\/j.tcs.2017.06.016","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"22_CR17","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.4227","volume":"36","author":"E Garrison","year":"2018","unstructured":"Garrison, E., et al.: Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat. Biotechnol. 36(9), 875\u2013879 (2018)","journal-title":"Nat. Biotechnol."},{"key":"22_CR18","doi-asserted-by":"publisher","unstructured":"Gibney, D., Hoppenworth, G., Thankachan, S.V.: Simple reductions from formula-SAT to pattern matching on labeled graphs and subtree isomorphism. In: Le, H.V., King, V. (eds.) 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, 11\u201312 January 2021, pp. 232\u2013242. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.26","DOI":"10.1137\/1.9781611976496.26"},{"key":"22_CR19","doi-asserted-by":"publisher","unstructured":"Gibney, D., Thankachan, S.V.: On the hardness and inapproximability of recognizing wheeler graphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, Munich\/Garching, Germany, 9\u201311 September 2019. LIPIcs, vol. 144, pp. 51:1\u201351:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.51","DOI":"10.4230\/LIPIcs.ESA.2019.51"},{"issue":"3","key":"22_CR20","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/s00453-021-00917-5","volume":"84","author":"D Gibney","year":"2022","unstructured":"Gibney, D., Thankachan, S.V.: On the complexity of recognizing wheeler graphs. Algorithmica 84(3), 784\u2013814 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00917-5","journal-title":"Algorithmica"},{"key":"22_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-031-04749-7_16","volume-title":"Research in Computational Molecular Biology","author":"D Gibney","year":"2022","unstructured":"Gibney, D., Thankachan, S.V., Aluru, S.: The complexity of approximate pattern matching on de Bruijn graphs. In: Pe\u2019er, I. (ed.) RECOMB 2022. LNCS, vol. 13278, pp. 263\u2013278. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-04749-7_16"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"22_CR23","volume-title":"Quantum Computing","author":"J Gruska","year":"1999","unstructured":"Gruska, J., et al.: Quantum Computing, vol. 2005. McGraw-Hill, London (1999)"},{"issue":"1","key":"22_CR24","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S1570-8667(03)00010-8","volume":"1","author":"R Hariharan","year":"2003","unstructured":"Hariharan, R., Vinay, V.: String matching in \u00f5(sqrt(n)+sqrt(m)) quantum time. J. Discrete Algorithms 1(1), 103\u2013110 (2003). https:\/\/doi.org\/10.1016\/S1570-8667(03)00010-8","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"22_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-020-1941-7","volume":"21","author":"G Hickey","year":"2020","unstructured":"Hickey, G., et al.: Genotyping structural variants in pangenome graphs using the vg toolkit. Genome Biol. 21(1), 1\u201317 (2020). https:\/\/doi.org\/10.1186\/s13059-020-1941-7","journal-title":"Genome Biol."},{"issue":"4","key":"22_CR26","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1089\/cmb.2019.0066","volume":"27","author":"C Jain","year":"2020","unstructured":"Jain, C., Zhang, H., Gao, Y., Aluru, S.: On the complexity of sequence-to-graph alignment. J. Comput. Biol. 27(4), 640\u2013654 (2020)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"22_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-020-02168-z","volume":"21","author":"H Li","year":"2020","unstructured":"Li, H., Feng, X., Chu, C.: The design and construction of reference pangenome graphs with minigraph. Genome Biol. 21(1), 1\u201319 (2020). https:\/\/doi.org\/10.1186\/s13059-020-02168-z","journal-title":"Genome Biol."},{"issue":"5","key":"22_CR28","doi-asserted-by":"publisher","first-page":"1374","DOI":"10.1093\/bioinformatics\/btz102","volume":"36","author":"A Limasset","year":"2020","unstructured":"Limasset, A., Flot, J.F., Peterlongo, P.: Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs. Bioinformatics 36(5), 1374\u20131381 (2020)","journal-title":"Bioinformatics"},{"issue":"1","key":"22_CR29","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1137\/090745854","volume":"40","author":"F Magniez","year":"2011","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM J. Comput. 40(1), 142\u2013164 (2011)","journal-title":"SIAM J. Comput."},{"key":"22_CR30","doi-asserted-by":"crossref","unstructured":"Manber, U., Wu, S.: Approximate string matching with arbitrary costs for text and hypertext. In: Advances in Structural and Syntactic Pattern Recognition, pp. 22\u201333. World Scientific (1992)","DOI":"10.1142\/9789812797919_0002"},{"issue":"24","key":"22_CR31","doi-asserted-by":"publisher","first-page":"4213","DOI":"10.1093\/bioinformatics\/bty521","volume":"34","author":"P Morisse","year":"2018","unstructured":"Morisse, P., Lecroq, T., Lefebvre, A.: Hybrid correction of highly noisy long reads using a variable-order de Bruijn graph. Bioinformatics 34(24), 4213\u20134222 (2018)","journal-title":"Bioinformatics"},{"issue":"1\u20132","key":"22_CR32","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/S0304-3975(99)00333-3","volume":"237","author":"G Navarro","year":"2000","unstructured":"Navarro, G.: Improved approximate pattern matching on hypertext. Theor. Comput. Sci. 237(1\u20132), 455\u2013463 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(99)00333-3","journal-title":"Theor. Comput. Sci."},{"key":"22_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-60044-2_51","volume-title":"Combinatorial Pattern Matching","author":"K Park","year":"1995","unstructured":"Park, K., Kim, D.K.: String matching in hypertext. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol. 937, pp. 318\u2013329. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60044-2_51"},{"issue":"5","key":"22_CR34","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1101\/gr.214155.116","volume":"27","author":"B Paten","year":"2017","unstructured":"Paten, B., Novak, A.M., Eizenga, J.M., Garrison, E.: Genome graphs and the evolution of genome inference. Genome Res. 27(5), 665\u2013676 (2017)","journal-title":"Genome Res."},{"key":"22_CR35","doi-asserted-by":"publisher","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20\u201322 November 1994, pp. 124\u2013134. IEEE Computer Society (1994). https:\/\/doi.org\/10.1109\/SFCS.1994.365700","DOI":"10.1109\/SFCS.1994.365700"},{"key":"22_CR36","unstructured":"Tzanis, E.: A quantum algorithm for string matching. In: Guimar\u00e3es, N., Isa\u00edas, P.T. (eds.) AC 2005, Proceedings of the IADIS International Conference on Applied Computing, Algarve, Portugal, 22\u201325 February 2005, vol. 2. pp. 374\u2013377. IADIS (2005)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-20643-6_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T13:20:32Z","timestamp":1667222432000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-20643-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031206429","9783031206436"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-20643-6_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Concepci\u00f3n","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2022.inf.udec.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"53% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.62","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}