Correcting a Single Indel/Edit for DNA-Based Data Storage: Linear-Time Encoders and Order-Optimality

索引 编码器 计算机科学 冗余(工程) 算法 代码字 二进制数 数学 解码方法 算术 遗传学 生物 操作系统 单核苷酸多态性 基因 基因型
作者
Kui Cai,Yeow Meng Chee,Ryan Gabrys,Han Mao Kiah,Tuan Thanh Nguyen
出处
期刊:IEEE Transactions on Information Theory [Institute of Electrical and Electronics Engineers]
卷期号:67 (6): 3438-3451 被引量:63
标识
DOI:10.1109/tit.2021.3049627
摘要

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刚刚
xixi完成签到,获得积分20
刚刚
领导范儿的应助被勤奋梨愁采纳,获得10
2秒前
sls完成签到,获得积分10
2秒前
yh完成签到,获得积分10
4秒前
万能图书馆的应助被Jason采纳,获得30
5秒前
陆豪杰完成签到,获得积分10
6秒前
充电宝的应助被星辰采纳,获得20
6秒前
7秒前
8秒前
8秒前
勤奋梨愁完成签到,获得积分10
8秒前
xixi关注了科研通微信公众号
9秒前
无花果的应助被guoguozhijia158采纳,获得10
9秒前
10秒前
863发布了新的文献求助10
10秒前
slsdianzi完成签到,获得积分10
11秒前
脱羰甲酸发布了新的文献求助10
12秒前
12秒前
12秒前
852的应助被小冰块采纳,获得10
12秒前
zhaoliancheng完成签到,获得积分20
15秒前
大模型的应助被执着的钢笔采纳,获得10
15秒前
Z_xy完成签到,获得积分10
15秒前
16秒前
细心鲂发布了新的文献求助10
17秒前
zhaoliancheng发布了新的文献求助10
17秒前
霞霞子完成签到 ,获得积分10
18秒前
19秒前
万能图书馆的应助被久怨采纳,获得10
20秒前
SONG完成签到,获得积分10
21秒前
Yy完成签到 ,获得积分10
22秒前
博士完成签到 ,获得积分10
23秒前
23秒前
Ava的应助被863采纳,获得10
24秒前
斯文败类的应助被百川采纳,获得10
24秒前
24秒前
24秒前
25秒前
wwqc完成签到,获得积分0
27秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
Sex, Aging, and Death in a Medieval Medical Compendium: Trinity College Cambridge MS R.14.52, Its Texts, Language, and Scribe 500
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8188353
求助须知:如何正确求助?哪些是违规求助? 9576169
关于积分的说明 21845860
捐赠科研通 7786410
什么是DOI,文献DOI怎么找? 3435292
关于科研通互助平台的介绍 2559588
邀请新用户注册赠送积分活动 2482235