{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T01:14:31Z","timestamp":1777511671410,"version":"3.51.4"},"reference-count":19,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T00:00:00Z","timestamp":1736121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Basic Research Project of Hetao Shenzhen-Hong Kong Science and Technology Cooperation Zone","award":["HZQB-KCZYZ-2021067"],"award-info":[{"award-number":["HZQB-KCZYZ-2021067"]}]},{"name":"Basic Research Project of Hetao Shenzhen-Hong Kong Science and Technology Cooperation Zone","award":["2022B1212010001"],"award-info":[{"award-number":["2022B1212010001"]}]},{"name":"Basic Research Project of Hetao Shenzhen-Hong Kong Science and Technology Cooperation Zone","award":["62201487"],"award-info":[{"award-number":["62201487"]}]},{"name":"Guangdong Provincial Key Laboratory of Future Network of Intelligence","award":["HZQB-KCZYZ-2021067"],"award-info":[{"award-number":["HZQB-KCZYZ-2021067"]}]},{"name":"Guangdong Provincial Key Laboratory of Future Network of Intelligence","award":["2022B1212010001"],"award-info":[{"award-number":["2022B1212010001"]}]},{"name":"Guangdong Provincial Key Laboratory of Future Network of Intelligence","award":["62201487"],"award-info":[{"award-number":["62201487"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["HZQB-KCZYZ-2021067"],"award-info":[{"award-number":["HZQB-KCZYZ-2021067"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["2022B1212010001"],"award-info":[{"award-number":["2022B1212010001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62201487"],"award-info":[{"award-number":["62201487"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen Science and Technology Stable","award":["HZQB-KCZYZ-2021067"],"award-info":[{"award-number":["HZQB-KCZYZ-2021067"]}]},{"name":"Shenzhen Science and Technology Stable","award":["2022B1212010001"],"award-info":[{"award-number":["2022B1212010001"]}]},{"name":"Shenzhen Science and Technology Stable","award":["62201487"],"award-info":[{"award-number":["62201487"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Motivated by studies of data retrieval in polymer-based storage systems, we consider the problem of reconstructing a multiset of binary strings that have the same length and the same weight from the compositions of their prefixes and suffixes of every possible length. We provide necessary and sufficient conditions for which unique reconstruction up to the reversal of the strings is possible. Additionally, we present two algorithms for reconstructing strings from the compositions of prefixes and suffixes of constant-length constant-weight strings.<\/jats:p>","DOI":"10.3390\/e27010039","type":"journal-article","created":{"date-parts":[[2025,1,6]],"date-time":"2025-01-06T10:40:52Z","timestamp":1736160052000},"page":"39","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Reconstruction of Multiple Strings of Constant Weight from Prefix\u2013Suffix Compositions"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-8771-4965","authenticated-orcid":false,"given":"Yaoyu","family":"Yang","sequence":"first","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen 518172, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0570-0770","authenticated-orcid":false,"given":"Zitan","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Science and Engineering, Future Networks of Intelligence Institute, The Chinese University of Hong Kong, Shenzhen 518172, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,1,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1038\/s41467-017-01104-3","article-title":"Mass spectrometry sequencing of long digital polymers facilitated by programmed inter-byte fragmentation","volume":"8","author":"Ouahabi","year":"2017","journal-title":"Nat. Commun."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1002\/ange.202010171","article-title":"Precise alkoxyamine design to enable automated tandem mass spectrometry sequencing of digital poly(phosphodiester)s","volume":"133","author":"Launay","year":"2021","journal-title":"Angew. Chem."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1340","DOI":"10.1137\/140962486","article-title":"String reconstruction from substring compositions","volume":"29","author":"Acharya","year":"2015","journal-title":"SIAM J. Discret. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"4812","DOI":"10.1109\/TIT.2023.3267620","article-title":"Coding for polymer-based data storage","volume":"69","author":"Pattabiraman","year":"2023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"4384","DOI":"10.1109\/TIT.2023.3252045","article-title":"Insertion and deletion correction in polymer-based data storage","volume":"69","author":"Banerjee","year":"2023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TCOMM.2022.3222341","article-title":"Reconstruction of sets of strings from prefix\/suffix compositions","volume":"71","author":"Gabrys","year":"2023","journal-title":"IEEE Trans. Commun."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3922","DOI":"10.1109\/TIT.2023.3315784","article-title":"Reconstruction of a single string from a part of its composition multiset","volume":"70","author":"Ye","year":"2023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gupta, U., and Mahdavifar, H. (July, January 26). A new algebraic approach for string reconstruction from substring compositions. Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT), Espoo, Finland.","DOI":"10.1109\/ISIT50566.2022.9834531"},{"key":"ref_9","unstructured":"Margaritis, D., and Skiena, S.S. (1995, January 23\u201325). Reconstructing strings from substrings in rounds. Proceedings of the IEEE 36th Annual Foundations of Computer Science, Milwaukee, WI, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1006\/jcta.2000.3081","article-title":"Efficient reconstruction of sequences from their subsequences or supersequences","volume":"93","author":"Levenshtein","year":"2001","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_11","unstructured":"Batu, T., Kannan, S., Khanna, S., and McGregor, A. (2004, January 11\u201314). Reconstructing strings from random traces. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA\u201904, New Orleans, LA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"4369","DOI":"10.1109\/TIT.2021.3084864","article-title":"Reconstruction of strings from their substrings spectrum","volume":"67","author":"Marcovich","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"5648","DOI":"10.1109\/TIT.2023.3269124","article-title":"Generalized unique reconstruction from substrings","volume":"69","author":"Yehezkeally","year":"2023","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"6084","DOI":"10.1109\/TIT.2020.2996377","article-title":"Coded trace reconstruction","volume":"66","author":"Cheraghchi","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3233","DOI":"10.1109\/TIT.2021.3066010","article-title":"Trace reconstruction: Generalized and parameterized","volume":"67","author":"Krishnamurthy","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/JSAIT.2022.3151737","article-title":"Coded shotgun sequencing","volume":"3","author":"Ravi","year":"2022","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Levick, K., and Shomorony, I. (2023, January 25\u201330). Fundamental limits of multiple sequence reconstruction from substrings. Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan.","DOI":"10.1109\/ISIT54713.2023.10206707"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sima, J., Li, Y., Shomorony, I., and Milenkovic, O. (2023, January 25\u201330). On constant-weight binary B2-sequences. Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan.","DOI":"10.1109\/ISIT54713.2023.10206632"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Yang, Y., and Chen, Z. (2024, January 7\u201312). Reconstruction of multiple strings of constant weight from prefix-suffix compositions. Proceedings of the 2024 IEEE International Symposium on Information Theory (ISIT), Athens, Greece.","DOI":"10.1109\/ISIT57864.2024.10619697"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/39\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:23:51Z","timestamp":1759919031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/1\/39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,6]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["e27010039"],"URL":"https:\/\/doi.org\/10.3390\/e27010039","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,6]]}}}