{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329588,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["851093"],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["322595","328877"],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"abstract":"Abstract<\/jats:title>Suffix trees are an important data structure at the core of optimal solutions to many fundamental string problems, such as exact pattern matching<\/jats:italic>, longest common substring<\/jats:italic>, matching statistics<\/jats:italic>, and longest repeated substring<\/jats:italic>. Recent lines of research focused on extending some of these problems to vertex-labeled graphs, either by using efficient ad-hoc approaches which do not generalize to all input graphs, or by indexing difficult graphs and having worst-case exponential complexities. In the absence of an ubiquitous and polynomial tool like the suffix tree for labeled graphs, we introduce the labeled direct product of two graphs as a general tool for obtaining optimal algorithms in the worst case: we obtain conceptually simpler algorithms for the quadratic problems of string matching () and longest common substring () in labeled graphs. Our algorithms run in time linear in the size of the labeled product graph, which may be smaller than quadratic for some inputs, and their run-time is predictable, because the size of the labeled direct product graph can be precomputed efficiently. We also solve on graphs containing cycles, which was left as an open problem by Shimohira et al. in 2011. To show the power of the labeled product graph, we also apply it to solve the matching statistics () and the longest repeated string () problems in labeled graphs. Moreover, we show that our (worst-case quadratic) algorithms are also optimal, conditioned on the Orthogonal Vectors Hypothesis. Finally, we complete the complexity picture around by studying it on undirected graphs.<\/jats:p>","DOI":"10.1007\/s00453-022-00989-x","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T12:03:08Z","timestamp":1657022588000},"page":"3008-3033","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Solving String Problems on Graphs Using the Labeled Direct Product"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2035-6309","authenticated-orcid":false,"given":"Nicola","family":"Rizzo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Policriti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"989_CR1","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Structuring labeled trees for optimal succinctness, and beyond. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pp. 184\u2013196. IEEE Computer Society, (2005). https:\/\/doi.org\/10.1109\/SFCS.2005.69","DOI":"10.1109\/SFCS.2005.69"},{"key":"989_CR2","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1038\/nbt.422710.1038\/nbt.4227","volume":"36","author":"E Garrison","year":"2018","unstructured":"Garrison, E., Sir\u00e9n, J., Novak, A.M., Hickey, G., Eizenga, J.M., Dawson, E.T., Jones, W., Garg, S., Markello, C., Lin, M.F., Paten, B., Durbin, R.: Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nat. Biotechnol. 36, 875 (2018). https:\/\/doi.org\/10.1038\/nbt.422710.1038\/nbt.4227","journal-title":"Nat. Biotechnol."},{"key":"989_CR3","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1186\/gb-2009-10-9-r98","volume":"10","author":"K Schneeberger","year":"2009","unstructured":"Schneeberger, K., Hagmann, J., Ossowski, S., Warthmann, N., Gesing, S., Kohlbacher, O., Weigel, D.: Simultaneous alignment of short reads against multiple genomes. Genome Biol. 10, 98 (2009)","journal-title":"Genome Biol."},{"key":"989_CR4","doi-asserted-by":"crossref","unstructured":"Akutsu, T.: A linear time pattern matching algorithm between a string and a tree. In: 4th Symposium on Combinatorial Pattern Matching, Padova, Italy, pp. 1\u201310 (1993)","DOI":"10.1007\/BFb0029792"},{"key":"989_CR5","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Which regular expression patterns are hard to match? In: IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pp. 457\u2013466 (2016)","DOI":"10.1109\/FOCS.2016.56"},{"key":"989_CR6","doi-asserted-by":"publisher","unstructured":"Equi, M., Grossi, R., M\u00e4kinen, V., Tomescu, A.I.: On the complexity of string matching for graphs. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. LIPIcs, vol. 132, pp. 55\u201315515. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.55","DOI":"10.4230\/LIPIcs.ICALP.2019.55"},{"key":"989_CR7","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-67731-2_44","volume-title":"SOFSEM 2021: Theory and Practice of Computer Science","author":"M Equi","year":"2021","unstructured":"Equi, M., M\u00e4kinen, V., Tomescu, A.I.: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails. In: Bure\u0161, T., Dondi, R., Gamper, J., Guerrini, G., Jurdzi\u0144ski, T., Pahl, C., Sikora, F., Wong, P.W.H. (eds.) SOFSEM 2021: Theory and Practice of Computer Science, pp. 608\u2013622. Springer, Cham (2021)"},{"key":"989_CR8","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, January 11-12, 2021, pp. 232\u2013242. SIAM, (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.26","DOI":"10.1137\/1.9781611976496.26"},{"issue":"1","key":"989_CR9","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)","journal-title":"J. Algorithms"},{"key":"989_CR10","doi-asserted-by":"crossref","unstructured":"Rautiainen, M., Marschall, T.: Aligning sequences to general graphs in $$O(V+ mE)$$ time. bioRxiv, 216\u2013127 (2017)","DOI":"10.1101\/216127"},{"key":"989_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-030-17083-7_6","volume-title":"Research in Computational Molecular Biology","author":"C Jain","year":"2019","unstructured":"Jain, C., Zhang, H., Gao, Y., Aluru, S.: On the complexity of sequence to graph alignment. In: Cowen, L.J. (ed.) Research in Computational Molecular Biology, pp. 85\u2013100. Springer, Cham (2019)"},{"key":"989_CR12","doi-asserted-by":"publisher","unstructured":"Bowe, A., Onodera, T., Sadakane, K., Shibuya, T.: Succinct de bruijn graphs. In: Raphael, B.J., Tang, J. (eds.) Algorithms in Bioinformatics - 12th International Workshop, WABI 2012, Ljubljana, Slovenia, September 10-12, 2012. Proceedings. Lecture Notes in Computer Science, vol. 7534, pp. 225\u2013235. Springer, (2012). https:\/\/doi.org\/10.1007\/978-3-642-33122-0_18","DOI":"10.1007\/978-3-642-33122-0_18"},{"issue":"2","key":"989_CR13","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","volume":"11","author":"V M\u00e4kinen","year":"2014","unstructured":"M\u00e4kinen, V., V\u00e4lim\u00e4ki, N., Sir\u00e9n, J.: Indexing graphs for path queries with applications in genome research. IEEE ACM Trans. Comput. Biol. Bioinform. 11(2), 375\u2013388 (2014). https:\/\/doi.org\/10.1109\/TCBB.2013.2297101","journal-title":"IEEE ACM Trans. Comput. Biol. Bioinform."},{"key":"989_CR14","doi-asserted-by":"publisher","unstructured":"Cotumaccio, N., Prezza, N.: On indexing and compressing finite automata. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 2585\u20132599. SIAM, (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.153","DOI":"10.1137\/1.9781611976465.153"},{"key":"989_CR15","doi-asserted-by":"publisher","unstructured":"Nellore, A., Nguyen, A., Thompson, R.F.: An invertible transform for efficient string matching in labeled digraphs. In: Gawrychowski, P., Starikovskaya, T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wroc\u0142aw, Poland. LIPIcs, vol. 191, pp. 20\u201312014. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.20","DOI":"10.4230\/LIPIcs.CPM.2021.20"},{"key":"989_CR16","doi-asserted-by":"publisher","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press (1997). https:\/\/doi.org\/10.1017\/cbo9780511574931","DOI":"10.1017\/cbo9780511574931"},{"key":"989_CR17","doi-asserted-by":"publisher","unstructured":"M\u00e4kinen, V., Belazzougui, D., Cunial, F., Tomescu, A.I.: Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing. Cambridge University Press, (2015). https:\/\/doi.org\/10.1017\/CBO9781139940023","DOI":"10.1017\/CBO9781139940023"},{"key":"989_CR18","doi-asserted-by":"crossref","unstructured":"Parida, L.: Pattern Discovery in Bioinformatics: Theory & Algorithms, 1st edn. Chapman & Hall\/CRC (2007)","DOI":"10.1201\/9781420010732"},{"key":"989_CR19","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific (2002). https:\/\/doi.org\/10.1142\/4838","DOI":"10.1142\/4838"},{"key":"989_CR20","unstructured":"Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, (2013). http:\/\/www.oldenbusch-verlag.de\/"},{"issue":"2","key":"989_CR21","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1242471.1242472","volume":"39","author":"SJ Puglisi","year":"2007","unstructured":"Puglisi, S.J., Smyth, W.F., Turpin, A.: A taxonomy of suffix array construction algorithms. ACM Comput. Surv. 39(2), 4 (2007). https:\/\/doi.org\/10.1145\/1242471.1242472","journal-title":"ACM Comput. Surv."},{"key":"989_CR22","unstructured":"Shimohira, K., Inenaga, S., Bannai, H., Takeda, M.: Computing longest common substring\/subsequence of non-linear texts. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2011, Prague, Czech Republic, August 29-31, 2011, pp. 197\u2013208. Prague Stringology Club, Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, (2011). http:\/\/www.stringology.org\/event\/2011\/p17.html"},{"issue":"1","key":"989_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.14232\/actacyb.23.1.2017.9","volume":"23","author":"Y Han","year":"2017","unstructured":"Han, Y., Salomaa, A., Salomaa, K.: Ambiguity, nondeterminism and state complexity of finite automata. Acta Cybern. 23(1), 141\u2013157 (2017). https:\/\/doi.org\/10.14232\/actacyb.23.1.2017.9","journal-title":"Acta Cybern."},{"key":"989_CR24","doi-asserted-by":"publisher","unstructured":"Colcombet, T.: Unambiguity in automata theory. In: Shallit, J.O., Okhotin, A. (eds.) Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings. Lecture Notes in Computer Science, vol. 9118, pp. 3\u201318. Springer, (2015). https:\/\/doi.org\/10.1007\/978-3-319-19225-3_1","DOI":"10.1007\/978-3-319-19225-3_1"},{"issue":"2","key":"989_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.3217\/jucs-008-02-0193","volume":"8","author":"J Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Univers. Comput. Sci. 8(2), 193\u2013234 (2002). https:\/\/doi.org\/10.3217\/jucs-008-02-0193","journal-title":"J. Univers. Comput. Sci."},{"issue":"2","key":"989_CR26","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1109\/T-C.1971.223204","volume":"20","author":"RV Book","year":"1971","unstructured":"Book, R.V., Even, S., Greibach, S.A., Ott, G.: Ambiguity in graphs and expressions. IEEE Trans. Computers 20(2), 149\u2013153 (1971). https:\/\/doi.org\/10.1109\/T-C.1971.223204","journal-title":"IEEE Trans. Computers"},{"issue":"2","key":"989_CR27","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"A Weber","year":"1991","unstructured":"Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theor. Comput. Sci. 88(2), 325\u2013349 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90381-B","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"989_CR28","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1142\/S0129054111008477","volume":"22","author":"C Allauzen","year":"2011","unstructured":"Allauzen, C., Mohri, M., Rastogi, A.: General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers. Int. J. Found. Comput. Sci. 22(4), 883\u2013904 (2011). https:\/\/doi.org\/10.1142\/S0129054111008477","journal-title":"Int. J. Found. Comput. Sci."},{"key":"989_CR29","doi-asserted-by":"publisher","unstructured":"Kosaraju, S.R.: Efficient tree pattern matching (preliminary version). In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pp. 178\u2013183. IEEE Computer Society, (1989). https:\/\/doi.org\/10.1109\/SFCS.1989.63475","DOI":"10.1109\/SFCS.1989.63475"},{"issue":"1\u20132","key":"989_CR30","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(96)00319-2","volume":"191","author":"D Breslauer","year":"1998","unstructured":"Breslauer, D.: The suffix tree of a tree and minimizing sequential transducers. Theor. Comput. Sci. 191(1\u20132), 131\u2013144 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(96)00319-2","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"989_CR31","first-page":"1061","volume":"86\u2013A","author":"T Shibuya","year":"2003","unstructured":"Shibuya, T.: Constructing the suffix tree of a tree with a large alphabet. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 86\u2013A(5), 1061\u20131066 (2003)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"989_CR32","doi-asserted-by":"publisher","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, October 19-22, 1997, pp. 137\u2013143. IEEE Computer Society, (1997). https:\/\/doi.org\/10.1109\/SFCS.1997.646102","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"2","key":"989_CR33","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci. 348(2), 357\u2013365 (2005). https:\/\/doi.org\/10.1016\/j.tcs.2005.09.023","journal-title":"Theoret. Comput. Sci."},{"key":"989_CR34","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. In: Digital SRC Research Report (1994). Citeseer"},{"key":"989_CR35","doi-asserted-by":"publisher","first-page":"104820","DOI":"10.1016\/j.ic.2021.104820","volume":"281","author":"J Alanko","year":"2021","unstructured":"Alanko, J., D\u2019Agostino, G., Policriti, A., Prezza, N.: Wheeler languages. Inf. Comput. 281, 104820 (2021). https:\/\/doi.org\/10.1016\/j.ic.2021.104820","journal-title":"Inf. Comput."},{"key":"989_CR36","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."},{"key":"989_CR37","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, September 9-11, 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, pp. 51\u201315116. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.51","DOI":"10.4230\/LIPIcs.ESA.2019.51"},{"key":"989_CR38","unstructured":"Harary, F.: Graph Theory. Addison-Wesley (1991)"},{"key":"989_CR39","doi-asserted-by":"crossref","unstructured":"Harary, F., Wilcox, G.W.: Boolean operations on graphs. Mathematica Scandinavica, 20(1), 41\u201351 (1967). https:\/\/www.jstor.org\/stable\/pdf\/24490249.pdf","DOI":"10.7146\/math.scand.a-10817"},{"issue":"2","key":"989_CR40","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959). https:\/\/doi.org\/10.1147\/rd.32.0114","journal-title":"IBM J. Res. Dev."},{"key":"989_CR41","doi-asserted-by":"publisher","unstructured":"Goldstein, I., Kopelowitz, T., Lewenstein, M., Porat, E.: Conditional lower bounds for space\/time tradeoffs. In: Ellen, F., Kolokolova, A., Sack, J. (eds.) Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John\u2019s, NL, Canada, July 31 - August 2, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10389, pp. 421\u2013436. Springer, (2017). https:\/\/doi.org\/10.1007\/978-3-319-62127-2_36","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"989_CR42","doi-asserted-by":"publisher","unstructured":"Thomas, W.: Automata on infinite objects. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 133\u2013191. Elsevier and MIT Press, (1990). https:\/\/doi.org\/10.1016\/b978-0-444-88074-1.50009-3","DOI":"10.1016\/b978-0-444-88074-1.50009-3"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00989-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00989-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00989-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T14:20:34Z","timestamp":1664547634000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00989-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":42,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["989"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00989-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"6 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 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":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest\/Competing interests"}}]}}