{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T19:53:13Z","timestamp":1770493993912,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["POIR.04.04.00-00-24BA\/16"],"award-info":[{"award-number":["POIR.04.04.00-00-24BA\/16"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["POIR.04.04.00-00-24BA\/16"],"award-info":[{"award-number":["POIR.04.04.00-00-24BA\/16"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["872539"],"award-info":[{"award-number":["872539"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["956229"],"award-info":[{"award-number":["956229"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["592\/17"],"award-info":[{"award-number":["592\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1652303"],"award-info":[{"award-number":["1652303"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1909046"],"award-info":[{"award-number":["1909046"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1934846"],"award-info":[{"award-number":["1934846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/D\/ST6\/03991"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/03991"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2018\/31\/D\/ST6\/03991"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/03991"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Sequence mappability is an important task in genome resequencing. In the (<jats:italic>k<\/jats:italic>,\u00a0<jats:italic>m<\/jats:italic>)-mappability problem, for a given sequence <jats:italic>T<\/jats:italic> of length <jats:italic>n<\/jats:italic>, the goal is to compute a table whose <jats:italic>i<\/jats:italic>th entry is the number of indices <jats:inline-formula><jats:alternatives><jats:tex-math>$$j \\ne i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>j<\/mml:mi>\n                    <mml:mo>\u2260<\/mml:mo>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that the length-<jats:italic>m<\/jats:italic> substrings of <jats:italic>T<\/jats:italic> starting at positions <jats:italic>i<\/jats:italic> and <jats:italic>j<\/jats:italic> have at most <jats:italic>k<\/jats:italic> mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of <jats:inline-formula><jats:alternatives><jats:tex-math>$$k=1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k=O(1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, works in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> space and, with high probability, in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n \\cdot \\min \\{m^k,\\log ^k n\\})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:mo>min<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>{<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>m<\/mml:mi>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:msup>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>}<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Our algorithm requires a careful adaptation of the <jats:italic>k<\/jats:italic>-errata trees of Cole et al.\u00a0[STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the all-pairs Hamming distance problem introduced by Crochemore et al.\u00a0[WABI 2017]. We further develop <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithms to compute <jats:italic>all<\/jats:italic> (<jats:italic>k<\/jats:italic>,\u00a0<jats:italic>m<\/jats:italic>)-mappability tables for a fixed <jats:italic>m<\/jats:italic> and all <jats:inline-formula><jats:alternatives><jats:tex-math>$$k\\in \\{0,\\ldots ,m\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or a fixed <jats:italic>k<\/jats:italic> and all <jats:inline-formula><jats:alternatives><jats:tex-math>$$m\\in \\{k,\\ldots ,n\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>\u2026<\/mml:mo>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we show that, for <jats:inline-formula><jats:alternatives><jats:tex-math>$$k,m = \\Theta (\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the (<jats:italic>k<\/jats:italic>,\u00a0<jats:italic>m<\/jats:italic>)-mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time\u00a0Hypothesis\u00a0fails. This is an improved and extended version of a paper presented at SPIRE 2018.<\/jats:p>","DOI":"10.1007\/s00453-022-00934-y","type":"journal-article","created":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T12:02:52Z","timestamp":1643803372000},"page":"1418-1440","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Computation of Sequence Mappability"],"prefix":"10.1007","volume":"84","author":[{"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2207-0053","authenticated-orcid":false,"given":"Juliusz","family":"Straszy\u0144ski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,2]]},"reference":[{"key":"934_CR1","doi-asserted-by":"publisher","unstructured":"Alamro, H., Ayad, L.A.K., Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P.: Longest common prefixes with $$k$$-mismatches and applications. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, LNCS, vol. 10706, pp. 636\u2013649. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-73117-9_45","DOI":"10.1007\/978-3-319-73117-9_45"},{"key":"934_CR2","doi-asserted-by":"publisher","unstructured":"Alzamel, M., Charalampopoulos, P., Iliopoulos, C.S., Kociumaka, T., Pissis, S.P., Radoszewski, J., Straszy\u0144ski, J.: Efficient computation of sequence mappability. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, LNCS, vol. 11147, pp. 12\u201326. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_2","DOI":"10.1007\/978-3-030-00479-8_2"},{"key":"934_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2019.04.026","volume":"812","author":"M Alzamel","year":"2020","unstructured":"Alzamel, M., Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P., Radoszewski, J., Sung, W.: Faster algorithms for 1-mappability of a sequence. Theor. Comput. Sci. 812, 2\u201312 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.04.026","journal-title":"Theor. Comput. Sci."},{"key":"934_CR4","doi-asserted-by":"publisher","unstructured":"Amir, A., Boneh, I., Kondratovsky, E.: The k-mappability problem revisited. In: Gawrychowski, P., Starikovskaya, T. (eds.) 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, LIPIcs, vol. 191, pp. 5:1\u20135:20. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2021.5","DOI":"10.4230\/LIPIcs.CPM.2021.5"},{"key":"934_CR5","doi-asserted-by":"publisher","unstructured":"Antoniou, P., Daykin, J.W., Iliopoulos, C.S., Kourie, D., Mouchard, L., Pissis, S.P.: Mapping uniquely occurring short sequences derived from high throughput technologies to a reference genome. In: 9th International Conference on Information Technology and Applications in Biomedicine, ITAB 2009, pp. 1\u20134. IEEE (2009). https:\/\/doi.org\/10.1109\/itab.2009.5394394","DOI":"10.1109\/itab.2009.5394394"},{"key":"934_CR6","doi-asserted-by":"publisher","unstructured":"Ayad, L.A.K., Barton, C., Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P.: Longest common prefixes with $$k$$-errors and applications. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, LNCS, vol. 11147, pp. 27\u201341. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_3","DOI":"10.1007\/978-3-030-00479-8_3"},{"issue":"2","key":"934_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"MA Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005). https:\/\/doi.org\/10.1016\/j.jalgor.2005.08.001","journal-title":"J. Algorithms"},{"issue":"1","key":"934_CR8","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/s13015-017-0119-7","volume":"13","author":"JA Carri\u00e7o","year":"2018","unstructured":"Carri\u00e7o, J.A., Crochemore, M., Francisco, A.P., Pissis, S.P., Ribeiro-Gon\u00e7alves, B., Vaz, C.: Fast phylogenetic inference from typing data. Algorithms Mol. Biol. 13(1), 4 (2018). https:\/\/doi.org\/10.1186\/s13015-017-0119-7","journal-title":"Algorithms Mol. Biol."},{"key":"934_CR9","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Linear-time algorithm for long LCF with $$k$$ mismatches. In: Navarro, G., Sankoff, D., Zhu, B. (eds.) 29th Annual Symposium on Combinatorial Pattern Matching, CPM 2018, LIPIcs, vol. 105, pp. 23:1\u201323:16. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2018.23","DOI":"10.4230\/LIPIcs.CPM.2018.23"},{"key":"934_CR10","doi-asserted-by":"publisher","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Babai, L. (ed.) 36th Annual ACM Symposium on Theory of Computing, STOC 2004, pp. 91\u2013100. ACM (2004). https:\/\/doi.org\/10.1145\/1007352.1007374","DOI":"10.1145\/1007352.1007374"},{"key":"934_CR11","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Francisco, A.P., Pissis, S.P., Vaz, C.: Towards distance-based phylogenetic inference in average-case linear-time. In: Schwartz, R., Reinert, K. (eds.) 17th International Workshop on Algorithms in Bioinformatics, WABI 2017, LIPIcs, vol.\u00a088, pp. 9:1\u20139:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2017.9","DOI":"10.4230\/LIPIcs.WABI.2017.9"},{"issue":"1","key":"934_CR12","doi-asserted-by":"publisher","first-page":"e30377","DOI":"10.1371\/journal.pone.0030377","volume":"7","author":"T Derrien","year":"2012","unstructured":"Derrien, T., Estell\u00e9, J., Sola, S.M., Knowles, D.G., Raineri, E., Guig\u00f3, R., Ribeca, P.: Fast computation and applications of genome mappability. PLoS ONE 7(1), e30377 (2012). https:\/\/doi.org\/10.1371\/journal.pone.0030377","journal-title":"PLoS ONE"},{"key":"934_CR13","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: A new universal class of hash functions and dynamic hashing in real time. In: Paterson, M. (ed.) 17th International Colloquium on Automata, Languages and Programming, ICALP 1990, LNCS, vol. 443, pp. 6\u201319. Springer (1990). https:\/\/doi.org\/10.1007\/BFb0032018","DOI":"10.1007\/BFb0032018"},{"issue":"6","key":"934_CR14","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000). https:\/\/doi.org\/10.1145\/355541.355547","journal-title":"J. ACM"},{"issue":"6\u20138","key":"934_CR15","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/j.ipl.2015.03.006","volume":"115","author":"T Flouri","year":"2015","unstructured":"Flouri, T., Giaquinta, E., Kobert, K., Ukkonen, E.: Longest common substrings with $$k$$ mismatches. Inf. Process. Lett. 115(6\u20138), 643\u2013647 (2015). https:\/\/doi.org\/10.1016\/j.ipl.2015.03.006","journal-title":"Inf. Process. Lett."},{"issue":"24","key":"934_CR16","doi-asserted-by":"publisher","first-page":"3169","DOI":"10.1093\/bioinformatics\/bts605","volume":"28","author":"NA Fonseca","year":"2012","unstructured":"Fonseca, N.A., Rung, J., Brazma, A., Marioni, J.C.: Tools for mapping high-throughput sequencing data. Bioinformatics 28(24), 3169\u20133177 (2012). https:\/\/doi.org\/10.1093\/bioinformatics\/bts605","journal-title":"Bioinformatics"},{"issue":"1","key":"934_CR17","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1186\/1471-2105-10-152","volume":"10","author":"AP Francisco","year":"2009","unstructured":"Francisco, A.P., Bugalho, M., Ramirez, M., Carri\u00e7o, J.A.: Global optimal eBURST analysis of multilocus typing data using a graphic matroid approach. BMC Bioinform. 10(1), 152 (2009). https:\/\/doi.org\/10.1186\/1471-2105-10-152","journal-title":"BMC Bioinform."},{"key":"934_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0304-3975(87)90042-9","volume":"51","author":"Z Galil","year":"1987","unstructured":"Galil, Z., Giancarlo, R.: Parallel string matching with $$k$$ mismatches. Theor. Comput. Sci. 51, 341\u2013348 (1987). https:\/\/doi.org\/10.1016\/0304-3975(87)90042-9","journal-title":"Theor. Comput. Sci."},{"key":"934_CR19","doi-asserted-by":"publisher","unstructured":"Gog, S., Venturini, R.: Fast and compact Hamming distance index. In: Perego, R., Sebastiani, F., Aslam, J.A., Ruthven, I., Zobel, J. (eds.) 39th International ACM-SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2016, pp. 285\u2013294. ACM (2016). https:\/\/doi.org\/10.1145\/2911451.2911523","DOI":"10.1145\/2911451.2911523"},{"key":"934_CR20","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2978","author":"S Grabowski","year":"2021","unstructured":"Grabowski, S., Kowalski, T.M.: Algorithms for all-pairs Hamming distance based similarity. Softw. Pract. Exp. (2021). https:\/\/doi.org\/10.1002\/spe.2978","journal-title":"Softw. Pract. Exp."},{"key":"934_CR21","doi-asserted-by":"publisher","unstructured":"Hooshmand, S., Abedin, P., Gibney, D., Aluru, S., Thankachan, S.V.: Faster computation of genome mappability with one mismatch. In: 8th IEEE International Conference on Computational Advances in Bio and Medical Sciences, ICCABS 2018, p.\u00a01. IEEE Computer Society (2018). https:\/\/doi.org\/10.1109\/ICCABS.2018.8541897","DOI":"10.1109\/ICCABS.2018.8541897"},{"issue":"2","key":"934_CR22","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. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"934_CR23","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"934_CR24","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006). https:\/\/doi.org\/10.1145\/1217856.1217858","journal-title":"J. ACM"},{"issue":"2","key":"934_CR25","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987). https:\/\/doi.org\/10.1147\/rd.312.0249","journal-title":"IBM J. Res. Dev."},{"key":"934_CR26","doi-asserted-by":"publisher","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) 12th Annual Symposium on Combinatorial Pattern Matching, CPM 2001, LNCS, vol. 2089, pp. 181\u2013192. Springer (2001). https:\/\/doi.org\/10.1007\/3-540-48194-X_17","DOI":"10.1007\/3-540-48194-X_17"},{"issue":"6","key":"934_CR27","doi-asserted-by":"publisher","first-page":"2633","DOI":"10.1007\/s00453-019-00548-x","volume":"81","author":"T Kociumaka","year":"2019","unstructured":"Kociumaka, T., Radoszewski, J., Starikovskaya, T.A.: Longest common substring with approximately $$k$$ mismatches. Algorithmica 81(6), 2633\u20132652 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00548-x","journal-title":"Algorithmica"},{"key":"934_CR28","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"GM Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with $$k$$ mismatches. Theor. Comput. Sci. 43, 239\u2013249 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90178-7","journal-title":"Theor. Comput. Sci."},{"key":"934_CR29","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.ipl.2019.02.003","volume":"146","author":"V M\u00e4kinen","year":"2019","unstructured":"M\u00e4kinen, V., Norri, T.: Applying the positional Burrows\u2013Wheeler transform to all-pairs Hamming distance. Inf. Process. Lett. 146, 17\u201319 (2019). https:\/\/doi.org\/10.1016\/j.ipl.2019.02.003","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"934_CR30","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."},{"key":"934_CR31","doi-asserted-by":"publisher","unstructured":"Manzini, G.: Longest common prefix with mismatches. In: Iliopoulos, C.S., Puglisi, S.J., Yilmaz, E. (eds.) 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015, LNCS, vol. 9309, pp. 299\u2013310. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_29","DOI":"10.1007\/978-3-319-23826-5_29"},{"issue":"12","key":"934_CR32","doi-asserted-by":"publisher","first-page":"3687","DOI":"10.1093\/bioinformatics\/btaa222","volume":"36","author":"C Pockrandt","year":"2020","unstructured":"Pockrandt, C., Alzamel, M., Iliopoulos, C.S., Reinert, K.: Genmap: ultra-fast computation of genome mappability. Bioinformatics 36(12), 3687\u20133692 (2020). https:\/\/doi.org\/10.1093\/bioinformatics\/btaa222","journal-title":"Bioinformatics"},{"key":"934_CR33","doi-asserted-by":"publisher","unstructured":"Thankachan, S.V., Aluru, C., Chockalingam, S.P., Aluru, S.: Algorithmic framework for approximate matching under bounded edits with applications to sequence analysis. In: Raphael, B.J. (ed.) 22nd Annual International Conference on Research in Computational Molecular Biology, RECOMB 2018, LNCS, vol. 10812, pp. 211\u2013224. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-319-89929-9_14","DOI":"10.1007\/978-3-319-89929-9_14"},{"issue":"6","key":"934_CR34","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1089\/cmb.2015.0235","volume":"23","author":"SV Thankachan","year":"2016","unstructured":"Thankachan, S.V., Apostolico, A., Aluru, S.: A provably efficient algorithm for the k-mismatch average common substring problem. J. Comput. Biol. 23(6), 472\u2013482 (2016). https:\/\/doi.org\/10.1089\/cmb.2015.0235","journal-title":"J. Comput. Biol."},{"key":"934_CR35","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbaa147","author":"C Vaz","year":"2021","unstructured":"Vaz, C., Nascimento, M., Carri\u00e7o, J.A., Rocher, T., Francisco, A.P.: Distance-based phylogenetic inference from typing data: a unifying view. Brief. Bioinform. (2021). https:\/\/doi.org\/10.1093\/bib\/bbaa147","journal-title":"Brief. Bioinform."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00934-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00934-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00934-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:04:48Z","timestamp":1651122288000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00934-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,2]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["934"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00934-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,2]]},"assertion":[{"value":"29 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}