基于K-spectrum的下一代测序数据的纠错算法分析

广西科学院学报

2017,33(1):〜11

Vol. 33，No. 1 February 2017

网络优先数字出版时间：01 飊02-28 DOI ： 10. 13657/j. cnki. gxkxyxb. 20170228. 001

网络优先数字出版地址：http://kns. cnki. net/kcms/detail/45. 1075. N. 20170228. 1016. 002. html

基于K-spectrum的下一代测序数据的纠错算法分析*

K - spectrum - based Analysis for Error Correction of Next Generation Sequencing

LAIDehuan1，CHEN Qingfeng1’2，HUANGLiyu3，LIANG Jiahai4

(1.广西大学计算机与电子信息学院，广西南宁530004;.广西大学亚热带农业生物资源保 护与利用国家重点实验室，广西南宁530004;.广西大学信息网络中心，广西南宁530004; 4.钦州学院电子与信息工程学院，广西钦州535000)

(1. School of Computer, Electronic and Information in Guangxi University,Nanning,Guan- gxi? 530004 ? China; 2. State Key Laboratory for Conservation and Utilization of Subtropical Agrc—bioresources，Guangxi University，Nanning，Guangxi，530004，China; 3. Information Network Center, Guangxi University? Nanning, Guangxi? 530004 ? China; 4. School of Elec­tronics and Information Engineering, Qinzhou University ? Qinzhou ? Guangxi 535000 ? China)

摘要：【目的】对现有的下一代测序（

赖德焕1，陈庆锋12**，黄丽宇3，梁家海4

NextGenerationSequencing，NGS)纠错算法和工具进行分析，提出基于

Hadoop平台的纠错算法，以解决大数据处理中计算机内存不足和运行时间长的问题，提升纠错性能。【方 法】使用特定的数据对现有的基于K-spectrum的纠错算法进行测试，对各纠错工具的运行时间、内存峰值和 纠错结果进行比较来衡量纠错工具的性能。在此基础上提出Hadoop分布式并行纠错算法（Paallel algo­rithm)， 并与串行程序、 Lighter 和 Racer 进行比较 ，分析分布式并行实现的可行性。【结果】现有的基于 K- spectrum的纠错工具普遍存在较大的内存消耗现象，其中Racer和Sga的纠错效果较好。而Hadoop分布式

并行纠错算法对计算机单机内存的消耗较低，当数据量超过一定值时，并行分布式程序的运算时间比串行单 机程序明显减少。【结论】本研究提出的Hadoop分布式并行纠错算法不仅降低了内存消耗，而且提高了运算 性能，更有利于大规模基因数据的分析处理。

关键词：NGS基因错误修正 Hadoop K-spectrum

中图分类号：

TP301. 6

文献标识码：

A

文章编号

：1002-7378(2017)01-000-05

Abstract ：暰 ObjectiveJThe existing Next Generation Sequencing (NGS) error correction algo­

rithms and tools are analyzed and summarized, and an error correction tool based on Hadoop platform is proposed to solve the problem of insufficient memory and long running time in large data processing.【Methods】The existingK-spectrum_based error correction algorithm is tested with the specific data? and the performance of the error correction ured by comparing the run time?peak memory and error correction result of each correction________________ tool. A new error correction algorithm is

designed by combining Hadoop parallel收稿日期=2016-12-20

作者简介：赖德焕（1993 —），男，硕士研究生，主要从事生物信 distributed program and the algorithm proposed

in this paper. A comparison is made between the 息学和数据挖掘研究。

*国家自然科学基金项目（61363025)和广西自然科学基金重 serial program，Lighter and Racer to analyze the

feasibility of distributed parallel program.【Re­点项目（013GXNSFDA019029)资助。

The existing error correction tools based * *通信作者：陈庆锋（1972 —），男，教授，主要从事数据挖掘 sults】

on K - spectrum method generally have large和生物信息学研究，E-mail: qingfeng@gxu. edu. cn。

softwa

广西科学院学报2017年2月第33卷第1期

memory footprint? in which Racer and Sga have better error correction effect. And Hadoop distributed parallel error correction algorithm shows lower memory consumption on single computer. When the data size exceeds a certain value ? comparing with the time of the serial single program，theparallel anddistributedcomputing time significantly reduces.【Conclu- sion】The parallel error correction programcombinedwith Hadoop improves thememory and operation performance of the NGS error correction program based on K_sgood for the analysis and processing of large scale gene data.Key words ： NGS, gene error correction, Hadoop, K-spectrum

〇引言

提出的一个纠错工具，因为Racer把序列存放到 hash表中，所以程序对数据处理占用内存较小且运 【研究意义】下一代测序（NextGenerationSe- quenCmg，NGS)[1]是第二代DNA测序技术，其主要 平台有 Illumina、Polonator、SOLiD 测序仪等。这 些平台都使用循环芯片的测序方法，对充满DNA 样本的芯片进行重复的DNA聚合酶反应和荧光序 列读取反应。与传统的测序方法相比，N G S具有高 通量、成本低、效率高的优点，但得到的序列通常包 含大量的错误，需要利用计算机对序列进行辅助修 正，其修正过程是先检测出序列中错误的碱基，然后 通过特定的算法对其进行修正。计算机纠错处理的 核心是设计一个好的纠错算法，以提高序列修正的 性能和质量。因此，本研究对现有的纠错工具进行 比较，给相关研究提供参考依据；设计与实现并行分 布式纠错算法，解决大规模基因数据分析处理中计 算机内存消耗大和运算时间长的问题。【前人研究 进展】目前的错误修正算法主要基于以下3种方法 实现[2—3]:通过进行K_mer[4]统计的基于K-spec- trum方法、基于后缀树的方法和基于MSA[5]的方 法。其中，基于K - spectrum方法的工具主要有 Sga[6]、Racer[7]、Musket[8]和 Lighter[9]等，基于后缀 树方法的工具主要有3只尺瓦匚[1。]、只丨丁6。[11]等，基于 MSA方法的工具主要有ECHO[12]、Co:ral[13]等。

基于K-spectrum的错误修正算法简单易懂，修 正效果较好，且易于在各种平台上实现。其中心思 想是首先把每个短序列划分为长度为&的K-mers， 然后将所有的K-mers进行排列并计数。当一个K- mer出现的次数达到一定的阈值N时，则认为该K- mer是ioZid的，否则认为该K-mer是非ioZid的， 即该序列含有错误碱基，接着用®

序列去修正含

有错误碱基的序列。基于K-spectrum方法的4种 主要纠错工具各具特点：Sga是2012年提出的一个 基因组装工具，同时使用FM-index和BWT算法对 序列进行压缩存储。其自带Map功能，淘汰了不能 匹配的数据，所以修正性能较好。Racer是2013年

行速度较快。Musket是一个专为Illumina测序产 生的序列进行纠错的工具，主要使用双端纠错、单端 推进和选举法进行纠错。Lighter通过采样算法获 得一系列尽可能与参考基因相似的K-mers，然后从 中找出属于•so/W的K-mers存放到Bloom filter。 Lighter通过对K-mers的采样处理加快了程序对 K- mers的统计操作，进而缩短程序的运行时间。 【本研究切入点】由于目前的纠错软件主要是在单机 上运行的，如要处理大规模的基因数据，则要求用高 性能计算机来实现。Had〇〇p[14]的HDFS系统可以 快速地访问存储在各计算节点的数据，非常适用于 开发处理海量数据集的应用程序，且HDFS系统具 有极高的容错性，用户可以将Hadoop部署在多台 性能一般的计算机集群上组成分布式系统，所以在 Hadoop上实现分布式并行纠错算法有利于解决数 据的存储和运算的优化问题，且在生物计算领域，越 来越多的问题已通过Hadoop平台得到解决，如基 因表达双聚类和重叠社区算法等。【拟解决的关键 问题】对现有基于K-spectrum的纠错工具进行比 较，找出性能较好的纠错工具，然后在借鉴前人的纠 错算法的基础上，在Hadoop平台上实现分布式并 行纠错算法，降低NGS错误修正算法对计算机内存 的消耗，提高其计算性能。

1基于

K-spectrum方法的常用纠错工具性

能分析

1.1 数据来源

本研究米用的实验数据Staphylococcus aureus (SA )、Rhodobacter sphaeroides ( RS)、Human Chromosome 14(HC14)、Bombus impatiens(BI)来 自 G AGE 网站（http : //gage. cbcb. umd. edu/data/ index, html),对应的参考基因组数据来自NCBI,实 验数据的大小依次为242 MB、436 MB、9. 6 GB、92 GB。

赖德焕等:基于K-spectrum的下一代测序数据的纠错算法分析9

12数据预处理

在进行实验前，首先需要删除含A、T、C、G以 外的其它任何字母的基因序列。本实验使用的基因 数据都是双链的，每一个基因数据都有两个Fatq 文件，一个对应序列的左链，一个对应序列的右链。 在处理一个文件的增删时，必须要同时对另一个文 件进行对应的增删操作，以保证序列是paired-end 的。接着便可使用纠错工具对序列进行纠错处理， 并用B W A工具把序列映射到参考基因组上，得到 每个序列在参考基因组上的起始位置。的运行时间和内存的性能是有效的。Sga在处理每 一个数据时，消耗的时间总是远远大于其他纠错工 具。但从实验结果上看，大多数的纠错工具都存在 内存占用大的问题。为了解决该问题，可以利用分 布式计算平台把普通的计算机有效地联合起来，对 大规模数据进行分布式并行处理。

1.3 Gain综合分析

通过对原序列、纠错工具生成的序列和参考基 因组中对应的碱基进行比对，对修正后原序列中错 误碱基的各种修改状态分别进行统计，其修改状态 包括修改正确、修改错误、没有进行修改。并利用统 计结果计算出衡量纠错工具性能的信息增益Gain。 Gain数据的计算公式如下：

其中：TP表示纠错工具改对的碱基个数，FP表示 纠错工具改错的碱基个数，FN表示纠错工具没有 对错误碱基进行修改的碱基个数。14性能分析结果

Gain综合分析结果如图1所示，Lighter对小 规模数据的错误修正效果较好，但在处理大规模数 据时效果较差。从总体上看，无论是在处理小规模 数据还是大规模数据上，Sga和Racer都表现出了 较好的修正效果。

图 2 和图 3 分别是 Lighter、Racer、Sga 和 Mis- ket处理SA、RS、HC14、BI数据时，计算机的内存 峰值和运行时间比较。由图2和图3分析可知，对 于相同的数据，Lighter对内存和运行时间的消耗较 少。说明Lighter采用的采样操作算法对提高程序

2

Hadoop分布式并行纠错算法

2.1 程序设计

本研究的Hadoop平台搭建在广西大学亚热带

农业生物资源保护与利用国家重点实验室生物信息 学团队的Openstack[15]平台上。其中，Openstack 平台搭建在5台曙光物理节点上，每个节点的主要 配置为6核处理器，32GB内存和300 GB硬盘。

程序的设计思想：把预处理后的文件只取基因 序列交给Hadoop的任务机制，Hadoop通过判断任 务的数据量大小来决定该任务需要分配多少个节点

进行处理。然后将每个节点的数据交给Map函数， Map函数并行地处理该文件，并将序列数据以<

>的形式输出，

中存放序列数据，

不赋值。文件读取完毕后，Map函数会调用 Correct函数进行纠错处理，其过程为程序按设定的

10广西科学院学报2017年2月第33卷第1期

K-mer长度，遍历所有的序列，分析每一步生成的 K-mer是否在Bloom Filter中，如果存在则说明此 K-mer是正确的，否则说明遍历到的碱基是错误的， 把错误的碱基用A、T、C、G进行遍历替换。定义一 个记录得分的变量score，如果替换碱基后的K-mer 在Bloom Filter中，则score加1。找到一个得分值 达到所检查K-mes数量的一半以上，且分值最大 的碱基进行替换，否则不进行修改。把数据放到 2. 2算法验证

为了验证基于Hadoop平台的分布式并行纠错

算法（Parallel algorithm )的可行性，本研究利用 SA、RS和HC14数据对程序进行测试，并与程序的 串行单机运行方式（Serial algorithm)、Lighter和 Racer做比较。其中本研究提出的算法的单机方式 运行在广西大学计算机与电子信息学院的惠普服务 器上，其配置为32核处理器， GB内存和1TB硬 盘。实验得到的运行时间比较情况如图4所示，内 Hadoop平台上进行纠错的伪代码如下：

protected text void mapCLongWString context) ritable key ..Text value, Con­

line = {

value. toStringO ;//从 HDFS 上读取一

行数据

String text. set( fixedfixed = corrector, correct(line) ;//修正序列)；

context. write(NullWritable. get()，text) ;//写人 HDFS}

public String correctC String seq) {

for (int i = k — 1； i < sequence, length； i+—+) { //

默认不修正首段

if ( laFilter stlsSolidO) { //判断序列是否在已构建的 Bloom 中

for DNA(int □i = 0； i Tfor + +jj fo )={ /curlndex 飊/ k + 1； j <= curlndex； j定义dex—kr(p =+ 0; 1 〜pK的长度为17

〈 k; p+ + ) { //截取 curln- (pcurlndex 间的if + j > = sequence. kmer

length) kmber[p] reak；

= sequence[p + j]；}

if (p〈 k) beak； //不能组成完整的 kmer

kmer[pos------] = DNA[i]；if (isExist (er //在km的pokms位置替换er) ) score +—DNA[i] + ； //如 kmer在已构建的Bloom Filter中得 分十1

}

}

//如所检查的kmes数量一半以上是soild的

则进行碱基替换

sequence[i] =DNA[rIndex] score > = checkCount /2 ?

： sequence[curlndex]；

暋}

}return newString(this, sequence) ；//返回修改后的

序列

}

存的比较情况如图5所示。

Fig. 4 Peak memory comparison of 4 algorithms

Fig. 5 Running time comparison of 4 algorithms

通过对不同程序在处理相同数据时的运行时间 和内存峰值进行比较，发现基于Hadoop平台的分 布式并行纠错程序在内存的消耗方面相比其它程序 少，且随实验数据规模的增大，其内存的变化非常平 稳。由于程序设计得还不够完善，所以在运行时间

上分布式算法的时间要比Lighter和Racer算法的 运行时间长。与算法的单机运行方式比较时，发现 当数据集小于RS时，单机运行方式较快，其主要原 因是分布式并行算法在进行MapReduce运算时消 耗的时间较多。但当数据集大于RS时，分布式并 行算法运行的时间比单机串行算法的运行时间减少

赖德焕等：基于Kspectum的下一代测序数据的纠错算法分析11

了72.5%。从整体上来看，Hadoop分布式并行纠 错算法能更有效地解决现有基于K-spectrum的 NGS错误修正算法对大规模基因数据处理时，在内 存和运行时间上的瓶颈问题。

3结论

基于K-spectrum的NGS错误修正算法直观易

懂、错误修正效果较好，但在处理规模较大的数据时 消耗大量内存。现有的基于K-spectrum的常用纠 错工具中，Sga和Racer的纠错效果较好，Lighter 的纠错效果较差，但Lighter的采样算法使数据存 []DIERINGER D,SCHLO TTERERER C. Microsatel­

lite analyser (MSA): A platform independent analysis tool for large microsatellite data sets[J]. Molecular E­cology Notes，2003,3(1) :167-169.[6] GONNELLA G，KURTZS. Readjoiner: A fast and

memory efficient string graph-based sequence assemb- ler[J]. Bmc Bioinformatics，2012，13:82.

[7] ILIE L，MOLNAR M. RACER: Rapid and accurate

correction of errors in reads[J]. Bioinformatics，2013， 29(19)=2490-2493.

[8] LIU Y C,SCHRODER J,SCHMIDT B. Musket：A

multistage k _mer spectrum-based error corrector for il- 储空间大大减少，降低了对计算机内存的需求。本 研究基于Hadoop的HDFS系统与MapReduce编 程模式，提出了 Hadoop分布式并行纠错算法，并与 其串行程序、Racer和Lighter进行比较，发现该算 法降低了对计算机单机的内存消耗，并在一定程度 上提高了纠错算法的运算性能，说明该算法是可 行的。

参考文献：

[]SHANKS M E,DOWNES S M,COPLEY R R,et al.

Next-generation sequencing (NGS) as a diagnostic tool for retinal degeneration reveals a much higher detection rate in early-onset disease[j]. European Journal of Hu­man Genetics,2013,21 (3) ：274-280.

[2] YANG X,CHOCKALINGAM S P，ALURU S. A sur­

vey of error-correction methods for next-generation se- quencing[j]. Briefings in Bioinformatics，2013，14 (1): 56-66.[]江育娥，黄伟，林劼.下一代测序纠错方法综述[J].北

京工业大学学报，2016,42(3) :377-386,

JIANG Y E, HUANG W» LIN J. Error correction in preprocessing of next-generation sequencing[J]. Jou-- nal of Beijing University of Technology, 2016 » 42 (3)：377-386.

[]CHOR B，HORN D，GOLDMAN N，et al Genomic

DNA k- mer spectra： Models and modalities [J]. Ge­nome Biology, 2009 »10 ： R108.

lumina sequence data[J]. Bioinformatics，2013,29(3): 308-315.

[9] LI S，FLOREA L，LANGMEAD B. Lighter: Fast and

memory- efficient sequencing error correction without countingJJ]. Genome Biology，2014，15(1) : Rl.

[10] SCHRODER J , SCHRODER H , PUGLISI S J , et al

SHREC：A short-read error correction method [J]. Bioinformatics,2009,25(17) ：2157-2163.[11] ILIE L,FAZAYELI F,ILIE S. HiTEC： Accurate er­

ror correction in high-throughput sequencing data[J]. Bioinformatics，2011，27(3) :295302.

[12] KAO W C,CHAN A H,SONG Y S. ECHO：A refer­

ence- free short- read error correction algorithm [ J]. Genome Research,2011,21(7) ：1181_1192.

[13] SALMELA L，SCHRODER J. Correcting errors in

short reads by multiple alignments [J ]. Bioinformat­ics, 2011, 27(11) ： 1455-1461.

[14] WHITE T,CUTTING D. Hadoop：The definitive

guide[J]. O^reilly Media Inc Gravenstein Highway

North,2010,215(11) ：

1-4.[15] CORRADI A,FANELLI M,FOSCHINI L. VM con­

solidation： A real case based on open stack cloud[J]. Future Generation Computer Systems^ 2014,32 ： 118_127.

(责任编辑：陆雁）