String Reconstruction from Substring Compositions

Jayadev Acharya, Hirakendu Das, Olgica Milenkovic +2

Motivated by mass-spectrometry protein sequencing, we consider a simply-stated problem of reconstructing a string from the multiset of its substring compositions. We show that all…