TY - GEN
T1 - On reconstructing a string from its substring compositions
AU - Acharya, Jayadev
AU - Das, Hirakendu
AU - Milenkovic, Olgica
AU - Orlitsky, Alon
AU - Pan, Shengjun
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2010
Y1 - 2010
N2 - Motivated by protein sequencing, we consider the problem of reconstructing a string from the compositions of its substrings. We provide several results, including the following. General classes of strings that cannot be distinguished from their substring compositions. An almost complete characterization of the lengths for which reconstruction is possible. Bounds on the number of strings with the same substring compositions in terms of the number of divisors of the string length plus one. A relation to the turnpike problem and a bivariate polynomial formulation of string reconstruction.
AB - Motivated by protein sequencing, we consider the problem of reconstructing a string from the compositions of its substrings. We provide several results, including the following. General classes of strings that cannot be distinguished from their substring compositions. An almost complete characterization of the lengths for which reconstruction is possible. Bounds on the number of strings with the same substring compositions in terms of the number of divisors of the string length plus one. A relation to the turnpike problem and a bivariate polynomial formulation of string reconstruction.
UR - https://www.scopus.com/pages/publications/77955679585
UR - https://www.scopus.com/pages/publications/77955679585#tab=citedBy
U2 - 10.1109/ISIT.2010.5513668
DO - 10.1109/ISIT.2010.5513668
M3 - Conference contribution
AN - SCOPUS:77955679585
SN - 9781424469604
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1238
EP - 1242
BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010
Y2 - 13 June 2010 through 18 June 2010
ER -