Abstract: The next generation sequencing needs to be processed by cloud computing due to its large data volume, complex pipeline and high requirements of computing resources. Cloud computing approach necessitates that the sequencing data is uploaded to the cloud platform first. The randomness of the sequencing process results in great differences at the binary level even dealing with the same sample or two similar samples. Existing methods of deduplication do not effectively identify duplicate contents in such sequencing results. Uploading and storing these duplicate data not only consume network bandwidth, but also waste storage space. Aiming to the existing methods are based on the binary feature of file, not effectively use the similarity features of sequencing results, NPD（Near Probability Deduplication） method is proposed for massive high-throughput sequencing data oriented cloud platform. It uses SimHash to calculate the block fingerprints of sequence and quality information in FastQ file, and then the fingerprints are quickly detected by double cuckoo filter of client and cloud platform. At the final stage, the cloud platform uses approximate algorithm to near deduplicate fingerprints. Experimental results show that the NPD method can improve deduplication ratio, reduce network traffic, shorten data upload time, and support massive data processing, and has a good practical value.

Key words: high-throughput sequence data, data de-duplication, near de-duplication, cuckoo filter

摘要： 新一代测序因其数据量大、数据处理过程复杂、对计算资源要求高等特点，需要通过云计算进行处理。然而，云计算的处理方式要求先将测序数据上传到云平台中。但由于测序过程的随机性，使得同一样本的两次测序、两个相似样本分别测序后所产生的文件在二进制层面会有较大差别。目前已有的去重方法无法有效识别出这样的“重复”测序文件和测序结果中的“重复”内容。重复上传和存储这些重复数据，不仅消耗网络带宽，而且浪费存储空间。针对现存的重复数据删除方法仅仅基于文件的二进制特征，并未有效利用测序结果数据相似性特点的问题，提出一种面向云平台的海量高通量测序数据近似去重方法NPD（Near Probability Deduplication）。该方法对FastQ中的序列和质量信息，使用SimHash计算分块指纹，采用客户端与云平台双布谷过滤器（Cukoo Filter）对指纹值进行快速存在性检测，最后由云平台使用近似算法对指纹值近似去重。实验结果表明，NPD方法在保证高效的同时，大幅提升了去重率，进而减少了网络流量，缩短了数据上传时间，能够支撑海量数据处理，具有良好的实用价值。

关键词: 高通量测序, 重复数据删除, 近似去重, 布谷过滤器