Quadratic-backtracking algorithm for string reconstruction from substring compositions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motivated by the problem of deducing the structure of proteins using mass-spectrometry, we study the reconstruction of a string from the multiset of its substring compositions. We specialize the backtracking algorithm used for the more general turnpike problem for string reconstruction. Employing well known results about transience of random walks in ≥ 3 dimensions, we show that the algorithm reconstructs random strings over alphabet size ≥ 4 with high probability in near-optimal quadratic time.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1296-1300
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
CountryUnited States
CityHonolulu, HI
Period6/29/147/4/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Quadratic-backtracking algorithm for string reconstruction from substring compositions'. Together they form a unique fingerprint.

  • Cite this

    Acharya, J., Das, H., Milenkovic, O., Orlitsky, A., & Pan, S. (2014). Quadratic-backtracking algorithm for string reconstruction from substring compositions. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 1296-1300). [6875042] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875042