写在前面

rust-mdbg 是一种超快的minimizer-space de Bruijn graphs (mdBG) 实现，适用于组装长而准确的读数，例如PacBio HiFi。

随着18年以来Pacbio HiFi reads的出现，让一些复杂基因组的组装不再复杂，而且有越来越多的课题组也加入到了基因组学的研究中，正是因为有了高精度长读长的reads，目前也产生了很多专门用于HiFi组装的软件，如Hifiasm，当然这篇文章的软件的算法，可以用超短时间，低内存去组装。我相信随着不断的发展，以后做组装的时候甚至都不需要服务器，在个人电脑也可以实现。

内容写了很多，考虑到阅读体验，做了删减。
下面是正文～

原理介绍

DNA测序技术发展的很快，尤其是以Pacbio HiFi数据为代表的Long reads兼顾了长读长以及高准确度。

在这里，研究者定义了一种算法方法mdBG，它利用最小空间德布莱英图(de Bruijn graph)实现long reads基因组组装。

这里插入一个视频，让大家了解一下以前的组装软件用到的 de Bruijn graph的原理

De Bruijn Graph – 基因组组装算法讲解

与现有方法相比，mdBG 在速度和内存使用方面都实现了几个数量级的改进，而不会影响准确性。
实战使用8个核心和10 GB RAM在10分钟内组装人类基因组，使用1 GB RAM在4分钟内组装60 GB的宏基因组数据。

此外，研究者构建了661405个细菌基因组的最小空间de Bruijn graph，包括1600万个节点和4500万条边，并在12分钟内成功搜索了抗微生物耐药性（AMR）基因。

鉴于基因组学、宏基因组学和泛基因组学中长读长测序的兴起，预计这一进步对序列分析至关重要！

构建mdBGs的代码可免费下载， 址为
https://github.com/ekimb/rust-mdbg/

介绍

DNA测序数据持续改善，

• 从最开始低质量的长reads，用于组装第一批人类基因组
• 再到Illumina低误差率(%1%)的短reads，
• 目前低误差率的长reads。例如，Pacbio HiFi 1%的错误率产生10-25kbp长(HiFi)reads 进行测序；Nanopore的R10.3孔在~5%的错误率。

未来DNA测序最终将产生长的、近乎完美的reads。

这些新技术要求算法对基因组组装等重要序列分析任务既有效又准确。

两种方法虚线分开，上方按照顺序
虚线上方（下方) 的图形区域对应于在 基本空间(最小空间) 中进行的分析。
输入reads按顺序扫描，并识别所有属于预先选择的universe minimizers 的 δ-mers。 然后将每个reads表示为所选最小值的有序列表，并使用长度为 k 的滑动窗口从reads的最小空间表示中收集 k-min-mer。 然后从所有 k-min-mer 的集合构建最小空间 de Bruijn 图 (mdBG) 并进行简化，以减少歧义并消除错误。 然后通过连接由 mdBG 中的最小化器跨越的基空间序列，将 mdBG 转换回基空间，并 告一组contigs

通过使用mdBG执行组装，大大减少了向组装程序输入的数据量，保持了准确性，减少了运行时间，与当前的汇编程序相比，内存使用量减少了1到2个数量级。为de Bruijn图的阶数和最小化方案的密度设置适当的参数能够以与传统碱基空间组装类似的方式克服测序深度和read长度的随机变化。

Fig 4 base space到minimizer space的测序误差

总结