孟金涛等 : 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 bstract: Keywrds: Rectly, new sequcing technlgies have emerged, a new set f algrithms have be dped, and seral

科研信息化技术与应用 213, 4(5: 58 69 应用 / PPLICTION 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 孟金涛 1, 苑建蕊 2,3, 魏彦杰 1 1, 冯圣中 1. 中国科学院先进技术研究院高性能中心, 广东深圳 51855 2. 中南大学信息科学与工程学院, 湖南长沙 4183 3. 长园深瑞继保自动化有限公司, 广东深圳 51857 摘要 : 关键词 : 随着新一代测序技术的发展, 一些新的全基因组组装算法应运而生, 特别是针对第三代高通量测序仪产生的海量短序列的组装软件被不断开发出来, 这些组装软件渐渐走向市场 但是, 由于这些组装软件的适用性和其性能的差别, 选择一款性能优良的组装工具或者开发并行高吞吐的组装工具成为了当前面临的一大难题 本文选取基于 De Bruijn 图算法开发的 4 款 De Nv 组装的软件 (vet v B 对 4 种物种的基因组的模拟数据进行测试, 并从软件的算法 组装性能和组装质量 3 个方面分析这 4 个软件的性能, 同时根据其算法特点推断影响这些软件性能的关键因素, 并给出软件的使用建议以及开发并行序列组装工具来组装超大规模的基因数据应该注意的问题 组装软件 ;De Bruijn 图 ;DN 测序技术 ; 性能分析 ; 质量评测 The nalysis f De Nv Gme ssembly Sftware Based n De Bruijn Graph Mg Jinta 1, Yuan Jianrui 2,3, Wei Yanjie 1, Fg Shgzhng 1 1. High Perfrmance Cmputing Cter, Shzh Institutes f advanced Technlgy, Chinese cademy f Scices, Shzh, Guangdng 51855, China 2. Departmt f Cmputer Scice and Technlgy, Ctral Suth University, Changsha, Hunan 4183, China 3. CYG SUNRI C., LTD. Shzh, Guangdng 51857, China 基金项目 : 国家自然科学基金 (1124342; 深圳市基础研究基金 (JCY2126151491221; 深圳市孔雀计划 (KQCX213628112914299 58

孟金涛等 : 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 bstract: Keywrds: Rectly, new sequcing technlgies have emerged, a new set f algrithms have be dped, and seral assembly sftware packages have be created specifically fr assembly f next-geratin sequcing data. Hwer, due t the pr knwledge abut the applicability and perfrmance f these sftware tls, chsing a befitting assembler becmes a tugh task. Here we cmpare the perfrmance betwe vet, v, B and, which all are dped based n De Bruijn graph. We cmpare cmputatinal time, assembly accuracy and integrity, ur cmparisn study will assist researchers in secting a wl-suited assembler and ffer esstial infrmatin fr the dpmt f existing assemblers. assembler sftware; De Bruijn Graph; sequcing technlgy; perfrmance analysis; quality f cntigs 引言基因是具有遗传效应的 DN 分子片段, 是生命的密码, 记录和传递着遗传信息, 基因测序是测定生物体内遗传基因组的序列 自 1977 年 Sanger 测序法问世以来, 人类已经获得了 8 多种细菌体和 1 多种真核生物体的基因组序列, 数以万计的基因组序列已经被存入基因库中, 然而这只是现有物种中极少的一部分, 大量物种仍需要被测序 现代医学研究表明, 几乎所有的疾病都和基因有关系 基因测序的结果有助于揭示遗传与变异奥秘, 并且广泛应用于基因诊断 基因治疗 药物设计等领域, 而基因测序中最为重要的一部分就是测序后的序列组装 [1-3] 新一代基因测序技术所产生的序列片段具有序列短 高覆盖率 额外的双端信息等特点 大量的 verlap ( 重叠区域 的产生, 增加了组装算法的计算量, 初始测序数据的庞大对算法内存的要求随之增加 [4] 这就使得序列组装软件不仅要处理重叠区域, 片段间隔, 还要处理短片段 而且短片段通常使得前两个问题更加严重 dv 序列组装问题就是对测序产生的大量长度为 5bp 到 1bp 的重叠序列片段进行比对合并, 以重构源序列 而基因组源序列的长度长达几个 Gbp 因此, 如果没有高效的序列组装软件, 对大基因组测序后产生的数以亿计重叠序列片段进行组装几乎是不可能的 随着序列片段越来越短, 序列组装算法也经历了三种算法的变迁, 最先出现的算法是 先重叠后 扩展 (OLC 算法, 其代表软件包括 PHRP [5] TIGR [6] CP3 [7] Cera [8] RCHNE [9-1] Phusin [11] KE [12] CKE [13] 和 SHRCGS [14] 等, 其核心思想都是利用数据结构中的前缀树检索数据, 找到 read 间匹配的 verlap, 把短序列组装成 cntig 但是, 此类软件运行依赖数据结构, 需要消耗大量的内存, 运行速度比较慢, 并且错误率特别高 接着出现的是串图算法 [15-16], 该类工具用结点代表每个 read, 若节点 u 中的 k 个核苷酸与 v 中的前缀的 k 个核苷酸相同, 那么从顶点 u 到顶点 v 存在一条边 串图算法最后得到没有分支的最大路径 因为通常许多 read ( 大于 25% 有一个或两个错误, 往往会造成边或分支的缺失, 容易限制 cntig 的长度 现在使用最多的是 De Bruijn 图算法, 其代表软件包括 Euler [17-19], llpaths [2],vet [21] B [22] v [23] 和 [24] 等 该算法思想是 反直觉 法 : 在将 reads 组装前, 将其切分为长度为 k 的子串, 每一个节点 N 代表了一系列长度为 k 的子串, 称为 k-mers 相邻的 k-mers 之间存在 N-1 个重叠的碱基 基因序列的排布信息由依次重叠的 k-mers 的最后一个碱基的读取顺序决定 N 节点上的基因序列的内容表示为 s(n 由于序列的测定的方向性并不明确, 为了保证序列组装的正确性, 对于每一个 N 节点, 都有一个反向的 N ' 节点而对应,N 与 N ' 是关联在一起的, 所有对于 N 的操作同时也对 N ' 有效 De Bruijn 图算法的目的在于得到没有分支的最大路径, 基于此最大路径, 得到 cntigs De Bruijn 图算法的主要工作就是 59

科研信息化技术与应用,213, 4 (5 通过获得的原始数据构建一个有众多 N 节点的图, 然后用 边 来连接这些节点, 从而构建一个连续的序列信息 [25] 由于新一代测序技术产生的序列很短, 从而使得采用第一种 OLC 算法的组装软件 ( 如 :PHRP [5] TIGR [6] CP3 [7] Cera [8] RCHNE [9-1] Phusin [11] 大部分无法使用了, 而其他软件如 KE [12] CKE [13] 和 SHRCGS [14] 等, 在基因长序列组装中更占有优势, 并不完全适用于基因短序列组装 与 OLC 组装算法不同,De Bruijn 算法不再以 read 为单位组织数据, 而是以 k-mers 为单位进行数据组装, 其优点主要有以下 3 个方面 : (1 以 k-mers 为单位进行序列组装, 不影响节点的质量, 减少了冗余数据量 (2 在图中重复区域只出现一次, 便于识别, 可以避免错误的组装, 减小出错率 (3 采取将有重叠区域映射到同一条弧上的策略, 从而简化了搜索路径 目前, 很多短序列组装软件都使用这种框架, 如 Euler [17-19] llpaths [2] vet [21] B [22] v [23] 和分布式的 [24] 对于这些不断出现的 de nv 组装软件, 如何比较并分析这些序列组装软件变得至关重要 而上面所述的基于 De Bruijn 图算法的组装软件性能不一, 组装结果质量也各不相同, 给测序人员 ( 如华大基因, 中科院青岛海洋所, 上海生物信息技术研究中心等 选择一款合适的组装软件带来了困难 同时为了优化或者开发新的基于 De Bruijn 图算法的软件, 科研人员也希望能对现有最新的 de nv 组装软件性能有一个比较广泛而深刻的认识, 以指导开发或者优化出新的性能优良, 质量良好并适用于下一代的测序技术的新型组装软件 因此我们需要对这些软件从算法特点, 性能和质量方面, 比较这些组装软件, 并对比较的结果从算法角度给出分析和解释 目前, 已有部分研究人员对组装软件做出了系统的介绍和比较 其中 Suying Ba [26] 使用了两组测序数据对 QSR [27] KE [12] Eda [28] vet [21] v [23] 和 [24] 6 个组装软件做了性能 和组装结果质量的简单分析, 结果表明 v 性能优异 Jasn R. Miller [29] 主要从算法的角度对组装算法进行了分类, 然后对使用 de Brujin 图算法的 5 个组装软件 Euler [17-19] vet [21] [24] llpaths [2] v [23] 分别进行了算法阐述和分析 Wxu Zhang [3] 在其论文中同时对 OLC 算法和 de brujin 图算法的组装软件的性能和组装结果质量基于八套模拟数据做了测试分析, 结果阐明各个软件均有其适用空间, 即长达大约 75bp 的微生物数据可以使用 OLC 算法的组装软件, 而其他情况短序列以及真核生物需要使用 De Bruijn 图算法的组装软件 虽然作者分别对多种算法的软件进行了介绍, 但缺乏针对性, 其次该文没有包括 B 这个性能优异的软件, 最后该文并未分析影响这些组装软件性能和质量的关键因素 本文选择了基于 De Bruijn 图算法的 4 个组装软件, 即 vet [21] B [22] v [23] 和分布式的 [24] 在 4 个物种的八组数据 ( 其中每个物种包括 Single d, 和 Paired d 的测序数据 做测试, 并从算法, 组装性能, 和组装质量 3 个方面分析这 4 个软件的性能, 同时根据其算法特点推断影响这些软件性能的关键因素, 并指导我们以后从哪几个方面开发性能更好, 质量更优的组装软件 本文接下来, 第二章将逐一分析上述 4 个基于 De Bruijn 图的组装软件的算法特性, 第三章将综合分析这 4 个组装性能, 并总结出影响各软件的性能的关键因素, 第四章对 4 个组装结果的质量进行分析, 并找出最优异的组装软件, 并解释其原因, 第五章总结了本文工作并提出了几点对未来基于 De Bruijn 图并行组装软件开发的指导建议 1 基于 De Bruijn 图的组装软件算法比较新一代基因测序技术所产生的序列片段具有序列短 高覆盖率 额外的双端信息等特点 这和前两代测序技术不同, 因此这些特点使得一些传统的拼接工具无法使用 如果序列片段没有引入测序错误, 而且序列片段均匀取样 ( 没有 gap, 那么拼接问题还是比 6

孟金涛等 : 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 较简单的 简而言之, 测序数据 ( 组装软件的输入数据 的特点, 导致了拼接问题的内在复杂性和困难 (1 测序错误率 - 产生序列片段的过程中可能伴随由于荧光强度识别问题带来测序误差, 例如, 一个碱基 T 可能被测序仪读出为 这些错误是难以避免的, 而且这个范围通常是.5% ~ 2% 之间 这就意味着一个长度为 75bp 的源序列如果带有 1% 的错误率, 那么将导致有一半以上的测序产生序列片段可能有错误碱基 (2 覆盖度 - 序列片段必须要互相重叠才能重新拼接, 覆盖度是指 DN 源序列上的一个特定碱基位置上平均覆盖的序列片段数 非均匀分布或者低覆盖度意味着可能基因组源序列上的某些位置并没有被覆盖到 这样将产生空隙 (gap 在实际测序中覆盖度通常为 1 ~ 1 (3 重叠区域 - 有些 DN 序列的某些子序列可能在多处重复出现, 这些子序列就叫做重复区 这给序列拼接带来困难, 例如在表 1 中给出了基因组源序列长度为 5.6M 的大肠杆菌的重复区统计表, 其中长度为 1 的重复区超过了 1 个 需要指出的是, 现在还没有算法能够解决超过序列片段长度 ( 第三代测序技术只能产生长度 5-1bp 的序列片段 的重复区问题 短基因片段的组装导致了大量的 verlap, 这大大加大了组装算法的计算量 大量的 repeat, 使得组装错误率增加, 严重影响了组装结果 能否有效表 1 E.cli 中的重复片段 Table 1 Repeats statistics in E.cli referce sequces 长度 (bp 出现次数 3 3899 4 2784 5 2248 1 174 2 536 3 345 5 2 1 11 的解决这两个问题, 成为评价一个组装算法优劣的关键 [29] 基于 OLC 组装算法开发的软件, 如 KE [12] CKE [13] SHRCGS [14] 等, 在基因长序列组装中更占有优势, 并不完全适用于短序列组装 与 OLC 组装算法不同,De Bruijn 算法不再以 read 为单位组织数据, 而是以 k-mers 为单位进行数据组装, 其优点主要有以下几个方面 : 首先, 以 k-mers 为单位进行序列组装, 不影响节点的质量, 减少了冗余数据量 其次, 在图中重复区域只出现一次, 便于识别, 可以避免错误的组装, 减小出错率 最后, 采取将有重叠区域映射到同一条弧上的策略, 从而简化了搜索路径 目前, 很多短序列组装算法都使用这种框架, 如 vet [21] B [22] v [23], 和运行于高性能集群上的分布式组装器 [24] 下面将这几种组装算法简单介绍 1.1 ELET vet [19-2] 有效的利用了 De Bruijn 图, 实现了高效的短序列组装 vet 以 k-mer 为基本单位构建 De Bruijn 图, 利用图的结构, 结合相应的序列特征, 简化图的构造, 最终找到一条最优路径完成组装过程 vet 把焦点集中在错误的数据产生的三种结构上, 即 tip bubble 以及 errneus cnnectin [19] 它依照长度原则和少数性原则, 将长度小于 2k 的均去除 ; 利用 Tur Bus 算法中的深度优先搜索策略合并 bubble, 最后利用覆盖度阈值法去除了 errneus cnnectin 该方法也充分利用了 paired-d 双端信息, 进一步解决 repeat 问题, 优化了组装效果 vet 充分利用图的结构性质, 简化了数据冗余, 速度较之前的算法有了很大的改进 虽然它没有在预处理阶段对序列进行纠错, 但是其对错误的预防机制, 很大程度上的弥补了这方面的缺陷 这使得它更好的应用在大型基因组序列的组装中 [2] 1.2 B B 基于 De Bruijn 图, 实现了简便且高效的短序列组装 [21] B 以 k-mer 为基本单位, 与以往 61

科研信息化技术与应用,213, 4 (5 不同的是, 它采用一个变化的 k 值域 (Kmin-Kmax, 代替使用固定的 k 值来得到 k-mers 的长度 由于基因组装以 k-mers 为单位, 通常会形成很多个重叠单元, 这使得组装面临着错误位置组装 顶点缺失和覆盖度低的问题 正确的选择 k 值的大小成为组装的一个关键因素 一些错误的 reads 的产生, 也导致产生了大量的 branching k 值越小,branching 问题越严重, k 值越大, 则出现的 reapt 区域则变少, 这直接影响了组装的质量 B 采用不固定的 k 值进行组装, 可以很好的解决 branching 问题, 从而, 提高了组装的质量 另外 B 通过删除低覆盖率的错误 k-mers 而使得 B 的内存使用率明显降低, 同时也提升了 B 的处理速度 1.3 PDENOO 以上介绍的组装软件都实现了细菌体及真菌体基因组的组装, 但是由于当前巨型计算机的内存限制, 并不适用于处理大的基因组组装, 如人类基因组 v 也是 De Bruijn 图算法的另一个应用, 能够高效高质量的完成数以亿计的 reads 的组装 [22] v 继承了 OLC 算法和 De Bruijn 图算法的优点, 使得其组装质量大为提高 P 通过预置 k-mer 阈值的方法, 采取过滤 纠错的方式减少了错误序列的产生 同时, 它借鉴了 vet 软件的方法成功处理了 bubble, 使得其平均覆盖度增加 另外, v 利用了双端信息进行进行重叠区域匹配, 并合并 read 生成 cntig 片段, 生成基于 cntig 的图结构, 从而,v 大大简化了 cntig 图的复杂性 [31-33] 1.4 BY 随着 GS FLX,L 系统等的测序技术的不断 发展, 高通量测序长度分布在 5bp 到 5bp 不等 [23] 大多数的基因组装软件都是运行在单线程的, 如 vet [19-2] llpaths [2] Euler-SR [17-19] 等等, 在运行 时间和内存消耗方面并不是很令人满意, 尤其是在处 理大的基因组的情况下 在此基础上, [24] 引进 并行计算的思想, 搭建了一个 linux 集群, 在集群上 建立了一个分布式的 De Bruijn 图结构, 将数据分布 式存储于每个节点上 其采用 MPI 通信机制完成节点 之间的相互通信 从构建图 纠错处理到后面的定点 融合, 最后完成整个基因组序列的再现, 其在运行时 间和内存消耗方面占有很大的优势, 并且其错误率极 低, 在性能方面特别是 cluster 中单机内存使用上均有 很大的提升, 正在得到越来越广泛的应用 2 基于 De Bruijn 图的组装软件性能比较 2.1 测序数据 本文测试数据选择 Swinepx virus winepx Escherichia cli str.k-12substr (E.cli Saccharmyces cerisiae (Yeast Carhabditis egans (C.egans 四种基因组, 其参考序列分别下载于 NCBI 基因 库的文件 (NC_3389,NC_913,NC_1133- NC_1148,NC_3279-NC_3284 我们使用 [3] Yifei Tang 开发的 Perl 脚本来生成实现所需要测 试数据, 其相应参数设置为, 单端测序 read 长达 36bp, 双端测序 read 长达 72bp, 错误率为 1%, 四个 物种测试数据的详细信息见表 2 表 2 测试数据质量信息 Table 2 Data quality Infrmatin f fur species 物种 参考序列长度 总数据大小 平均序列长度 平均覆盖度 错误率 Swinepx 146K 24M 36bp 5X 1% E.cli 4.5M 1G 36bp 5X 1% Yeast 12M 2.5G 36bp 5X 1% C.egans 98M 2G 36bp 5X 1% 62

孟金涛 等: 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 的 单结点 16 核 的序列都无法完成 2.2 组装软件 本实验平台为中国科学院深圳先进技术研究院 C.egans 的组装 对这几个相应的测试结果我们都标 超算中心曙光5 超算平台 该平台使用 72 台 4 路 注为 通过分析收集数据 我们做出其运行时间和 4 核心 MD Shanghai 节能 CPU 闲时时钟频率为 内存使用对比图形来直观分析其计算性能 图 1 是运 8Mhz 工作时频率为 1.8Ghz 所有服务器内存标 行时间对比图 图 2 是内存使用对比图 准配置为 32G 集群内部由 InfiniBand 的大小为 2G 在图 1 中 我们使用四个序列组装软件分别对 4 个物种单端和双端序列进行组装时所消耗的 CPU 的光纤实现网络通信 测试的软件版本如表 3 所示 时间做了对比 其中耗时最长的组装软件是使用单 个进程的 而耗时最短的单进程组装软件是 表3 软件版本 B 虽然使用单个进程的 在四个组装软件 Table 3 Sftware versin f sected assemblers 软件名称 软件测试版本(versins ELEET vet_1.1.4 B 中耗时最长 但是单结点 16 核 在总的组装时 间上要比单进程的 略有降低 但依然比 B 耗费的时间要长 4 节点 64 核 的运行时间虽 B_.2 PDEBOO 然有进一步的下降 但也还是比 B 的时间要长 v_v1.5 BY 所以 使用多核加速的性能并不显著 值得一 _1.2.7 提的是 v 在多数物种上的组装时间上实 际上与 B 相当 但只是在最后一个测试数据上耗 2.3 性能分析 时略多于 B 所以大多数情况下 v 的 本文选取的四款组装软件分别对 Swinepx 耗时与 B 的耗时相当 E.cli Yeast C.egans 四种物种模拟 8 套数据进行 在图 2 中 随着测试数据规模的增大 四个组 时间和内存使用情况的数据 其中 SE 代表 Single 装软件在组装相应的测试数据时 内存消耗也逐渐增 d 单端序列片段 代表 Pair d 双端序列片段 大 其中 v 在所有组装软件中内存消耗 由于服务器内存只有 32G vet 单 CPU 运行 最大 而 B 在四个组装软件均使用单进程时内存 B t (m ul d ea r ith v n e et lv e CPU (s y B U CP (1 CPU (s y B (1 CPU (s B U P 6C CPU (s S ys ( CPU (s PU C 64 CPU (s 1 9 8 7 6 5 4 3 2 1 Yeast CPU (s CPU (s 序列组装 并通过 shl 脚本监视测得的 CPU 运行 C. egan E. cli Swinepx 图1 使用序列组装软件对分别对 4 个物种单端和双端序列进行组装时所消耗的 CPU 时间对比 Fig. 1 The CPU time usage cmparisn n assembling these fur species using single-d and pair-d data 63

科研信息化技术与应用 213, 4 (5 Yeast Mem (MB Mem (MB Mem (MB Mem (MB Mem (MB Mem (MB Mem (MB U CP PU 4 (6 6C PU d S (1 1C y ea ( r B S S h tit v ys et ul lv e B d (m P B Mem (MB 35 3 25 2 15 1 5 C. egan E. cli Swinepx 图2 使用序列组装软件对分别对 4 个物种单端和双端序列进行组装时所消耗的内存对比 Fig. 2 The memry usage cmparisn n assembling these fur species using single-d and pair-d data. 增长速度最慢 所以 B 在单进程时对组装软件的 件组装速度 但是在我们最终的实验中显示其加速 内存消耗控制效果要好于其他三个组装软件 但是当 效果比较一般 使用多进程来组装软件时 其单个进程的内 这四款软件为了优化其组装结果的质量 对其 存消耗显著降低 并且远低于 B 的单个进程内存 使用的 De Bruijn 算法也有一定的改进 这实际上也 消耗量 的这个显著优点使得其在使用在高 是另一个影响软件性能的因素 我们这里将在下一 性能集群时 对单个计算节点的内存要求显著降低 章详述 尤其是在处理更大规模的基因组时将发挥显著优势 而其他 3 个组装软件在组装大规模基因组时 其能否 3 基于 De Bruijn 图的组装软件结果质量比较 组装成功则取决于单个节点的内存大小 这四款组装软件虽然都使用 De Brujin 图算法 新一代的测序技术得到的 read 不仅长度更短 但是其并行优化策略各不相同是这 4 款软件性能 而且其数量又极为巨大 覆盖度高 组装得到的 各不相同的重要因素 t 未做任何并行优化 cntigs 的数量和 cntigs 的长度也成为衡量组装质量 B 和 v 只能运行于单个服务器 这 的重要指标 本文选取上述提供的软件对四种物种 8 3 个软件会受到服务器内存的限制而不能组装大的 组单端和双端测序数据组装后 收集了组装结果 并 基因组 其中 v 自动开启多线程参与计 统计了长度大于 1bp 的 cntig 的数目 基因片段的 算 但是最多只能利用半数的 CPU 来加速计算 而 总大小 最大的 cntig 的长度 平均 cntig 的长度 B 中使用了 OpMP 能够利用服务器所有 CPU 以及 N5 的大小等指标 在本章 我们将通过分析总 加速计算 是这四个软件中唯一的一款分布 的 cntigs 的数目和长度大于 1bp 的 cntig 的数目 式的的组装软件 它通过在集群系统上使用 MPI 来分析 cntigs 的数量 然后利用最大的 cntig 的长 利用集群系统的分布式内存存储 De Brujin 图 并把 度和 N5 两个指标来衡量 cntigs 的长度 最后综合 相应的计算任务分配到集群的每个 CPU 上来提高软 这两方面来确定这 4 款软件组装结果的质量 64

孟金涛 等: 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 结合这 4 个组装软件的算法 我们发现 B 3.1 Cntigs 数量分析 根据经验 cntigs 的数量越小 软件的组装质 使用的是多个 K-mer 长度 并且能够迭代合并扩展 量越高 在此 我们选取总的 cntigs 的数量以及长 cntigs 这是其 cntig 数量远少于其他同类软件的主 度大于 1bp 的 cntigs 的数量两项指标做了相关的 要原因 K-mer 过滤和纠错也使得错误 K-mer 数量减 数据分析和对比 如图 3 所示 结果显示 一方面 少 进而减少 De Bruijn 图的分叉 最终使得 cntigs 从总的 cntigs 的数量上看 无论是从小的基因组还 的数量少而且长 而 v 和 B 均使用了 是大的基因组 其用 B 软件组装之后 得到的 相关策略来减少其 cntigs 的数量 其中这两个软件 cntig 数量远远小于其他组装软件 而 v 在长度大约 1bp 的 cntigs 数量上要明显少于其他 软件组装之后得到的 cntig 数量远远超过其它组装软 软件 件 由此可以得到 从得到的 cntig 数量上来看 B 软件占有明显的优势 v 仍需要在 3.2 Cntigs 长度分析 此方面进行更好的改进 另一方面 从大于 1bp 的 Cntig 的长度越长 其组装效果越好 错误率越 cntig 的数量与总的 cntig 的数量上的比例上看 其 低 而 cntigs 的长度通常可以从 cntigs 的最长长度 B 在组装时产生的大于 1bp 的 cntig 的数量的 和 N5 两个参数衡量 在此 我们分别对四种物种基 比例占总量的比例最大 由此间接反映了 B 的性 因组进行测试 在此 选取 cntig 的最大长度和 N5 能优良 大小分别作图 进行对比分析 如图 4 图 5 所示 Swinepx E. cli 8 5 6 4 3 4 2 2 1 Number f cntigs (lgth>=1bp B Number f cntigs (lgth>=1bp C. egans 2 5 4 15 1 3 2 1 5 SE Number f cntigs (lgth>=1bp B B v v SE Number f cntigs v v B B v Number f cntigs Yeast 6 B Number f cntigs v SE B B v v SE Number f cntigs Number f cntigs (lgth>=1bp 图3 组装结果中总的 cntigs 的数量以及长度大于 1bp 的 cntigs 的数量对比 Fig. 3 The cmparisn f fur species n the number f cntigs and cntigs with lgth larger than 1bp 65

科研信息化技术与应用 213, 4 (5 如图 4 所以 我们可以得出 从最大的 Cntig 于单端组装得到的 cntig 的长度 可见 B 很好 长度上比较 对于不同的物种 v 组装得 的应用了双端序列中的信息 有效地减小了错误率 到的 Cntig 的长度大于 vet 的长度 其这方面 大大提高了组装效果 组装得到的最大 cntig 其有很大的改进 而 B 组装所产生的 cntig 的长 的长度比较小 在这方面 其仍需要进行优化 度最长 并且其双端组装得到的 cntig 的长度远远大 根据图 5 分析 可以得知 对于不同物种来说 14 12 1 8 6 4 2 Yeast C. egans SE ve ve v v B B by ss ss Swinepx E. cli 图4 分别用四种不同的软件对四种物种进行组装之后最大 cntigs 长度的数据分析图 Fig. 4 The results analysis n the max lgth f cntigs by assembling fur species with fur sected assemblers 14 12 1 8 6 2 ep li Sw c E. Y s an eg C. ve SE ve ea st B in B x v v E ss by s s( 4 图5 分别用四种不同的软件对四种物种进行测试之后 N5 的数据分析图 Fig. 5 The results analysis n N5 f cntigs by assembling fur species with fur sected assemblers 66

孟金涛等 : 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 不受基因组大小的限制, 用 B 软件测试出来的 N5 的长度远远大于其他几种软件测试出来的结果, 并且, 其在单端测序和双端测序方面差别显著, 其很好地利用了双端序列中存在 Paired-d 的信息 实验表明, 对于 vet 来说, 在测试数据量比较小的基因组时, 其双端测序的 N5 的长度远远大于单端测序的结果, 说明其在测试较小基因组时, 很好的利用了双端序列中的信息, 但是随着基因组数据量的增大, 其结果质量有逐渐下降的趋势 v 在测试 N5 大小时, 单端序列组装的结果优于双端序列组装的结果 对于 软件, 其在单端组装和双端组装上, 没有很明显的区别 基于对 4 个组装软件算法分析,B 和上一小节一样, 由于其使用多个 K-mer 长度, 并且能够迭代合并扩展 cntig, 这是不仅使得 cntig 数量减少, 而且 cntig 的长度也远长于其他同类软件 而其他软件由于只用了一个 Kmer 长度来构建收缩其 De Bruijn 图, 所以在 cntig 长度和 cntig 数量上均处于劣势 值得一提的是, 由于 v 在分支解耦方面采用激进的 cntigs 合并策略, 即使可能引入错误也会追求更长的 cntigs, 所以其 cntigs 的长度要长于 vet 和 组装软件 最后由于 的主要重点在其并行策略上, 而其相应的组装质量, 包括 cntig 的数量,cntig 的长度等, 都要差于其他同类软件 4 总结结合第二章对这四款软件的算法分析, 我们可以进一步分析这四款软件的算法优化对其组装结果的影响 由于 B 使用的 K-mer 取值从 3 到 5, 累计最好的 cntigs, 而这一方法在得到更好的质量结果上起到很大作用, 所以最终组装质量分析显示, 从 N5 大小, 最大 cntig 长度, 以及得到的 cntig 的数量等三项项指标上看,B 的组装质量最高 其次 v 和 vet 都使用了路径解耦 (cntigs merge 来进一步提高 cntigs 的长度, 而使得 v 和 vet 结果比较好, 然而实验显示 v 在对大物种的基因组进行序列组装时, 其组装质量优于 vet,vet 在小物种基因组的组装质量要优于 v 最后由于 在图的收缩 (Graph simplificatin 操作后没有进一步的处理, 从而导致 的组装质量并不比其他软件占有优势 这四款组装软件虽然都使用 De Brujin 图算法, 但是其并行优化策略各不相同是这 4 款软件性能各不相同的重要因素 t 未做任何并行优化,B 和 v 只能运行于单个服务器, 这 3 个软件会受到服务器内存的限制而不能组装大的基因组 其中 v 自动开启多线程参与计算, 但是最多只能利用半数的 CPU 来加速计算, 而 B 中使用了 OpMP, 能够利用服务器所有 CPU 加速计算 是这四个软件中唯一的一款分布式的的组装软件, 它通过在集群系统上使用 MPI, 利用集群系统的分布式内存存储 De Brujin 图, 并把相应的计算任务分配到集群的每个 CPU 上来提高软件组装速度, 但是在我们最终的实验中显示其加速效果比较一般 5 总结与展望新一代测序技术的发展, 使得一些传统的基因组装算法无法适用于海量的短序列片段的组装, 新一代的组装算法应运而生 由于这些组装软件的适用性和其性能的差别, 选择或者开发一款性能优良的组装工具成为了当前面临的一大难题 在此领域, 目前已经有很多人做了相关的工作, 但是缺乏针对性研究, 缺乏对软件组装性能 组装质量等方面的分析阐述 针对当前序列高通量, 长度短的特点, 针对当前不断出现的 de nv 组装软, 本文选择基于 De Bruijn 图算法的四个组装软件, 即 vet [21] B [22] v [23] 和分布式的 [24], 分别对其进行从小物种基因组到大物种基因组四种基因组, 进行单端组装和双端组装两种形式的组装测试, 并从算法 组装性能和组装质量 3 个角度对软件性能做了分析, 找出性能优良的软件 实验表明,B 组装软件内存消耗最小, 并且组装用时最少, 在组装质量方面, 67

科研信息化技术与应用,213, 4 (5 无论是对大的基因组还是对小的基因组, 从 N5 大小 cntig 的数量以及最大 cntig 的长度等三项指标分析, 其组装质量也远远优于其他组装软件 BY 软件是基于 De Bruijn 图算法的唯一一款并行软件, 在计算性能上得到了优化, 减小了内存消耗, 减少了运行时间, 但是在组装质量上仍不为乐观, 仍需要很大的改进, 有很大的研究空间 本文系统讲述了基于 De Bruijn 图算法的四种组装软件, 为进一步进行新型并行组装软件的开发和应用的研究奠定了坚实的基础 但是, 这些组装软件仍存在一些问题, 如对重叠区域的处理而引起的错误组装问题, 软件组装覆盖度问题等等, 这些仍对组装结果产生重要的影响 因此, 在未来的工作中, 我们将重点研究基因组装领域如何处理基因组装错误的问题, 并在此基础上开发并行的序列组装工具来组装超大规模的基因数据 致谢本文工作由自然科学基金 NSFC ( 基金号 : 1124342, 以及深圳市基础研究基金 ( 基金号 : JCY2126151491221 共同资助. [6] Suttn G, White O, dams M, Kerlavage. TIGR ssembler: new tl fr assembling large shtgun sequcing prjects [J]. Gme Scice Technlgy, 1995, 1: 9-19. [7] Huang X, Madan, CP3: DN sequce assembly prgram [J]. Gme Research, 1999. 9:868-877. [8] Myers E, Suttn G, Dche, Dew I, et al. whlegme assembly f Drsphila [J]. Scice, 2, 287:2196-224. [9] Batzglu S, Jaffe O, Stanley K, et al. RCHNE: whle-gme Shtgun assembler [J]. Gme Research, 22. 12:177-189. [1] Jaffe D, Butler J, Gnerre S, et al. Whle-gme sequce assembly fr mammalian gmes: RCHNE 2 [J]. Gme Research, 23, 13:91-96. [11] Mullikin J, Ning Z. The Phusin assembler [J]. Gme Research, 23, 13:81-9. [12] Warr R, Suttn G, Jnes S, Hlt R. ssembling millins f shrt DN sequces using KE [J]. Biinfrmatics, 27, 23(4: p. 5-51. [13] Jeck W, Reinhardt J, Baltrus D, et al. Extding assembly f shrt DN sequces t handle errr [J]. Biinfrmatics, 27, 23(21:2942-2944. [14] Dhm J, Lttaz C, Brdina T and Himmbauer H. 参考文献 [1] Mihai P. Gme assembly rebrn: rect cmputatinal challges[j]. Briefings in Biinfrmatics, 29, July, 1(4:354-366. [2] Mihai P, Salzberg S, Shumway M. Gme sequce assembly: algrithms and issues [J]. Cmputer, 22, 35(7:47-54. [3] J.Craig, Mark D, et al. The Sequce f the Human Gme [J]. Scice 21, 291(557:134-1351. [4] Jay S, Hanlee J, Next-geratin DN sequcing [J]. Nature Bitechnlgy, 28, 26:1135-1145. [5] Ewing B, Gre P. Base-calling f autmated sequcer traces using Phred. II. Errr prbabilities [J]. Gme Research, 1994. 8:186-194. SHRCGS, a fast and highly accurate shrt-read assembly algrithm fr de nv gmic sequcing [J]. Gme Research, 27, 17(11:1697-76. [15] Hernandez D, Francis P, Farinli L, Osteras M, and Schrz J. De nv bacterial gme sequcing: millins f very shrt reads assembled n a desktp cmputer [J]. Gme Research, 28, 18(5:82-89. [16] Myers E, The fragmt assembly string graph [J]. Biinfrmatics, 25. 21 uppl 2: 79-85. [17] Pzner P, Tang H, Waterman M. n Eulerian path apprach t DN fragmt assembly [J]. Prc. Natl. cad. Sci, 21, 98(17:9748-53. [18] Chaissn M, Pzner P. Shrt read fragmt assembly f bacterial gmes [J]. Gme Reseach. 28, 18:324-68

孟金涛等 : 基于 De Bruijn 图的 De Nv 序列组装软件性能分析 33. [19] Chaissn M, Brinza D, Pzner P. De nv fragmt assembly with shrt mate-paired reads: Des the read lgth matter [J]. Gme Research, 29, 19(2: 336-346. [2] Jnathan B, Iain M, Micha K. LLPTHS: De nv assembly f whle-gme shtgun micrreads [J]. Gme Research, 28, 18: 81-82. [21] Zerbin R, Birney E. vet: lgrithms fr de nv shrt read assembly using De Bruijn graphs [J]. Gme Research, 28, 18: 821-829. [22] Pg Y, Hry C, Yiu S, Francis Y. B S. Practical Cmparisn f De Nv Gme ssembly Sftware Tls fr Next-Geratin Sequcing Technlgies [J]. PLS One, 211; 6(3: e17915. [31] R.Li, H.Zhu, J.Ruan, et al. De nv assembly f human gmes with massivy parall shrt read sequcing [J]. Gme Research, 29, 2: 265-272. [32] R.Li,W.Fan,G.Tian, et al. The sequce and de nv assembly f the giant panda gme [J]. Nature, 29, 46:3311-317. [33] R.Li, Y.Li, H.Zhg et al. Building the sequce map f the human pan-gme [J]. Nature Bitechnlgy, 29, 28: 57-63. Practical Iterative De Bruijn Graph De Nv ssembler [C]. Research in Cmputatinal Mlecular Bilgy (RECOMB 21, 21, vl 644. [23] Miller J, Kr S, Suttn G. ssembly algrithms fr next-geratin sequcing data [J]. Gmics, 21, 95(6:315-27. [24] Simpsn J, Wng K, Jackman S, et al. : parall assembler fr shrt read sequce data [J]. Gme Research, 29, 19: 1117-1123. [25] Idury R, Waterman M. new algrithm fr DN sequce assembly [J]. Jurnal f Cmputatinal Bilgy. 1995, 2(2:291-36. [26] Ba S, Jiang R, Kwan W, et al. Evaluatin f nextgeratin sequcing sftware in mapping and assembly [J]. Jurnal f Human Getics, 211, 56, 46-414. [27] Bryant D, Wng W, Mckler T. QSR-a qualityvalue guided de nv shrt read assembler [J]. BMC Biinfrmatics, 29, 1: 69. [28] Hernandez D, Françis P, Farinli L, et al. De nv bacterial gme sequcing: millins f very shrt reads assembled n a desktp cmputer [J]. Gme Research, 收稿日期 :213 年 7 月 11 日孟金涛 : 中国科学院深圳先进技术研究院, 工程师, 中国科学院计算所在读博士研究生, 主要研究领域为并行分布式计算, 生物信息学 E-mail: jt.mg@siat.ac.cn 苑建蕊 : 长园深瑞继保自动化有限公司, 工程师, 硕士, 主要研究领域为并行计算, 智能电网 E-mail: yuanjr@sznari.cm 魏彦杰 : 中国科学院深圳先进技术研究院, 副研究员, 博士, 主要研究领域为生物信息学, 蛋白质折叠 E-mail: yj.wei@siat.ac.cn 冯圣中 : 中国科学院深圳先进技术研究院先进计算与数字工程研究所, 研究员, 博士生导师, 主要研究方向为高性能计算 网格计算 生物信息学 E-mail: sz.fg@siat.ac.cn 28, 18:82-89. [29] Miller J, Kr S, Suttn G, ssembly algrithms fr next-geratin sequcing data [J]. Gmics, 21, 95(6:315-27. [3] Wyu Z, Jiajia C, Yang Y, Yifei Tang, Jing S, Bairng 69