The problem of reconstructing strings from substring information has found many applications due to its importance in genomic data sequencing and DNA- and polymer-based data storage. One practically important and challenging paradigm requires reconstructing mixtures of strings based on the union of compositions of their prefixes and suffixes, generated by mass spectrometry devices. We describe new coding methods that allow for unique joint reconstruction of subsets of strings selected from a code and provide upper and lower bounds on the asymptotic rate of the underlying codebooks. Our code constructions combine properties of binary Bh and Dyck strings and that can be extended to accommodate missing substrings in the pool. As auxiliary results, we obtain the first known bounds on binary Bh sequences for arbitrary even parameters h, and also describe various error models inherent to mass spectrometry analysis. This paper contains a correction of the prior work by the authors, published in [24]. In particular, the bounds on the prefix codes are now corrected.


翻译:从子字符串信息中重建字符串的问题由于在基因组数据测序以及DNA和聚合物数据存储中的重要性而发现许多应用问题。一个实际重要和具有挑战性的范例是,需要根据质量光谱仪设备产生的前缀和后缀的组合组合来重建字符串的混合物。我们描述了新的编码方法,这些方法使得从一个代码中选择的字符串子集能够进行独特的联合重建,并为基础代码簿的无药率提供上下限。我们的代码构造结合了二进制 Bh 和 Dyck 字符串的特性,这些特性可以扩展以适应池中缺失的子字符串。作为辅助结果,我们获得了关于任意甚至参数h的二进制 Bh 序列的第一个已知界限,还描述了质量光谱分析所固有的各种错误模型。本文载有作者先前工作(在[24] 中发表) 的更正。特别是前缀代码的界限现在得到了更正。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
ExBert — 可视化分析Transformer学到的表示
专知会员服务
31+阅读 · 2019年10月16日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】全卷积语义分割综述
机器学习研究会
19+阅读 · 2017年8月31日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月29日
Arxiv
0+阅读 · 2021年11月28日
VIP会员
相关VIP内容
相关资讯
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【推荐】全卷积语义分割综述
机器学习研究会
19+阅读 · 2017年8月31日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员