TU1.R6.4

Reconstruction of multiple strings of constant weight from prefix-suffix compositions

Yaoyu Yang, Zitan Chen, The Chinese University of Hong Kong, Shenzhen, China
Session:
Biology: sequence reconstruction
Track:
17: Information and Coding in Biology
Location:
Sigma/Delta
Presentation Time:
Tue, 9 Jul, 10:45 - 11:05
Session Chair:
Netanel Raviv, Washington University in St. Louis
Abstract
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 weight from the compositions of their prefixes and suffixes of every possible length. We provide necessary and sufficient conditions for the multiset of strings so that unique reconstruction up to reversal is possible.
Session TU1.R6
TU1.R6.1: On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction
Kuan Cheng, Peking University, China; Elena Grigorescu, Purdue University, United States; Xin Li, Johns Hopkins University, United States; Madhu Sudan, Harvard University, United States; Minshen Zhu, N/A, China
TU1.R6.2: Tree Trace Reconstruction - Reductions to String Trace Reconstruction
Thomas Maranzatto, University of Illinois Chicago, United States
TU1.R6.3: Sequence Reconstruction over 3-Deletion Channels
Di Zhang, Shandong University, China; Gennian Ge, Capital Normal University, China; Yiwei Zhang, Shandong University, China
TU1.R6.4: Reconstruction of multiple strings of constant weight from prefix-suffix compositions
Yaoyu Yang, Zitan Chen, The Chinese University of Hong Kong, Shenzhen, China
Resources
View Manuscript