{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:49:23Z","timestamp":1762325363408,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T00:00:00Z","timestamp":1658966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T00:00:00Z","timestamp":1658966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005877","name":"Luonnontieteiden ja Tekniikan Tutkimuksen Toimikunta","doi-asserted-by":"publisher","award":["309048","322595"],"award-info":[{"award-number":["309048","322595"]}],"id":[{"id":"10.13039\/501100005877","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005877","name":"Luonnontieteiden ja Tekniikan Tutkimuksen Toimikunta","doi-asserted-by":"publisher","award":["328877"],"award-info":[{"award-number":["328877"]}],"id":[{"id":"10.13039\/501100005877","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["851093"],"award-info":[{"award-number":["851093"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of matching a string in a labeled graph. Previous research has shown that unless the<jats:italic>Orthogonal Vectors Hypothesis<\/jats:italic>(OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial time to answer queries efficiently (Equi et al. ICALP 2019, SOFSEM 2021). These conditional lower-bounds cover even deterministic graphs with binary alphabet, but there naturally exist also graph classes that are easy to index: For example,<jats:italic>Wheeler graphs<\/jats:italic>(Gagie et al.\u00a0<jats:italic>Theor. Comp. Sci.<\/jats:italic>2017) cover graphs admitting a Burrows-Wheeler transform -based indexing scheme. However, it is NP-complete to recognize if a graph is a Wheeler graph (Gibney, Thankachan, ESA 2019). We propose an approach to alleviate the construction bottleneck of Wheeler graphs. Rather than starting from an arbitrary graph, we study graphs induced from<jats:italic>multiple sequence alignments<\/jats:italic>().<jats:italic>Elastic degenerate strings<\/jats:italic>(Bernadini et al. SPIRE 2017, ICALP 2019) can be seen as such graphs, and we introduce here their generalization:<jats:italic>elastic founder graphs<\/jats:italic>. We first prove that even such induced graphs are hard to index under OVH. Then we introduce two subclasses, repeat-free and semi-repeat-free graphs, that are easy to index. We give a linear time algorithm to construct a repeat-free (non-elastic) founder graph from a gapless , and (parameterized) near-linear time algorithms to construct a semi-repeat-free (repeat-free, respectively) elastic founder graph from general . Finally, we show that repeat-free founder graphs admit a reduction to Wheeler graphs in polynomial time.<\/jats:p>","DOI":"10.1007\/s00453-022-01007-w","type":"journal-article","created":{"date-parts":[[2022,7,28]],"date-time":"2022-07-28T05:02:41Z","timestamp":1658984561000},"page":"1586-1623","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Algorithms and Complexity on Indexing Founder Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Massimo","family":"Equi","sequence":"first","affiliation":[]},{"given":"Tuukka","family":"Norri","sequence":"additional","affiliation":[]},{"given":"Jarno","family":"Alanko","sequence":"additional","affiliation":[]},{"given":"Bastien","family":"Cazaux","sequence":"additional","affiliation":[]},{"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4454-1493","authenticated-orcid":false,"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,28]]},"reference":[{"key":"1007_CR1","doi-asserted-by":"publisher","unstructured":"M\u00e4kinen, V., Cazaux, B., Equi, M., Norri, T., Tomescu, A.I.: Linear time construction of indexable founder block graphs. In: Kingsford, C., Pisanti, N. (eds.) 20th International Workshop on Algorithms in Bioinformatics, WABI 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference). LIPIcs, vol. 172. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2020.7. pp. 7:1\u20137:18","DOI":"10.4230\/LIPIcs.WABI.2020.7"},{"key":"1007_CR2","doi-asserted-by":"publisher","unstructured":"Equi, M., Norri, T., Alanko, J., Cazaux, B., Tomescu, A.I., M\u00e4kinen, V.: Algorithms and complexity on indexing elastic founder graphs. In: Ahn, H., Sadakane, K. (eds.) 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan. LIPIcs, vol. 212. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.20. pp. 20:1\u201320:18","DOI":"10.4230\/LIPIcs.ISAAC.2021.20"},{"issue":"2","key":"1007_CR3","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978). https:\/\/doi.org\/10.1145\/322063.322075","journal-title":"J. ACM"},{"issue":"6","key":"1007_CR4","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1093\/bib\/bbv099","volume":"17","author":"M Chatzou","year":"2015","unstructured":"Chatzou, M., Magis, C., Chang, J.-M., Kemena, C., Bussotti, G., Erb, I., Notredame, C.: Multiple sequence alignment modeling: methods and applications. Briefings in Bioinformatics 17(6), 1009\u20131023 (2015)","journal-title":"Briefings in Bioinformatics"},{"issue":"3","key":"1007_CR5","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. Journal of Computational Biology 17(3), 281\u2013308 (2010)","journal-title":"Journal of Computational Biology"},{"key":"1007_CR6","doi-asserted-by":"crossref","unstructured":"Na, J.C., Park, H., Crochemore, M., Holub, J., Iliopoulos, C.S., Mouchard, L., Park, K.: Suffix tree of alignment: An efficient index for similar data. In: Lecroq, T., Mouchard, L. (eds.) Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8288, pp. 337\u2013348. Springer, Germany (2013)","DOI":"10.1007\/978-3-642-45278-9_29"},{"key":"1007_CR7","doi-asserted-by":"crossref","unstructured":"Na, J.C., Park, H., Lee, S., Hong, M., Lecroq, T., Mouchard, L., Park, K.: Suffix array of alignment: A practical index for similar data. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) String Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings. Lecture Notes in Computer Science, vol. 8214, pp. 243\u2013254. Springer, Germany (2013)","DOI":"10.1007\/978-3-319-02432-5_27"},{"key":"1007_CR8","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.tcs.2015.08.008","volume":"638","author":"JC Na","year":"2016","unstructured":"Na, J.C., Kim, H., Park, H., Lecroq, T., L\u00e9onard, M., Mouchard, L., Park, K.: FM-index of alignment: A compressed index for similar strings. Theoretical Computer Science 638, 159\u2013170 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.08.008. (Pattern Matching, Text Data Structures and Compression)","journal-title":"Theoretical Computer Science"},{"key":"1007_CR9","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.tcs.2017.02.020","volume":"710","author":"J Na","year":"2016","unstructured":"Na, J., Kim, H., Min, S., Park, H., Lecroq, T., Leonard, M., Mouchard, L., Park, K.: FM-index of alignment with gaps. Theoretical Computer Science 710, 148\u2013157 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2017.02.020","journal-title":"Theoretical Computer Science"},{"key":"1007_CR10","volume-title":"Encyclopedia of Big Data Technologies","author":"T Gagie","year":"2019","unstructured":"Gagie, T., Navarro, G.: Compressed indexes for repetitive textual datasets. In: Sakr, S., Zomaya, A.Y. (eds.) Encyclopedia of Big Data Technologies. Springer, Germany (2019)"},{"issue":"1","key":"1007_CR11","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/3375890","volume":"67","author":"T Gagie","year":"2020","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully functional suffix trees and optimal text searching in bwt-runs bounded space. J. ACM 67(1), 2\u20131254 (2020)","journal-title":"J. ACM"},{"key":"1007_CR12","unstructured":"Marschall, T., Marz, M., Abeel, T., Dijkstra, L., Dutilh, B.E., Ghaffaari, A., Kersey, P., Kloosterman, W., M\u00e4kinen, V., Novak, A., et al.: Computational pan-genomics: status, promises and challenges. BioRxiv, 043430 (2016)"},{"issue":"1","key":"1007_CR13","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":"1007_CR14","doi-asserted-by":"crossref","unstructured":"Manber, U., Wu, S.: Approximate string matching with arbitrary costs for text and hypertext. In: IAPR Workshop on Structural and Syntactic Pattern Recognition, Bern, Switzerland, pp. 22\u201333 (1992)","DOI":"10.1142\/9789812797919_0002"},{"key":"1007_CR15","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":"1007_CR16","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. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). pp. 55:1\u201355:15"},{"key":"1007_CR17","doi-asserted-by":"crossref","unstructured":"Thachuk, C.: Indexing hypertext. Journal of Discrete Algorithms 18, 113\u2013122 (2013). Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011)","DOI":"10.1016\/j.jda.2012.10.001"},{"issue":"2","key":"1007_CR18","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","volume":"11","author":"J Sir\u00e9n","year":"2014","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V.: Indexing graphs for path queries with applications in genome research. IEEE\/ACM Transactions on Computational Biology and Bioinformatics 11(2), 375\u2013388 (2014)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"1007_CR19","doi-asserted-by":"publisher","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: Bures, T., Dondi, R., Gamper, J., Guerrini, G., Jurdzinski, T., Pahl, C., Sikora, F., Wong, P.W.H. (eds.) SOFSEM 2021: Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12607, pp. 608\u2013622. Springer, Germany (2021). https:\/\/doi.org\/10.1007\/978-3-030-67731-2_44","DOI":"10.1007\/978-3-030-67731-2_44"},{"key":"1007_CR20","doi-asserted-by":"publisher","unstructured":"Aoyama, K., Nakashima, Y., I, T., Inenaga, S., Bannai, H., Takeda, M.: Faster Online Elastic Degenerate String Matching. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 105. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.9. pp. 9:1\u20139:10. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/8701","DOI":"10.4230\/LIPIcs.CPM.2018.9"},{"key":"1007_CR21","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Gawrychowski, P., Pisanti, N., Pissis, S.P., Rosone, G.: Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 132. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.21. pp. 21:1\u201321:15. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/10597","DOI":"10.4230\/LIPIcs.ICALP.2019.21"},{"key":"1007_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2019.08.012","volume":"812","author":"G Bernardini","year":"2020","unstructured":"Bernardini, G., Pisanti, N., Pissis, S.P., Rosone, G.: Approximate pattern matching on elastic-degenerate text. Theor. Comput. Sci. 812, 109\u2013122 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.08.012","journal-title":"Theor. Comput. Sci."},{"key":"1007_CR23","doi-asserted-by":"publisher","unstructured":"Bernardini, G., Pisanti, N., Pissis, S.P., Rosone, G.: Pattern matching on elastic-degenerate text with errors. In: Fici, G., Sciortino, M., Venturini, R. (eds.) String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10508, pp. 74\u201390. Springer, Germany (2017). https:\/\/doi.org\/10.1007\/978-3-319-67428-5_7","DOI":"10.1007\/978-3-319-67428-5_7"},{"key":"1007_CR24","doi-asserted-by":"publisher","unstructured":"Iliopoulos, C.S., Kundu, R., Pissis, S.P.: Efficient pattern matching in elastic-degenerate texts. In: Drewes, F., Mart\u00edn-Vide, C., Truthe, B. (eds.) Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Ume\u00e5, Sweden, March 6-9, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10168, pp. 131\u2013142 (2017). https:\/\/doi.org\/10.1007\/978-3-319-53733-7_9","DOI":"10.1007\/978-3-319-53733-7_9"},{"key":"1007_CR25","doi-asserted-by":"crossref","unstructured":"Gibney, D.: An efficient elastic-degenerate text index? not likely. In: International Symposium on String Processing and Information Retrieval, pp. 76\u201388 (2020). Springer","DOI":"10.1007\/978-3-030-59212-7_6"},{"key":"1007_CR26","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. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2019). pp. 51:1\u201351:16"},{"issue":"1","key":"1007_CR27","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1186\/s13015-019-0147-6","volume":"14","author":"T Norri","year":"2019","unstructured":"Norri, T., Cazaux, B., Kosolobov, D., M\u00e4kinen, V.: Linear time minimum segmentation enables scalable founder reconstruction. Algorithms Mol. Biol. 14(1), 12:1-12:15 (2019)","journal-title":"Algorithms Mol. Biol."},{"key":"1007_CR28","doi-asserted-by":"crossref","unstructured":"Cazaux, B., Kosolobov, D., M\u00e4kinen, V., Norri, T.: Linear time maximum segmentation problems in column stream model. In: Brisaboa, N.R., Puglisi, S.J. (eds.) String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11811, pp. 322\u2013336. Springer, Germany (2019)","DOI":"10.1007\/978-3-030-32686-9_23"},{"key":"1007_CR29","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)","journal-title":"Theor. Comput. Sci."},{"key":"1007_CR30","doi-asserted-by":"crossref","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, January 5-8, 2020, pp. 911\u2013930. SIAM, USA (2020)","DOI":"10.1137\/1.9781611975994.55"},{"key":"1007_CR31","doi-asserted-by":"publisher","unstructured":"De\u00a0La\u00a0Briandais, R.: File searching using variable length keys. In: Papers Presented at the the March 3-5, 1959, Western Joint Computer Conference. IRE-AIEE-ACM \u201959 (Western), pp. 295\u2013298. Association for Computing Machinery, New York, NY, USA (1959). https:\/\/doi.org\/10.1145\/1457838.1457895","DOI":"10.1145\/1457838.1457895"},{"key":"1007_CR32","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 137\u2013143 (1997). IEEE","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"5","key":"1007_CR33","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993). https:\/\/doi.org\/10.1137\/0222058","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1007_CR34","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41(4), 589\u2013607 (2007). https:\/\/doi.org\/10.1007\/s00224-006-1198-x","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"1007_CR35","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"1007_CR36","unstructured":"Burrows, M., Wheeler, D.: A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"1007_CR37","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.ic.2011.03.007","volume":"213","author":"T Schnattinger","year":"2012","unstructured":"Schnattinger, T., Ohlebusch, E., Gog, S.: Bidirectional search in a string with wavelet trees and bidirectional matching statistics. Inf. Comput. 213, 13\u201322 (2012)","journal-title":"Inf. Comput."},{"issue":"2","key":"1007_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3381417","volume":"16","author":"D Belazzougui","year":"2020","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Linear-time string indexing and analysis in small space. ACM Trans. Algorithms 16(2), 1\u201354 (2020). https:\/\/doi.org\/10.1145\/3381417. (Article 17)","journal-title":"ACM Trans. Algorithms"},{"key":"1007_CR39","unstructured":"Belazzougui, D., Cunial, F.: Fully-functional bidirectional burrows-wheeler indexes and infinite-order de bruijn graphs. In: Pisanti, N., Pissis, S.P. (eds.) 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy. LIPIcs, vol. 128. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). pp. 10:1\u201310:15"},{"key":"1007_CR40","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proc. FOCS, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"1007_CR41","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional burrows-wheeler transform. In: European Symposium on Algorithms, pp. 133\u2013144 (2013). Springer","DOI":"10.1007\/978-3-642-40450-4_12"},{"key":"1007_CR42","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pp. 841\u2013850. ACM\/SIAM, USA (2003). http:\/\/dl.acm.org\/citation.cfm?id=644108.644250"},{"issue":"22","key":"1007_CR43","doi-asserted-by":"publisher","first-page":"4607","DOI":"10.1093\/bioinformatics\/btz268","volume":"35","author":"F Cunial","year":"2019","unstructured":"Cunial, F., Alanko, J., Belazzougui, D.: A framework for space-efficient variable-order markov models. Bioinformatics 35(22), 4607\u20134616 (2019)","journal-title":"Bioinformatics"},{"issue":"1\u20134","key":"1007_CR44","doi-asserted-by":"publisher","first-page":"41","DOI":"10.3233\/FI-2020-1947","volume":"175","author":"M Alzamel","year":"2020","unstructured":"Alzamel, M., Ayad, L.A.K., Bernardini, G., Grossi, R., Iliopoulos, C.S., Pisanti, N., Pissis, S.P., Rosone, G.: Comparing degenerate strings. Fundam. Informaticae 175(1\u20134), 41\u201358 (2020)","journal-title":"Fundam. Informaticae"},{"key":"1007_CR45","doi-asserted-by":"publisher","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: DeMillo, R.A. (ed.) Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pp. 135\u2013143. ACM, USA (1984). https:\/\/doi.org\/10.1145\/800057.808675","DOI":"10.1145\/800057.808675"},{"key":"1007_CR46","unstructured":"Iliopoulos, C.S., Radoszewski, J.: Truly subquadratic-time extension queries and periodicity detection in strings with uncertainties. In: Grossi, R., Lewenstein, M. (eds.) 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel. LIPIcs, vol. 54. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016). pp. 8:1\u20138:12"},{"issue":"2","key":"1007_CR47","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of k-SAT. Journal of Computer and System Sciences 62(2), 367\u2013375 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2\u20133","key":"1007_CR48","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. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1007_CR49","doi-asserted-by":"crossref","unstructured":"Rizzo, N., M\u00e4kinen, V.: Linear time construction of indexable elastic founder graphs. In: Proc. 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), Springer, LNCS, vol. 13270 (2022). pp. 480\u2013493","DOI":"10.1007\/978-3-031-06678-8_35"},{"key":"1007_CR50","unstructured":"Rizzo, N., M\u00e4kinen, V.: Indexable elastic founder graphs of minimum height. In: Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, LIPIcs, vol. 223 (2022). pp. 19:1\u201319:19"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01007-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01007-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01007-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T01:31:15Z","timestamp":1727659875000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01007-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,28]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1007"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01007-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,28]]},"assertion":[{"value":"6 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}