{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:10Z","timestamp":1787322070702,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Motivated by mass-spectrometry protein sequencing, we consider the problem of reconstructing a string from the multisets of its substring composition. We show that all strings of length 7, one less than a prime and one less than twice a prime, can be reconstructed uniquely up to reversal. For all other lengths, we show that unique reconstruction is not always possible and provide sometimes-tight bounds on the largest number of strings with given substring compositions. The lower bounds are derived by combinatorial arguments, while the upper bounds follow from algebraic approaches that lead to precise characterizations of the sets of strings with the same substring compositions in terms of the factorization properties of bivariate polynomials. Using results on the transience of multidimensional random walks, we also provide a reconstruction algorithm that recovers random strings over alphabets of size $\\ge4$ from their substring compositions in optimal near-quadratic time. The problem considered is related to the well-known turnpike problem, and its solution may hence shed light on this longstanding open problem as well.<\/jats:p>","DOI":"10.1137\/140962486","type":"journal-article","created":{"date-parts":[[2015,8,4]],"date-time":"2015-08-04T13:03:40Z","timestamp":1438693420000},"page":"1340-1371","source":"Crossref","is-referenced-by-count":47,"title":["String Reconstruction from Substring Compositions"],"prefix":"10.1137","volume":"29","author":[{"given":"Jayadev","family":"Acharya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hirakendu","family":"Das","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olgica","family":"Milenkovic","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Orlitsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shengjun","family":"Pan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,8,4]]},"reference":[{"key":"atypb1","first-page":"1238","author":"Acharya J.","year":"2010","journal-title":"Proceedings of the IEEE Symposium on Information Theory"},{"key":"atypb2","first-page":"1296","author":"Acharya J.","year":"2014","journal-title":"IEEE"},{"key":"atypb3","unstructured":"T. Batu, S. Kannan, S. Khanna, and A. McGregor,\n                      Reconstructing strings from random traces\n                      , in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004, pp. 910-918."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2005.05.014"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_16"},{"key":"atypb6","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , 2nd ed., MIT Press, Cambridge, MA, 2001."},{"key":"atypb7","unstructured":"T. E. Creighton,\n                      Proteins: Structures and Molecular Properties\n                      , 2nd ed., W. H. Freeman, San Francisco, 1992."},{"key":"atypb8","unstructured":"T. Dakic,\n                      On the Turnpike Problem\n                      , Ph.D. thesis, Simon Fraser University, Burnaby, Canada, 2000."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.021"},{"key":"atypb10","first-page":"117","volume":"4","author":"Dix T. I.","year":"1988","journal-title":"Comput. Appl. Biosci."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00103-1"},{"key":"atypb12","first-page":"228","author":"Fici G.","year":"2011","journal-title":"New York"},{"key":"atypb13","unstructured":"D. J. H. Garling,\n                      A Course in Galois Theory\n                      , Cambridge University Press, Cambridge, 1986."},{"key":"atypb14","unstructured":"S. Kannan,\n                      Private communication\n                      , 2009."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Lang,\n                      Algebra\n                      , 3rd ed., Grad. Texts in Math., Springer, New York, 2002.","DOI":"10.1007\/978-1-4613-0041-0_1"},{"key":"atypb16","unstructured":"P. Lemke and M. Werman,\n                      Inverting the Autocorrelation and the Problem of Locating Points on a Line, Given Unlabelled Distances Between Them\n                      , Technical report 453, IMA preprint, Institute for Mathematics and Its Applications, Minneapolis, MN, 1988."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3081"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"D. Margaritis and S. S. Skiena,\n                      Reconstructing strings from substrings in rounds\n                      , in Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995, pp. 613-620.","DOI":"10.1109\/SFCS.1995.492591"},{"key":"atypb20","unstructured":"D. W. Mount,\n                      Bioinformatics: Sequence and Genome Analysis\n                      , 2nd ed., Cold Spring Harbor Laboratory Press, Cold Spring Harbor, NY, 2001."},{"key":"atypb21","unstructured":"I. Niven, H. S. Zuckerman, and H. L. Montgomery,\n                      An Introduction to the Theory of Numbers\n                      , 5th ed., Wiley Interscience, New York, 1991."},{"key":"atypb22","first-page":"317","volume":"39","author":"Odlyzko A. M.","year":"1993","journal-title":"Enseign. Math."},{"key":"atypb23","first-page":"517","volume":"90","author":"Patterson A. L.","year":"1935","journal-title":"Zeitsehr. Krist."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.65.195"},{"key":"atypb25","doi-asserted-by":"crossref","first-page":"317","DOI":"10.37236\/161","volume":"16","author":"Richmond L. B.","year":"2009","journal-title":"Electron. J. Combin."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/0603035"},{"key":"atypb27","first-page":"332","author":"Skiena S. S.","year":"1990","journal-title":"ACM"},{"key":"atypb28","unstructured":"F. Spitzer,\n                      Principles of Random Walk\n                      , Grad. Texts in Math. 34, Springer, New York, 2001."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90143-4"},{"key":"atypb30","first-page":"399","author":"Viswanathan K.","year":"2008","journal-title":"Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140962486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:49Z","timestamp":1787318269000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140962486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140962486"],"URL":"https:\/\/doi.org\/10.1137\/140962486","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}