@inproceedings{7960e434141b4aefb608b7a2c2388bb9,
title = "Quadratic-backtracking algorithm for string reconstruction from substring compositions",
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.",
author = "Jayadev Acharya and Hirakendu Das and Olgica Milenkovic and Alon Orlitsky and Shengjun Pan",
year = "2014",
doi = "10.1109/ISIT.2014.6875042",
language = "English (US)",
isbn = "9781479951864",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1296--1300",
booktitle = "2014 IEEE International Symposium on Information Theory, ISIT 2014",
address = "United States",
note = "2014 IEEE International Symposium on Information Theory, ISIT 2014 ; Conference date: 29-06-2014 Through 04-07-2014",
}