Reconstructing strings from random traces
Reconstructing strings from random traces
复制标题
从随机痕迹重建字符串
DOI：
10.1111/j.1467-9574.1980.tb00681.x
复制
发表时间：
2004
影响因子：
1.5
通讯作者：
A. Mcgregor
中科院分区：
文献类型：
--
作者：
Tugkan Batu;Sampath Kannan;S. Khanna;A. Mcgregor
我们获得了一个长度为n的字符串t的M序列（痕迹），其中通过使用概率q删除字符串中的每个痕迹是从这些观察到的轨迹中重建字符串t在这里启动一项对删除率的研究。多数比对重建了与原始字符串（W.H.P.）相同的Q = O（1/N1/2+ε）的字符串，在这种情况下，使用O（n log n）样本，我们使用O（1）。可以将原始字符串重建。在建立这些结果的过程中，我们表明，位多数对准具有有趣的自我校正属性，从而使痕迹中的局部扭曲不会在重建中产生错误，有时会得到纠正。
We are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly reconstruct the string t from these observed traces. We initiate here a study of deletion rates for which we can successfully reconstruct the original string using a small number of samples. We investigate a simple reconstruction algorithm called Bitwise Majority Alignment that uses majority voting (with suitable shifts) to determine each bit of the original string. We show that for random strings t, we can reconstruct the original string (w.h.p.) for q = O(1/ log n) using only O(log n) samples. For arbitrary strings t, we show that a simple modification of Bitwise Majority Alignment reconstructs a string that has identical structure to the original string (w.h.p.) for q = O(1/n1/2+ε) using O(1) samples. In this case, using O(n log n) samples, we can reconstruct the original string exactly. Our setting can be viewed as the study of an idealized biological evolutionary process where the only possible mutations are random deletions. Our goal is to understand at what mutation rates, a small number of observed samples can be correctly aligned to reconstruct the parent string.In the process of establishing these results, we show that Bitwise Majority Alignment has an interesting self-correcting property whereby local distortions in the traces do not generate errors in the reconstruction and eventually get corrected.