Fundamental Limits of Multiple Sequence Reconstruction from Substrings
Fundamental Limits of Multiple Sequence Reconstruction from Substrings
复制标题
DOI：
10.1109/isit54713.2023.10206707
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Kelly Levick;Ilan Shomorony
中科院分区：
文献类型：
--
作者：
Kelly Levick;Ilan Shomorony
从长度为k的子串的集合重构序列的问题由于其在基因组学中的各种应用而受到相当大的关注。我们研究了这个问题的未编码版本，其中多个随机源是同时从他们的k-mer集的工会重建。我们考虑一个渐近区域，其中m = nα i.i.d.长度为n的源序列将从它们的长度为k = β logn的子串的集合中重构，并且试图表征重构在信息理论上可行的（α，β）对。我们证明了当n →∞α + 1时，如果β > max（2α + 1，α + 2），则源序列可以重建;如果$\beta < \max \left（{2\alpha +1，\alpha + \frac{3}{2}} \right）$，则源序列不能重建，从而几乎完全刻画了可行域。有趣的是，我们的结果表明，存在可行的（α，β）对，其中源串中的重复比比皆是，并且需要非平凡的重建算法来实现基本限制。
The problem of reconstructing a sequence from the set of its length-k substrings has received considerable attention due to its various applications in genomics. We study an uncoded version of this problem where multiple random sources are to be simultaneously reconstructed from the union of their k-mer sets. We consider an asymptotic regime where m = nα i.i.d. source sequences of length n are to be reconstructed from the set of their substrings of length k = β logn, and seek to characterize the (α,β) pairs for which reconstruction is information-theoretically feasible. We show that, as n →∞α + 1, the source sequences can be reconstructed if β > max(2α + 1, α + 2) and cannot be reconstructed if $\beta < \max \left( {2\alpha + 1,\alpha + \frac{3}{2}} \right)$, characterizing the feasibility region almost completely. Interestingly, our result shows that there are feasible (α,β) pairs where repeats across the source strings abound, and non-trivial reconstruction algorithms are needed to achieve the fundamental limit.