已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!祝你早点完成任务,早点休息,好梦!

Clustering Billions of Reads for DNA Data Storage

计算机科学 聚类分析 可扩展性 加速 数据挖掘 管道(软件) 编辑距离 算法 公制(单位) 离群值 趋同(经济学) 噪音(视频) 人工智能 并行计算 数据库 图像(数学) 经济 经济增长 程序设计语言 运营管理
作者
Cyrus Rashtchian,Konstantin Makarychev,Miklós Z. Rácz,Siena Dumas Ang,Djordje Jevdjic,Sergey Yekhanin,Luís Ceze,Karin Strauß
出处
期刊:Neural Information Processing Systems 卷期号:30: 3360-3371 被引量:40
链接
摘要

Storing data in synthetic DNA offers the possibility of improving information density and durability by several orders of magnitude compared to current storage technologies. However, DNA data storage requires a computationally intensive process to retrieve the data. In particular, a crucial step in the data retrieval pipeline involves clustering billions of strings with respect to edit distance. Datasets in this domain have many notable properties, such as containing a very large number of small clusters that are well-separated in the edit distance metric space. In this regime, existing algorithms are unsuitable because of either their long running time or low accuracy. To address this issue, we present a novel distributed algorithm for approximately computing the underlying clusters. Our algorithm converges efficiently on any dataset that satisfies certain separability properties, such as those coming from DNA data storage systems. We also prove that, under these assumptions, our algorithm is robust to outliers and high levels of noise. We provide empirical justification of the accuracy, scalability, and convergence of our algorithm on real and synthetic data. Compared to the state-of-the-art algorithm for clustering DNA sequences, our algorithm simultaneously achieves higher accuracy and a 1000x speedup on three real datasets.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
阎罗恶煞发布了新的文献求助10
1秒前
1秒前
鱼大智发布了新的文献求助10
1秒前
琳666发布了新的文献求助10
1秒前
白开水完成签到 ,获得积分10
2秒前
3秒前
科目三的应助被激动的忆翠采纳,获得10
3秒前
yy32323完成签到,获得积分10
5秒前
orixero的应助被xue采纳,获得10
6秒前
鳗鱼鞋垫发布了新的文献求助10
6秒前
DXB发布了新的文献求助30
6秒前
琳666完成签到,获得积分10
11秒前
JamesPei的应助被jill采纳,获得10
11秒前
11秒前
绾绾完成签到 ,获得积分10
12秒前
风呼呼的好完成签到 ,获得积分10
15秒前
xiaoxiaozi发布了新的文献求助10
16秒前
YQP完成签到 ,获得积分10
16秒前
17秒前
8R60d8的应助被冷静新烟采纳,获得10
18秒前
zbjm881完成签到,获得积分20
18秒前
66发布了新的文献求助30
18秒前
Evan完成签到,获得积分10
18秒前
WilliamTT发布了新的文献求助10
18秒前
懒羊羊完成签到 ,获得积分10
19秒前
科研通AI6.4的应助被赵师傅采纳,获得10
19秒前
JamesPei的应助被yr采纳,获得10
22秒前
23秒前
淡淡听枫完成签到,获得积分10
23秒前
23秒前
岚岚伍发布了新的文献求助10
24秒前
可爱的函函的应助被成太采纳,获得10
25秒前
晚晚完成签到 ,获得积分10
26秒前
cun完成签到,获得积分10
30秒前
李健的应助被xiaoxiaozi采纳,获得10
31秒前
铅笔完成签到,获得积分10
31秒前
33秒前
34秒前
cj关注了科研通微信公众号
35秒前
脑洞疼的应助被rocsoar采纳,获得10
36秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 2000
Handbook of Sport Coaching Research 1000
Orthognathic Surgery - 2 Volume Set 500
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8194542
求助须知:如何正确求助?哪些是违规求助? 9580381
关于积分的说明 21870692
捐赠科研通 7794154
什么是DOI,文献DOI怎么找? 3437711
关于科研通互助平台的介绍 2560995
邀请新用户注册赠送积分活动 2484393