String Reconstruction from Substring Compositions
String Reconstruction from Substring Compositions
复制标题
从子字符串组合重建字符串
DOI：
10.1137/140962486
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Shengjun Pan
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;Hirakendu Das;O. Milenkovic;A. Orlitsky;Shengjun Pan
受质谱蛋白测序的启发，我们考虑了从其子串组成的多集重建字符串的问题。我们证明了所有长度为7的字符串，一个小于一个素数，一个小于两个素数，可以唯一地重构到反转。对于所有其他长度，我们证明了惟一重构并不总是可能的，并提供了具有给定子字符串组成的最大字符串数的有时很紧的界限。下界是由组合参数推导出来的，而上界是由代数方法推导出来的，根据二元多项式的因式分解性质，可以精确地描述具有相同子串组成的字符串集合。利用多维随机漫步的瞬态结果，我们还提供了一种重建算法，该算法可以在最优的近二次时间内从其子串组成中恢复大小≥4的字母表上的随机字符串。所考虑的问题与众所周知的收费公路问题有关，因此它的解决方案也可能有助于解决这个长期存在的开放性问题。
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.