跳到正文
bioRxiv 生物信息学· Sanaullah, A., Zhi, D., Li, H., Zhang, S. ·· 8 天前精选AI 评分73

TeraMEM 在压缩空间与次线性时间内检测太碱基级基因组组装的完全匹配

Detection of Maximal Exact Matches in Terabases of Genome Assemblies in Compressed Space and Sublinear Time

AI 导读

预印本提出 TeraMEM 算法,在给定压缩索引的前提下,用 O(r) 内存和 O(r+occ) 时间计算组装面板两两之间的全部最长精确匹配(MEM)。在 625 个单倍型的人类着丝粒组装数据上,其内存占用比现有方法低 7.5 倍;计入索引构建时间时快 20 倍,不计入时快 2500 倍。

AI 深度导读基于原文整理的分节解读
背景
在成对基因组之间检测长精确匹配,长期是基因组学的一项基础操作;在群体遗传学中,对大规模基因分型芯片数据或全基因组测序变异调用里所有单倍型做两两同样的检测,同样是基础操作。随着近期多个泛基因组项目的推进,大规模高质量基因组组装面板首次开始被构建,于是出现了把这两类需求接起来的场景:在数百到数千个高质量组装构成的面板中,检测所有组装两两之间的长精确匹配。这类数据集包含数万亿碱基对,要实际检出全部精确匹配,算法必须至多在线性时间和压缩空间中运行。此前的方法如 Mumemto 已能做到,但在太碱基规模的泛基因组上运行仍占用极大空间、耗时很长。
做法
作者提出的算法在给定该面板压缩索引的前提下,以压缩空间和亚线性时间输出所有组装两两之间的长精确匹配。前提是先构建一个 O(r) 空间的压缩索引,这是一次性开销,可借助此前工作在压缩空间中、接近线性时间内完成。在此基础上给出三个算法,均占 O(r) words 内存:(1) 在 O(r) 时间计算所有超极大精确匹配(SMEM);(2) 在 O(r+occ) 时间计算所有 SMEM 及其出现位置;(3) 在 O(r+occ) 时间计算所有极大精确匹配(MEM)。其中 r 是组装面板 Burrows-Wheeler 变换中的 runs 数,occ 是输出的出现次数或匹配数。算法实现为 TeraTools 套件中的 TeraMEM。
结论
在来自 625 个单倍型的人类着丝粒组装数据集上,该方法占用的内存比当前最优的竞争方法少 7.5 倍;计入索引构建时间则快 20 倍,不计索引构建快 2,500 倍。作者还对 Human Pangenome Reference Consortium Release 2 数据集中所有组装良好的着丝粒做了全对全 MEM 分析,得到多项关于着丝粒结构变异的新观察。例如,2 号染色体活跃的 α-satellite 高阶重复(HOR)阵列,一侧被约 200 kbp 的倒位、另一侧被约 200–300 kbp 的假回文序列夹住。除 Y 染色体外,每条染色体的着丝粒中都检测到大片段重复,大小从数百 kbp 到数 Mbp 不等,且同时出现在活跃 α-satellite HOR 阵列内外。
意义
计算层面的结果是让泛基因组中的两两 MEM 分析变得可行;作者指出,对着丝粒所做的生物学分析说明这类分析很可能有用。算法以 TeraMEM 形式实现在 TeraTools 套件中并公开了代码地址。
局限
算法的时间和空间都以 r 为界,并依赖预先构建的该面板的 O(r) 压缩索引,索引构建虽是一次性开销,但仍是额外的计算成本。摘要中给出的内存与加速比较是在 625 个单倍型的人类着丝粒组装数据集上取得的。

本页是 AI 精读,不转载论文原文;完整论文(含方法、图表与参考文献)见原文

推荐理由

用压缩索引把全基因组组装两两最长精确匹配降到次线性时间,内存降 7.5 倍,可判断泛基因组比对是否用得动。

来源:bioRxiv 生物信息学 · biorxiv.org