Pairwise sequence alignment is a very time-consuming step in common bioinformatics pipelines. Speeding up this step requires heuristics, efficient implementations, and/or hardware acceleration. A promising candidate for all of the above is the recently proposed GenASM algorithm. We identify and address three inefficiencies in the GenASM algorithm: it has a high amount of data movement, a large memory footprint, and does some unnecessary work. We propose Scrooge, a fast and memory-frugal genomic sequence aligner. Scrooge includes three novel algorithmic improvements which reduce the data movement, memory footprint, and the number of operations in the GenASM algorithm. We provide efficient open-source implementations of the Scrooge algorithm for CPUs and GPUs, which demonstrate the significant benefits of our algorithmic improvements. For long reads, the CPU version of Scrooge achieves a 20.1x, 1.7x, and 2.1x speedup over KSW2, Edlib, and a CPU implementation of GenASM, respectively. The GPU version of Scrooge achieves a 4.0x 80.4x, 6.8x, 12.6x and 5.9x speedup over the CPU version of Scrooge, KSW2, Edlib, Darwin-GPU, and a GPU implementation of GenASM, respectively. We estimate an ASIC implementation of Scrooge to use 3.6x less chip area and 2.1x less power than a GenASM ASIC while maintaining the same throughput. Further, we systematically analyze the throughput and accuracy behavior of GenASM and Scrooge under various configurations. As the best configuration of Scrooge depends on the computing platform, we make several observations that can help guide future implementations of Scrooge. Availability: https://github.com/CMU-SAFARI/Scrooge


翻译:基因组序列比对是常见生物信息学流程中耗时很长的步骤。加速该步骤需要启发式方法、高效实现和/或硬件加速。最近提出的GenASM算法是一种具有潜力的候选方案。我们确定并解决了GenASM算法中的三个低效问题:数据移动量大、内存消耗大且会执行一些不必要的工作。我们提出了Scrooge,一款快速且内存友好的基因组序列比对器。Scrooge包括三项新颖的算法改进,可以减少GenASM算法中的数据移动、内存占用和操作数。我们提供了针对CPU和GPU的高效开源实现,展示了算法改进带来的显著好处。对于长读取数据,Scrooge CPU版本相对于 KSW2、Edlib和GenASM CPU实现分别实现了20.1倍,1.7倍和2.1倍的加速。Scrooge GPU版本相对于Scrooge CPU版本、KSW2、Edlib、Darwin-GPU和GenASM GPU实现分别实现了4.0倍、80.4倍、6.8倍、12.6倍和5.9倍的加速。我们估计Scrooge ASIC实现的芯片面积和功耗都将比GenASM ASIC低3.6倍和2.1倍,而具有相同的吞吐量。此外,我们系统地分析了GenASM和Scrooge在不同配置下的吞吐量和精度行为。由于Scrooge的最佳配置取决于计算平台,因此我们提出了一些有助于指导未来Scrooge实现的观察结果。可访问性:https://github.com/CMU-SAFARI/Scrooge

0
下载
关闭预览

相关内容

最新《计算机体系结构和系统的机器学习》综述论文
专知会员服务
54+阅读 · 2021年2月17日
深度学习搜索,Exploring Deep Learning for Search
专知会员服务
57+阅读 · 2020年5月9日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Deep Compression/Acceleration:模型压缩加速论文汇总
极市平台
14+阅读 · 2019年5月15日
基于PyTorch/TorchText的自然语言处理库
专知
28+阅读 · 2019年4月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
12+阅读 · 2022年1月26日
VIP会员
相关VIP内容
最新《计算机体系结构和系统的机器学习》综述论文
专知会员服务
54+阅读 · 2021年2月17日
深度学习搜索,Exploring Deep Learning for Search
专知会员服务
57+阅读 · 2020年5月9日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Deep Compression/Acceleration:模型压缩加速论文汇总
极市平台
14+阅读 · 2019年5月15日
基于PyTorch/TorchText的自然语言处理库
专知
28+阅读 · 2019年4月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
利用动态深度学习预测金融时间序列基于Python
量化投资与机器学习
18+阅读 · 2018年10月30日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员