The problem of string reconstruction based on its substrings spectrum has received significant attention recently due to its applicability to DNA data storage and sequencing. In contrast to previous works, we consider in this paper a setup of this problem where multiple strings are reconstructed together. Given a multiset $S$ of strings, all their substrings of some fixed length $\ell$, defined as the $\ell$-profile of $S$, are received and the goal is to reconstruct all strings in $S$. A multi-strand $\ell$-reconstruction code is a set of multisets such that every element $S$ can be reconstructed from its $\ell$-profile. Given the number of strings~$k$ and their length~$n$, we first find a lower bound on the value of $\ell$ necessary for existence of multi-strand $\ell$-reconstruction codes with non-vanishing asymptotic rate. We then present two constructions of such codes and show that their rates approach~$1$ for values of $\ell$ that asymptotically behave like the lower bound.


翻译:基于其子字符串频谱的字符串重建问题最近由于适用于DNA数据存储和排序而引起极大关注。与以前的工作不同,我们在本文件中认为这个问题的设置是多字符串一起重建的。考虑到多个字符串的多套元S$,所有其固定长度为$S$的子字符串都收到,目标是以美元重整所有字符串。多字符串和美元重建代码是一套多套套套件,每套元S$都可以从其$\ell$的特征中重建。考虑到字符串~k$及其长度~n美元,我们首先发现一个较低的约束值,即多字符串和美元重建代码存在所需的美元/ell$美元价值,其价值以美元计为美元。然后我们提出两种这种代码的构建,并表明其利率为$1美元/ell$的汇率,其表现方式类似低调。

0
下载
关闭预览

相关内容

在数学中,多重集是对集的概念的修改,与集不同,集对每个元素允许多个实例。 为每个元素提供的实例的正整数个数称为该元素在多重集中的多重性。 结果存在无限多个多重集,它们仅包含元素a和b,但因元素的多样性而变化:(1)集{a,b}仅包含元素a和b,当将{a,b}视为多集时,每个元素的多重性为1;(2)在多重集{a,a,b}中,元素a具有多重性2,而b具有多重性1;(3)在多集{a,a,a,b,b,b}中,a和b都具有多重性3。
专知会员服务
76+阅读 · 2021年3月16日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【最受欢迎的概率书】《概率论:理论与实例》,490页pdf
专知会员服务
162+阅读 · 2020年11月13日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
专知会员服务
82+阅读 · 2020年5月16日
计算机视觉最佳实践、代码示例和相关文档
专知会员服务
17+阅读 · 2019年10月9日
BERT源码分析PART I
AINLP
38+阅读 · 2019年7月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年10月20日
Arxiv
0+阅读 · 2021年10月19日
VIP会员
相关VIP内容
相关资讯
BERT源码分析PART I
AINLP
38+阅读 · 2019年7月12日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
机器学习线性代数速查
机器学习研究会
19+阅读 · 2018年2月25日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员