String reconstruction from substring compositions

Jayadev Acharya, Hirakendu Das, Olgica Milenkovic, Alon Orlitsky, Shengjun Pan

Research output: Contribution to journalArticlepeer-review


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 ≥ 4 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.

Original languageEnglish (US)
Pages (from-to)1340-1371
Number of pages32
JournalSIAM Journal on Discrete Mathematics
Issue number3
StatePublished - 2015


  • Backtracking algorithm
  • Mass spectrometry
  • Polynomial factorization
  • Protein sequencing
  • String reconstruction
  • Turnpike problem

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'String reconstruction from substring compositions'. Together they form a unique fingerprint.

Cite this