{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:13:02Z","timestamp":1760238782371,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,6]],"date-time":"2020-09-06T00:00:00Z","timestamp":1599350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The shortest unique substring (SUS) problem is an active line of research in the field of string algorithms and has several applications in bioinformatics and information retrieval. The initial version of the problem was proposed by Pei et al. [ICDE\u201913]. Over the years, many variants and extensions have been pursued, which include positional-SUS, interval-SUS, approximate-SUS, palindromic-SUS, range-SUS, etc. In this article, we highlight some of the key results and summarize the recent developments in this area.<\/jats:p>","DOI":"10.3390\/a13090224","type":"journal-article","created":{"date-parts":[[2020,9,6]],"date-time":"2020-09-06T23:12:49Z","timestamp":1599433969000},"page":"224","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Survey on Shortest Unique Substring Queries"],"prefix":"10.3390","volume":"13","author":[{"given":"Paniz","family":"Abedin","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4583-6261","authenticated-orcid":false,"given":"M.","family":"K\u00fclekci","sequence":"additional","affiliation":[{"name":"Informatics Institute, Istanbul Technical University, Istanbul 34469, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shama","family":"Thankachan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,6]]},"reference":[{"key":"ref_1","unstructured":"Pei, J., Wu, W.C.H., and Yeh, M.Y. (2013, January 8\u201311). On Shortest Unique Substring Queries. Proceedings of the 2013 IEEE 29th International Conference on Data Engineering (ICDE), Brisbane, Australia."},{"key":"ref_2","first-page":"161","article-title":"Shortest Unique Queries on Strings","volume":"Volume 8799","author":"Crochemore","year":"2014","journal-title":"Proceedings of the String Processing and Information Retrieval-21st International Symposium\u2014SPIRE 2014"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2017.05.032","article-title":"In-place algorithms for exact and approximate shortest unique substring problems","volume":"690","author":"Hon","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jda.2018.11.009","article-title":"Algorithms and combinatorial properties on shortest unique palindromic substrings","volume":"52","author":"Inoue","year":"2018","journal-title":"J. Discrete Algorithms"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Abedin, P., Ganguly, A., Pissis, S.P., and Thankachan, S.V. (2019, January 7\u20139). Range Shortest Unique Substring Queries. Proceedings of the International Symposium on String Processing and Information Retrieval, Segovia, Spain.","DOI":"10.1007\/978-3-030-32686-9_18"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ileri, A.M., K\u00fclekci, M.O., and Xu, B. (2014). Shortest unique substring query revisited. Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-319-07566-2_18"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.tcs.2014.11.004","article-title":"A simple yet time-optimal and linear-space algorithm for shortest unique substring queries","volume":"562","author":"Ileri","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","unstructured":"LIPIcs, Faliszewski, P., Muscholl, A., and Niedermeier, R. (2016, January 22\u201326). Shortest Unique Substring Queries on Run-Length Encoded Strings. Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Krak\u00f3w, Poland."},{"key":"ref_9","unstructured":"Shehu, A., Wu, C.H., Boucher, C., Li, J., Liu, H., and Pop, M. (September, January 29). A Practical and Efficient Algorithm for the k-mismatch Shortest Unique Substring Finding Problem. Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics\u2014BCB 2018, Washington, DC, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Allen, D.R., Thankachan, S.V., and Xu, B. (2020). An Ultra-Fast and Parallelizable Algorithm for Finding k-Mismatch Shortest Unique Substrings. IEEE\/ACM Trans. Comput. Biol. Bioinform.","DOI":"10.1109\/TCBB.2020.2968531"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Watanabe, K., Nakashima, Y., Inenaga, S., Bannai, H., and Takeda, M. (2019, January 23\u201325). Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings. Proceedings of the Combinatorial Algorithms-30th International Workshop, IWOCA 2019, Pisa, Italy.","DOI":"10.1007\/978-3-030-25005-8_35"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Watanabe, K., Nakashima, Y., Inenaga, S., Bannai, H., and Takeda, M. (2020). Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings. Theory Comput. Syst.","DOI":"10.1007\/978-3-030-25005-8_35"},{"key":"ref_13","first-page":"503","article-title":"Shortest Unique Substrings Queries in Optimal Time","volume":"Volume 8327","author":"Geffert","year":"2014","journal-title":"Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science-40th International Conference on Current Trends in Theory and Practice of Computer Science"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Mieno, T., K\u00f6ppl, D., Nakashima, Y., Inenaga, S., Bannai, H., and Takeda, M. (2019, January 7\u20139). Compact Data Structures for Shortest Unique Substring Queries. Proceedings of the International Symposium on String Processing and Information Retrieval, Segovia, Spain.","DOI":"10.1007\/978-3-030-32686-9_8"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Schultz, D.W., and Xu, B. (2018, January 8\u201311). On k-Mismatch Shortest Unique Substring Queries Using GPU. Proceedings of the Bioinformatics Research and Applications-14th International Symposium\u2014ISBRA 2018, Beijing, China.","DOI":"10.1007\/978-3-319-94968-0_18"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Schultz, D.W., and Xu, B. (2019). Parallel Methods for Finding k-Mismatch Shortest Unique Substrings Using GPU. IEEE\/ACM Trans. Comput. Biol. Bioinform.","DOI":"10.1109\/TCBB.2019.2935061"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Hon, W., Thankachan, S.V., and Xu, B. (2015, January 9\u201311). An In-place Framework for Exact and Approximate Shortest Unique Substring Queries. Proceedings of the Algorithms and Computation-26th International Symposium\u2014ISAAC 2015, Nagoya, Japan.","DOI":"10.1007\/978-3-662-48971-0_63"},{"key":"ref_18","unstructured":"Ganguly, A., Hon, W.K., Shah, R., and Thankachan, S.V. (2016, January 12\u201314). Space-time trade-offs for the shortest unique substring problem. Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Sydney, Australia."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Haubold, B., Pierstorff, N., M\u00f6ller, F., and Wiehe, T. (2005). Genome comparison without alignment using shortest unique substrings. Bmc Bioinform., 6.","DOI":"10.1186\/1471-2105-6-123"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1002\/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.0.CO;2-D","article-title":"String matching in the DNA alphabet","volume":"27","author":"Tarhio","year":"1997","journal-title":"Software Pract. Exp."},{"key":"ref_21","first-page":"363","article-title":"Nucleotide Sequence Alignment and Compression via Shortest Unique Substring","volume":"Volume 9044","author":"Guzman","year":"2015","journal-title":"Proceedings of the Bioinformatics and Biomedical Engineering-Third International Conference\u2014IWBBIO 2015"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.1093\/bioinformatics\/btv738","article-title":"OMPPM: Online multiple palindrome pattern matching","volume":"32","author":"Kim","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","article-title":"Searching for gapped palindromes","volume":"410","author":"Kolpakov","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1016\/j.jcss.2014.02.010","article-title":"Range LCP","volume":"80","author":"Amir","year":"2014","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_25","first-page":"245","article-title":"A linear-space data structure for range-LCP queries in poly-logarithmic time","volume":"163","author":"Abedin","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., and Wale\u0144, T. (2014, January 5\u20137). Internal pattern matching queries in a text and applications. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, Portland, OR, USA.","DOI":"10.1137\/1.9781611973730.36"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Weiner, P. (1973, January 15\u201317). Linear Pattern Matching Algorithms. Proceedings of the 14th Annual Symposium on Switching and Automata Theory (Swat 1973), Iowa City, IA, USA.","DOI":"10.1109\/SWAT.1973.13"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: A new method for online string searches","volume":"22","author":"Manber","year":"1993","journal-title":"Siam J. Comput."},{"key":"ref_29","unstructured":"K\u00e4rkk\u00e4inen, J., and Sanders, P. (July, January 30). Simple linear work suffix array construction. Proceedings of the International Colloquium on Automata, Languages, and Programming, Eindhoven, The Netherlands."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","article-title":"Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays","volume":"40","author":"Fischer","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","article-title":"Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N)","volume":"17","author":"Willard","year":"1983","journal-title":"Inf. Process. Lett."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Rubinchik, M., and Shur, A.M. (2015). EERTREE: An efficient data structure for processing palindromes in strings. International Workshop on Combinatorial Algorithms, Springer.","DOI":"10.1007\/978-3-319-29516-9_27"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","article-title":"On-line construction of suffix trees","volume":"14","author":"Ukkonen","year":"1995","journal-title":"Algorithmica"},{"key":"ref_34","unstructured":"Jensen, C.S., Jermaine, C.M., and Zhou, X. (2013, January 8\u201312). On shortest unique substring queries. Proceedings of the 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","article-title":"The input\/output complexity of sorting and related problems","volume":"31","author":"Aggarwal","year":"1988","journal-title":"Commun. ACM"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Tamakoshi, Y., Goto, K., Inenaga, S., Bannai, H., and Takeda, M. (2015, January 20\u201322). An opportunistic text indexing structure based on run length encoding. Proceedings of the International Conference on Algorithms and Complexity, Paris, France, Germany.","DOI":"10.1007\/978-3-319-18173-8_29"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2006.13.336","article-title":"The average common substring approach to phylogenomic reconstruction","volume":"13","author":"Ulitsky","year":"2006","journal-title":"J. Comput. Biol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"267","DOI":"10.3233\/FI-2018-1743","article-title":"On computing average common substring over run length encoded sequences","volume":"163","author":"Hooshmand","year":"2018","journal-title":"Fundam. Informaticae"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1089\/cmb.2015.0217","article-title":"ALFRED: A practical method for alignment-free distance computation","volume":"23","author":"Thankachan","year":"2016","journal-title":"J. Comput. Biol."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Bannai, H., Gagie, T., Inenaga, S., K\u00e4rkk\u00e4inen, J., Kempa, D., Pi\u0105tkowski, M., Puglisi, S.J., and Sugimoto, S. (2015, January 27\u201330). Diverse palindromic factorization is NP-complete. Proceedings of the International Conference on Developments in Language Theory, Liverpool, UK.","DOI":"10.1007\/978-3-319-21500-6_6"},{"key":"ref_41","unstructured":"Borozdin, K., Kosolobov, D., Rubinchik, M., and Shur, A.M. (2017, January 4\u20136). Palindromic length in linear time. Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Warsaw, Poland."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"957","DOI":"10.1038\/nmeth.2649","article-title":"Cas9 as a versatile tool for engineering biology","volume":"10","author":"Mali","year":"2013","journal-title":"Nat. Methods"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1145\/321892.321896","article-title":"A New Linear-Time\u201cOn-Line\u201dAlgorithm for Finding the Smallest Initial Palindrome of a String","volume":"22","author":"Manacher","year":"1975","journal-title":"J. ACM (JACM)"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., and Patrascu, M. (2011, January 13\u201315). Orthogonal Range Searching on the RAM, Revisited. Proceedings of the 27th Annual Symposium on Computational Geometry 2011, Paris, France.","DOI":"10.1145\/1998196.1998198"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., and Puglisi, S.J. (2015). Parallel external memory suffix sorting. Annual Symposium on Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-319-19929-0_28"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J., and Zhukova, B. Engineering external memory induced suffix sorting. Proceedings of the 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Barcelona, Spain, 17\u201318 January 2017.","DOI":"10.1137\/1.9781611974768.8"},{"key":"ref_47","unstructured":"K\u00e4rkk\u00e4inen, J., and Kempa, D. (2016, January 22\u201324). Faster external memory LCP array construction. Proceedings of the 24th Annual European Symposium on Algorithms (ESA 2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Aarhus, Denmark."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., and Kempa, D. (2016, January 18\u201320). LCP array construction using O (sort (n))(or less) I\/Os. Proceedings of the International Symposium on String Processing and Information Retrieval, Beppu, Japan.","DOI":"10.1007\/978-3-319-46049-9_20"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"255","DOI":"10.6026\/97320630009255","article-title":"A method to find palindromes in nucleic acid sequences","volume":"9","author":"Anjana","year":"2013","journal-title":"Bioinformation"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Thankachan, S.V., Aluru, C., Chockalingam, S.P., and Aluru, S. (2018, January 21\u201324). Algorithmic framework for approximate matching under bounded edits with applications to sequence analysis. Proceedings of the International Conference on Research in Computational Molecular Biology, Paris, France.","DOI":"10.1007\/978-3-319-89929-9_14"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"2369","DOI":"10.1093\/nar\/27.11.2369","article-title":"Alignment of whole genomes","volume":"27","author":"Delcher","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"2633","DOI":"10.1007\/s00453-019-00548-x","article-title":"Longest common substring with approximately k mismatches","volume":"81","author":"Kociumaka","year":"2019","journal-title":"Algorithmica"},{"key":"ref_53","unstructured":"Abedin, P., Hooshmand, S., Ganguly, A., and Thankachan, S.V. (2018, January 2\u20134). The heaviest induced ancestors problem revisited. Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Qingdao, China."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1016\/j.ipl.2015.03.006","article-title":"Longest common substrings with k mismatches","volume":"115","author":"Flouri","year":"2015","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/224\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:07:23Z","timestamp":1760177243000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,6]]},"references-count":54,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090224"],"URL":"https:\/\/doi.org\/10.3390\/a13090224","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,9,6]]}}}