{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:01Z","timestamp":1759639081785,"version":"3.40.3"},"publisher-location":"Cham","reference-count":85,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030592110"},{"type":"electronic","value":"9783030592127"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-59212-7_12","type":"book-chapter","created":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:05:34Z","timestamp":1600250734000},"page":"155-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction"],"prefix":"10.1007","author":[{"given":"Ramtin","family":"Afshar","sequence":"first","affiliation":[]},{"given":"Amihood","family":"Amir","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0664-9145","authenticated-orcid":false,"given":"Pedro","family":"Matias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,17]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Acharya, J., Das, H., Milenkovic, O., Orlitsky, A., Pan, S.: Quadratic-backtracking algorithm for string reconstruction from substring compositions. In: 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, 29 June\u20134 July 2014, pp. 1296\u20131300. IEEE (2014). \nhttps:\/\/doi.org\/10.1109\/ISIT.2014.6875042","DOI":"10.1109\/ISIT.2014.6875042"},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"1340","DOI":"10.1137\/140962486","volume":"29","author":"J Acharya","year":"2015","unstructured":"Acharya, J., Das, H., Milenkovic, O., Orlitsky, A., Pan, S.: String reconstruction from substring compositions. SIAM J. Discrete Math. 29(3), 1340\u20131371 (2015). \nhttps:\/\/doi.org\/10.1137\/140962486","journal-title":"SIAM J. Discrete Math."},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40273-9_1","volume-title":"Space-Efficient Data Structures, Streams, and Algorithms","author":"P Afshani","year":"2013","unstructured":"Afshani, P., Agrawal, M., Doerr, B., Doerr, C., Larsen, K.G., Mehlhorn, K.: The query complexity of finding a hidden permutation. In: Brodnik, A., L\u00f3pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 1\u201311. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-40273-9_1"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"Afshani, P., van Duijn, I., Killmann, R., Nielsen, J.S.: A lower bound for jumbled indexing. In: 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 592\u2013606 (2020). \nhttps:\/\/doi.org\/10.1137\/1.9781611975994.36","DOI":"10.1137\/1.9781611975994.36"},{"key":"12_CR5","unstructured":"Afshar, R., Amir, A., Goodrich, M.T., Matias, P.: Adaptive exact learning in a mixed-up world: dealing with periodicity errors, and jumbled-index queries in string reconstruction. arXiv preprint \narXiv:2007.08787\n\n (2029). \nhttps:\/\/arxiv.org\/abs\/2007.08787"},{"key":"12_CR6","unstructured":"Amir, A., Eisenberg, E., Levy, A., Porat, E., Shapira, N.: Cycle detection and correction. ACM Trans. Alg. 9(1) (2012). Article no. 13"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/j.tcs.2016.04.030","volume":"656","author":"A Amir","year":"2016","unstructured":"Amir, A., Apostolico, A., Hirst, T., Landau, G.M., Lewenstein, N., Rozenberg, L.: Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings. Theor. Comput. Sci. 656, 146\u2013159 (2016). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2016.04.030\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S030439751630069X","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"12_CR8","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.jcss.2009.03.001","volume":"75","author":"A Amir","year":"2009","unstructured":"Amir, A., et al.: Pattern matching with address errors: rearrangement distances. J. Comput. Syst. Sci. 75(6), 359\u2013370 (2009). \nhttps:\/\/doi.org\/10.1016\/j.jcss.2009.03.001","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR9","doi-asserted-by":"publisher","unstructured":"Amir, A., Butman, A., Porat, E.: On the relationship between histogram indexing and block-mass indexing. Philos. Trans. Roy. Soc. Math. Phys. Eng. Sci. 372(2016) (2014). \nhttps:\/\/doi.org\/10.1098\/rsta.2013.0132\n\n. \nhttps:\/\/royalsocietypublishing.org\/doi\/abs\/10.1098\/rsta.2013.0132","DOI":"10.1098\/rsta.2013.0132"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-662-43948-7_10","volume-title":"Automata, Languages, and Programming","author":"A Amir","year":"2014","unstructured":"Amir, A., Chan, T.M., Lewenstein, M., Lewenstein, N.: On hardness of jumbled indexing. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 114\u2013125. Springer, Heidelberg (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-43948-7_10"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-540-75520-3_11","volume-title":"Algorithms \u2013 ESA 2007","author":"A Amir","year":"2007","unstructured":"Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 99\u2013110. Springer, Heidelberg (2007). \nhttps:\/\/doi.org\/10.1007\/978-3-540-75520-3_11"},{"issue":"4","key":"12_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1023\/A:1022821128753","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn. 2(4), 319\u2013342 (1988). \nhttps:\/\/doi.org\/10.1023\/A:1022821128753","journal-title":"Mach. Learn."},{"issue":"3","key":"12_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1089\/cmb.1996.3.425","volume":"3","author":"R Arratia","year":"1996","unstructured":"Arratia, R., Martin, D., Reinert, G., Waterman, M.S.: Poisson process approximation for sequence repeats and sequencing by hybridization. J. Comput. Biol. 3(3), 425\u2013463 (1996). \nhttps:\/\/doi.org\/10.1089\/cmb.1996.3.425","journal-title":"J. Comput. Biol."},{"key":"12_CR14","unstructured":"Batu, T., Kannan, S., Khanna, S., McGregor, A.: Reconstructing strings from random traces. In: Munro, J.I. (ed.) Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, 11\u201314 January 2004, pp. 910\u2013918. SIAM (2004). \nhttp:\/\/dl.acm.org\/citation.cfm?id=982792.982929"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1093\/nar\/27.2.573","volume":"27","author":"G Benson","year":"1999","unstructured":"Benson, G.: Tandem repeats finder: a program to analyze DNA sequence. Nucleic Acids Res. 27(2), 573\u2013580 (1999)","journal-title":"Nucleic Acids Res."},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"4828","DOI":"10.1093\/nar\/22.22.4828","volume":"22","author":"G Benson","year":"1994","unstructured":"Benson, G., Waterman, M.: A method for fast database search for all k-nucleotide repeats. Nucleic Acids Res. 22, 4828\u20134836 (1994)","journal-title":"Nucleic Acids Res."},{"issue":"3","key":"12_CR17","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","volume":"5","author":"JL Bentley","year":"1976","unstructured":"Bentley, J.L., Yao, A.C.: An almost optimal algorithm for unbounded searching. Inf. Process. Lett. 5(3), 82\u201387 (1976). \nhttps:\/\/doi.org\/10.1016\/0020-0190(76)90071-5","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"12_CR18","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1006\/inco.2000.3017","volume":"168","author":"A Bernasconi","year":"2001","unstructured":"Bernasconi, A., Damm, C., Shparlinski, I.: Circuit and decision tree complexity of some number theoretic problems. Inf. Comput. 168(2), 113\u2013124 (2001). \nhttps:\/\/doi.org\/10.1006\/inco.2000.3017\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540100930177","journal-title":"Inf. Comput."},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Bresler, G., Bresler, M., Tse, D.: Optimal assembly for high throughput shotgun sequencing. BMC Bioinform. 14(2013). Article number. S18. \nhttps:\/\/doi.org\/10.1186\/1471-2105-14-S5-S18","DOI":"10.1186\/1471-2105-14-S5-S18"},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23(2), 357\u2013374 (2012). \nhttps:\/\/doi.org\/10.1142\/S0129054112400175","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"12_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.ipl.2004.09.002","volume":"92","author":"A Butman","year":"2004","unstructured":"Butman, A., Eres, R., Landau, G.M.: Scaled and permuted string matching. Inf. Process. Lett. 92(6), 293\u2013297 (2004). \nhttps:\/\/doi.org\/10.1016\/j.ipl.2004.09.002","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"12_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(99)00334-5","volume":"259","author":"A Carpi","year":"2001","unstructured":"Carpi, A., de Luca, A.: Words and special factors. Theor. Comput. Sci. 259(1\u20132), 145\u2013182 (2001). \nhttps:\/\/doi.org\/10.1016\/S0304-3975(99)00334-5","journal-title":"Theor. Comput. Sci."},{"issue":"232","key":"12_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1080\/14786444908646287","volume":"34","author":"A Cayley","year":"1849","unstructured":"Cayley, A.: LXXVII. Note on the theory of permutations. Lond. Edinb. Dublin Philos. Mag. J. Sci. 34(232), 527\u2013529 (1849)","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"issue":"11","key":"12_CR24","doi-asserted-by":"publisher","first-page":"7166","DOI":"10.1109\/TIT.2017.2747557","volume":"63","author":"Z Chang","year":"2017","unstructured":"Chang, Z., Chrisnata, J., Ezerman, M.F., Kiah, H.M.: Rates of DNA sequence profiles for practical values of read lengths. IEEE Trans. Inf. Theory 63(11), 7166\u20137177 (2017). \nhttps:\/\/doi.org\/10.1109\/TIT.2017.2747557","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"12_CR25","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1016\/j.artint.2010.02.003","volume":"174","author":"SS Choi","year":"2010","unstructured":"Choi, S.S., Kim, J.H.: Optimal query complexity bounds for finding graphs. Artif. Intell. 174(9), 551\u2013569 (2010). \nhttps:\/\/doi.org\/10.1016\/j.artint.2010.02.003\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0004370210000251","journal-title":"Artif. Intell."},{"key":"12_CR26","unstructured":"Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Searching for jumbled patterns in strings. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2009, Prague, Czech Republic, 31 August\u20132 September 2009, pp. 105\u2013117. Prague Stringology Club, Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague (2009). \nhttp:\/\/www.stringology.org\/event\/2009\/p10.html"},{"key":"12_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/3-540-44692-3_3","volume-title":"Computer Analysis of Images and Patterns","author":"L Cieplinski","year":"2001","unstructured":"Cieplinski, L.: MPEG-7 color descriptors and their applications. In: Skarbek, W. (ed.) CAIP 2001. LNCS, vol. 2124, pp. 11\u201320. Springer, Heidelberg (2001). \nhttps:\/\/doi.org\/10.1007\/3-540-44692-3_3"},{"key":"12_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1007\/978-3-642-31155-0_34","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"R Cleve","year":"2012","unstructured":"Cleve, R., et al.: Reconstructing strings from substrings with quantum queries. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 388\u2013397. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-31155-0_34"},{"key":"12_CR29","unstructured":"Dakic, T.: On the turnpike problem. Simon Fraser University BC, Canada (2000)"},{"key":"12_CR30","unstructured":"Deininger, P.: SINEs: short interspersed repeated DNA elements in higher eukaryotes. In: Berg, D., Howe, M. (eds.) Mobile DNA, Chap. 27, pp. 619\u2013636. American Society for Microbiology (1989)"},{"issue":"2","key":"12_CR31","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s10791-007-9039-3","volume":"11","author":"T Deselaers","year":"2008","unstructured":"Deselaers, T., Keysers, D., Ney, H.: Features for image retrieval: an experimental comparison. Inf. Retrieval 11(2), 77\u2013107 (2008). \nhttps:\/\/doi.org\/10.1007\/s10791-007-9039-3","journal-title":"Inf. Retrieval"},{"key":"12_CR32","doi-asserted-by":"publisher","unstructured":"Dobzinski, S., Vondrak, J.: From query complexity to computational complexity. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 1107\u20131116. ACM, New York (2012). \nhttps:\/\/doi.org\/10.1145\/2213977.2214076","DOI":"10.1145\/2213977.2214076"},{"issue":"7","key":"12_CR33","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1089\/cmb.2007.0018","volume":"14","author":"NO Domani\u00e7","year":"2007","unstructured":"Domani\u00e7, N.O., Preparata, F.P.: A novel approach to the detection of genomic approximate tandem repeats in the levenshtein metric. J. Comput. Biol. 14(7), 873\u2013891 (2007)","journal-title":"J. Comput. Biol."},{"issue":"2","key":"12_CR34","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0097-3165(03)00103-1","volume":"103","author":"M Dud\u00edk","year":"2003","unstructured":"Dud\u00edk, M., Schulman, L.J.: Reconstruction from subsequences. J. Comb. Theory Ser. A 103(2), 337\u2013348 (2003). \nhttps:\/\/doi.org\/10.1016\/S0097-3165(03)00103-1","journal-title":"J. Comb. Theory Ser. A"},{"issue":"4","key":"12_CR35","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1158\/1078-0432.CCR-15-1678","volume":"22","author":"J Dudley","year":"2016","unstructured":"Dudley, J., Lin, M.T., Le, D., Eshleman, J.R.: Microsatellite instability as a biomarker for PD-1 blockade. Clin. Cancer Res. 22(4), 813\u2013820 (2016)","journal-title":"Clin. Cancer Res."},{"key":"12_CR36","doi-asserted-by":"publisher","unstructured":"Elishco, O., Gabrys, R., M\u00e9dard, M., Yaakobi, E.: Repeat-free codes. In: IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7\u201312 July 2019, pp. 932\u2013936. IEEE (2019). \nhttps:\/\/doi.org\/10.1109\/ISIT.2019.8849483","DOI":"10.1109\/ISIT.2019.8849483"},{"issue":"6","key":"12_CR37","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1089\/cmb.2004.11.1050","volume":"11","author":"R Eres","year":"2004","unstructured":"Eres, R., Landau, G.M., Parida, L.: Permutation pattern discovery in biosequences. J. Comput. Biol. 11(6), 1050\u20131060 (2004). \nhttps:\/\/doi.org\/10.1089\/cmb.2004.11.1050","journal-title":"J. Comput. Biol."},{"issue":"1\u20133","key":"12_CR38","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.tcs.2006.03.006","volume":"359","author":"G Fici","year":"2006","unstructured":"Fici, G., Mignosi, F., Restivo, A., Sciortino, M.: Word assembly through minimal forbidden words. Theor. Comput. Sci. 359(1\u20133), 214\u2013230 (2006). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2006.03.006","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"12_CR39","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16(1), 109\u2013114 (1965)","journal-title":"Proc. Am. Math. Soc."},{"key":"12_CR40","doi-asserted-by":"publisher","unstructured":"Gabrys, R., Milenkovic, O.: The hybrid k-Deck problem: reconstructing sequences from short and long traces. In: 2017 IEEE International Symposium on Information Theory, ISIT 2017, Aachen, Germany, 25\u201330 June 2017, pp. 1306\u20131310. IEEE (2017). \nhttps:\/\/doi.org\/10.1109\/ISIT.2017.8006740","DOI":"10.1109\/ISIT.2017.8006740"},{"key":"12_CR41","doi-asserted-by":"publisher","unstructured":"Gabrys, R., Milenkovic, O.: Unique reconstruction of coded sequences from multiset substring spectra. In: 2018 IEEE International Symposium on Information Theory, ISIT 2018, Vail, CO, USA, 17\u201322 June 2018, pp. 2540\u20132544. IEEE (2018). \nhttps:\/\/doi.org\/10.1109\/ISIT.2018.8437909","DOI":"10.1109\/ISIT.2018.8437909"},{"key":"12_CR42","doi-asserted-by":"publisher","unstructured":"Ganguly, S., Mossel, E., R\u00e1cz, M.Z.: Sequence assembly from corrupted shotgun reads. In: IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 10\u201315 July 2016, pp. 265\u2013269. IEEE (2016). \nhttps:\/\/doi.org\/10.1109\/ISIT.2016.7541302","DOI":"10.1109\/ISIT.2016.7541302"},{"key":"12_CR43","unstructured":"Holenstein, T., Mitzenmacher, M., Panigrahy, R., Wieder, U.: Trace reconstruction with constant deletion probability and related results. In: Teng, S. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, 20\u201322 January 2008, pp. 389\u2013398. SIAM (2008). \nhttp:\/\/dl.acm.org\/citation.cfm?id=1347082.1347125"},{"key":"12_CR44","unstructured":"Iwama, K., Teruyama, J., Tsuyama, S.: Reconstructing strings from substrings: optimal randomized and average-case algorithms (2018)"},{"key":"12_CR45","doi-asserted-by":"publisher","unstructured":"Jeong, K., Bandeira, N., Kim, S., Pevzner, P.A.: Gapped spectral dictionaries and their applications for database searches of tandem mass spectra. Mol Cell Proteomics (2011). \nhttps:\/\/doi.org\/10.1074\/mcp.M110.002220","DOI":"10.1074\/mcp.M110.002220"},{"key":"12_CR46","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M Jerrum","year":"1985","unstructured":"Jerrum, M.: The complexity of finding minimum-length generator sequences. Theor. Comput. Sci. 36, 265\u2013289 (1985). \nhttps:\/\/doi.org\/10.1016\/0304-3975(85)90047-7","journal-title":"Theor. Comput. Sci."},{"key":"12_CR47","unstructured":"Kalashnik, L.: The reconstruction of a word from fragments. In: Numerical Mathematics and Computer Technology, pp. 56\u201357 (1973)"},{"key":"12_CR48","doi-asserted-by":"publisher","unstructured":"Kannan, S., McGregor, A.: More on reconstructing strings from random traces: insertions and deletions. In: Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 2005, Adelaide, South Australia, Australia, 4\u20139 September 2005, pp. 297\u2013301. IEEE (2005). \nhttps:\/\/doi.org\/10.1109\/ISIT.2005.1523342","DOI":"10.1109\/ISIT.2005.1523342"},{"issue":"6","key":"12_CR49","doi-asserted-by":"publisher","first-page":"3125","DOI":"10.1109\/TIT.2016.2555321","volume":"62","author":"HM Kiah","year":"2016","unstructured":"Kiah, H.M., Puleo, G.J., Milenkovic, O.: Codes for DNA sequence profiles. IEEE Trans. Inf. Theory 62(6), 3125\u20133146 (2016). \nhttps:\/\/doi.org\/10.1109\/TIT.2016.2555321","journal-title":"IEEE Trans. Inf. Theory"},{"key":"12_CR50","doi-asserted-by":"publisher","first-page":"1391","DOI":"10.1074\/mcp.M800535-MCP200","volume":"8","author":"S Kim","year":"2009","unstructured":"Kim, S., Bandeira, N., Pevzner, P.A.: Spectral profiles: a novel representation of tandem mass spectra and its applications for de novo peptide sequencing and identification. Mol. Cell. Proteomics 8, 1391\u20131400 (2009)","journal-title":"Mol. Cell. Proteomics"},{"issue":"1","key":"12_CR51","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1074\/mcp.M800103-MCP200","volume":"8","author":"S Kim","year":"2009","unstructured":"Kim, S., Gupta, N., Bandeira, N., Pevzner, P.A.: Spectral dictionaries: integrating de novo peptide sequencing with database search of tandem mass spectra. Mol. Cell. Proteomics 8(1), 53\u201369 (2009)","journal-title":"Mol. Cell. Proteomics"},{"key":"12_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/978-3-642-40450-4_53","volume-title":"Algorithms \u2013 ESA 2013","author":"T Kociumaka","year":"2013","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Efficient indexes for jumbled pattern matching with constant-sized alphabet. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 625\u2013636. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-40450-4_53"},{"key":"12_CR53","doi-asserted-by":"publisher","first-page":"3672","DOI":"10.1093\/nar\/gkg617","volume":"31","author":"R Kolpakov","year":"2003","unstructured":"Kolpakov, R., Kucherov, G.: mreps: efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Res. 31, 3672\u20133678 (2003). \nhttp:\/\/www.loria.fr\/mreps\/","journal-title":"Nucleic Acids Res."},{"issue":"2","key":"12_CR54","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jcta.1997.2732","volume":"77","author":"I Krasikov","year":"1997","unstructured":"Krasikov, I., Roditty, Y.: On a reconstruction problem for sequences. J. Comb. Theory Ser. A 77(2), 344\u2013348 (1997). \nhttps:\/\/doi.org\/10.1006\/jcta.1997.2732","journal-title":"J. Comb. Theory Ser. A"},{"key":"12_CR55","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707\u2013710 (1966)","journal-title":"Soviet Phys. Dokl."},{"issue":"1","key":"12_CR56","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/18.904499","volume":"47","author":"VI Levenshtein","year":"2001","unstructured":"Levenshtein, V.I.: Efficient reconstruction of sequences. IEEE Trans. Inf. Theory 47(1), 2\u201322 (2001). \nhttps:\/\/doi.org\/10.1109\/18.904499","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"12_CR57","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R Lowrance","year":"1975","unstructured":"Lowrance, R., Wagner, R.A.: An extension of the string-to-string correction problem. J. ACM 22(2), 177\u2013183 (1975). \nhttps:\/\/doi.org\/10.1145\/321879.321880","journal-title":"J. ACM"},{"issue":"3","key":"12_CR58","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0012-365X(91)90026-X","volume":"94","author":"B Manvel","year":"1991","unstructured":"Manvel, B., Meyerowitz, A., Schwenk, A.J., Smith, K., Stockmeyer, P.K.: Reconstruction of sequences. Discrete Math. 94(3), 209\u2013219 (1991). \nhttps:\/\/doi.org\/10.1016\/0012-365X(91)90026-X","journal-title":"Discrete Math."},{"key":"12_CR59","unstructured":"Marcovich, S., Yaakobi, E.: Reconstruction of strings from their substrings spectrum. CoRR abs\/1912.11108 (2019). \nhttp:\/\/arxiv.org\/abs\/1912.11108"},{"key":"12_CR60","doi-asserted-by":"publisher","unstructured":"Margaritis, D., Skiena, S.S.: Reconstructing strings from substrings in rounds. In: IEEE 36th Symposium on Foundations of Computer Science (FOCS), pp. 613\u2013620, October 1995. \nhttps:\/\/doi.org\/10.1109\/SFCS.1995.492591","DOI":"10.1109\/SFCS.1995.492591"},{"key":"12_CR61","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"issue":"18","key":"12_CR62","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1016\/j.ipl.2010.06.012","volume":"110","author":"TM Moosa","year":"2010","unstructured":"Moosa, T.M., Rahman, M.S.: Indexing permutations for binary strings. Inf. Process. Lett. 110(18), 795\u2013798 (2010). \nhttps:\/\/doi.org\/10.1016\/j.ipl.2010.06.012\n\n. \nhttp:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019010002012","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"12_CR63","doi-asserted-by":"publisher","first-page":"6273","DOI":"10.1109\/TIT.2013.2270273","volume":"59","author":"AS Motahari","year":"2013","unstructured":"Motahari, A.S., Bresler, G., Tse, D.N.C.: Information theory of DNA shotgun sequencing. IEEE Trans. Inf. Theory 59(10), 6273\u20136289 (2013). \nhttps:\/\/doi.org\/10.1109\/TIT.2013.2270273","journal-title":"IEEE Trans. Inf. Theory"},{"key":"12_CR64","doi-asserted-by":"publisher","unstructured":"Motahari, A.S., Ramchandran, K., Tse, D., Ma, N.: Optimal DNA shotgun sequencing: noisy reads are as good as noiseless reads. In: Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, 7\u201312 July 2013, pp. 1640\u20131644. IEEE (2013). \nhttps:\/\/doi.org\/10.1109\/ISIT.2013.6620505","DOI":"10.1109\/ISIT.2013.6620505"},{"issue":"14","key":"12_CR65","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1093\/bioinformatics\/btg268","volume":"19","author":"V Parisi","year":"2003","unstructured":"Parisi, V., Fonzo, V.D., Aluffi-Pentini, F.: STRING: finding tandem repeats in DNA sequences. Bioinformatics 19(14), 1733\u20131738 (2003)","journal-title":"Bioinformatics"},{"issue":"12","key":"12_CR66","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1093\/bioinformatics\/btq209","volume":"26","author":"M Pellegrini","year":"2010","unstructured":"Pellegrini, M., Renda, M.E., Vecchio, A.: TRStalker: an efficient heuristic for finding fuzzy tandem repeats. Bioinformatics [ISMB] 26(12), 358\u2013366 (2010)","journal-title":"Bioinformatics [ISMB]"},{"key":"12_CR67","doi-asserted-by":"publisher","unstructured":"Sala, F., Gabrys, R., Schoeny, C., Mazooji, K., Dolecek, L.: Exact sequence reconstruction for insertion-correcting codes. In: IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 10\u201315 July 2016, pp. 615\u2013619. IEEE (2016). \nhttps:\/\/doi.org\/10.1109\/ISIT.2016.7541372","DOI":"10.1109\/ISIT.2016.7541372"},{"issue":"1\u20133","key":"12_CR68","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0012-365X(96)00153-7","volume":"175","author":"AD Scott","year":"1997","unstructured":"Scott, A.D.: Reconstructing sequences. Discrete Math. 175(1\u20133), 231\u2013238 (1997). \nhttps:\/\/doi.org\/10.1016\/S0012-365X(96)00153-7","journal-title":"Discrete Math."},{"key":"12_CR69","doi-asserted-by":"publisher","unstructured":"Shomorony, I., Courtade, T.A., Tse, D.N.C.: Do read errors matter for genome assembly? In: IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, China, 14\u201319 June 2015, pp. 919\u2013923. IEEE (2015). \nhttps:\/\/doi.org\/10.1109\/ISIT.2015.7282589","DOI":"10.1109\/ISIT.2015.7282589"},{"key":"12_CR70","doi-asserted-by":"publisher","unstructured":"Shomorony, I., Kamath, G.M., Xia, F., Courtade, T.A., Tse, D.N.C.: Partial DNA assembly: a rate-distortion perspective. In: IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 10\u201315 July 2016, pp. 1799\u20131803. IEEE (2016). \nhttps:\/\/doi.org\/10.1109\/ISIT.2016.7541609","DOI":"10.1109\/ISIT.2016.7541609"},{"key":"12_CR71","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/3-540-07407-4_23","volume-title":"Automata Theory and Formal Languages","author":"I Simon","year":"1975","unstructured":"Simon, I.: Piecewise testable events. In: Brakhage, H. (ed.) GI-Fachtagung 1975. LNCS, vol. 33, pp. 214\u2013222. Springer, Heidelberg (1975). \nhttps:\/\/doi.org\/10.1007\/3-540-07407-4_23"},{"key":"12_CR72","doi-asserted-by":"publisher","unstructured":"Skiena, S., Smith, W.D., Lemke, P.: Reconstructing sets from interpoint distances (extended abstract). In: Seidel, R. (ed.) Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, CA, USA, 6\u20138 June 1990, pp. 332\u2013339. ACM (1990). \nhttps:\/\/doi.org\/10.1145\/98524.98598","DOI":"10.1145\/98524.98598"},{"issue":"2","key":"12_CR73","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1089\/cmb.1995.2.333","volume":"2","author":"S Skiena","year":"1995","unstructured":"Skiena, S., Sundaram, G.: Reconstructing strings from substrings. J. Comput. Biol. 2(2), 333\u2013353 (1995). \nhttps:\/\/doi.org\/10.1089\/cmb.1995.2.333","journal-title":"J. Comput. Biol."},{"key":"12_CR74","doi-asserted-by":"publisher","unstructured":"Sokol, D.: TRedD - a database for tandem repeats over the edit distance. Database J. Biol. Databases Curation 2010(baq003) (2010). \nhttps:\/\/doi.org\/10.1093\/database\/baq003","DOI":"10.1093\/database\/baq003"},{"issue":"1","key":"12_CR75","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1023\/A:1011359607594","volume":"14","author":"K Tan","year":"2001","unstructured":"Tan, K., Ooi, B.C., Yee, C.Y.: An evaluation of color-spatial retrieval techniques for large image databases. Multimed. Tools Appl. 14(1), 55\u201378 (2001). \nhttps:\/\/doi.org\/10.1023\/A:1011359607594","journal-title":"Multimed. Tools Appl."},{"issue":"4","key":"12_CR76","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G Tardos","year":"1989","unstructured":"Tardos, G.: Query complexity, or why is it difficult to separate $$NP^A\\cap coNP^A$$ from $$P^A$$ by random oracles $$A$$? Combinatorica 9(4), 385\u2013392 (1989). \nhttps:\/\/doi.org\/10.1007\/BF02125350","journal-title":"Combinatorica"},{"key":"12_CR77","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/11538462_38","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"D Tsur","year":"2005","unstructured":"Tsur, D.: Tight bounds for string reconstruction using substring queries. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX\/RANDOM -2005. LNCS, vol. 3624, pp. 448\u2013459. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11538462_38"},{"issue":"1","key":"12_CR78","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E Ukkonen","year":"1992","unstructured":"Ukkonen, E.: Approximate string matching with q-grams and maximal matches. Theor. Comput. Sci. 92(1), 191\u2013211 (1992). \nhttps:\/\/doi.org\/10.1016\/0304-3975(92)90143-4","journal-title":"Theor. Comput. Sci."},{"key":"12_CR79","unstructured":"Viswanathan, K., Swaminathan, R.: Improved string reconstruction over insertion-deletion channels. In: Teng, S. (ed.) Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, 20\u201322 January 2008, pp. 399\u2013408. SIAM (2008). \nhttp:\/\/dl.acm.org\/citation.cfm?id=1347082.1347126"},{"key":"12_CR80","doi-asserted-by":"publisher","unstructured":"Wagner, R.A.: On the complexity of the extended string-to-string correction problem. In: Rounds, W.C., Martin, N., Carlyle, J.W., Harrison, M.A. (eds.) Proceedings of the 7th Annual ACM Symposium on Theory of Computing, Albuquerque, New Mexico, USA, 5\u20137 May 1975, pp. 218\u2013223. ACM (1975). \nhttps:\/\/doi.org\/10.1145\/800116.803771","DOI":"10.1145\/800116.803771"},{"issue":"1","key":"12_CR81","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/2036264.2036276","volume":"3","author":"J Wang","year":"2011","unstructured":"Wang, J., Hua, X.: Interactive image search by color map. ACM Trans. Intell. Syst. Technol. 3(1), 12:1\u201312:23 (2011)","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"12_CR82","doi-asserted-by":"crossref","unstructured":"Wexler, Y., Yakhini, Z., Kashi, Y., Geiger, D.: Finding approximate tandem repeats in genomic sequences. In: RECOMB, pp. 223\u2013232 (2004)","DOI":"10.1145\/974614.974644"},{"key":"12_CR83","doi-asserted-by":"publisher","unstructured":"Yao, A.C.C.: Decision tree complexity and Betti numbers. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 615\u2013624. ACM, New York (1994). \nhttps:\/\/doi.org\/10.1145\/195058.195414","DOI":"10.1145\/195058.195414"},{"issue":"3","key":"12_CR84","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0041-5553(84)90069-7","volume":"24","author":"A Zenkin","year":"1984","unstructured":"Zenkin, A., Leont\u2019ev, V.K.: On a non-classical recognition problem. USSR Comput. Math. Math. Phys. 24(3), 189\u2013193 (1984)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"12_CR85","unstructured":"Zhou, W., Li, H., Tian, Q.: Recent advance in content-based image retrieval: a literature survey. CoRR abs\/1706.06064 (2017). \nhttp:\/\/arxiv.org\/abs\/1706.06064"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-59212-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:07:02Z","timestamp":1600250822000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-59212-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030592110","9783030592127"],"references-count":85,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-59212-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 September 2020","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":"Orlando, FL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.ucf.edu\/spire2020\/","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":"32","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":"17","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":"4","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":"4","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":"2","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)"}}]}}