面向大规模序列同源问题的并行分布式算法及其关键技术研究

Both the sequencing sequences alignment and the code clone detection search for some ancestral or original fragments of sequences, called them as the sequence homology problems, which many such problems are existed in academia and industry. There are 1000 genomes data in 50TB+ and code lines of large software 50,000,000 lines or more. For this scale of data, the sequence data organization, parallel and distributed algorithms and architecture have become a serious challenge. We will associate research on two independent development problems at the level of sequence homology, in order to find the cross-referenced technologies and methods and propose the new concepts and new approaches at a high level. This project is planned to take the indexing, compression and feature extraction and other key technologies innovation as the basis, the design and optimization of whole process in the problem-specific parallel and distributed algorithms as the main line, and apply the parallel enabling technologies and the large-scale computational modes to enhance the solving ability. Our innovations are reflected in as follows. (1) Build the rapid code clone detection approach using the dynamic indexing and compression, based on the indexing and compression technologies in sequencing sequences alignment. (2) Create the fast sequencing sequences alignment approach using the loss compression, base on the feature extraction technologies in code clone detection. (3) Design the index structure of time and space balance using combination Hash and BWT, in order to the variety of different parallel distributed computing architectures with limited storage.

测序序列比对和代码克隆检测都是寻找一些序列片段的祖先或原版片段，我们称之为序列同源问题，学术界和工业界存在许多这样的问题和应用。像千人基因组数据在50TB以上、大型软件代码都在5000行以上，如此规模的序列数据组织、并行分布式算法与体系结构成为了严峻的挑战。我们对两个独立发展的问题在序列同源层面上进行关联研究，挖掘可借鉴的技术和方法，进而在更高层面上提出新概念和新方法。本项目将以索引、压缩和特征提取等关键技术创新为基础，面向问题的并行分布式算法全过程设计和优化为主线，应用并行分布使能技术和大规模计算模式进一步提升求解能力。创新和突破体现在：(1)借鉴序列比对中的索引和压缩技术，创建基于动态索引和压缩的代码克隆检测快速方法；(2)参考代码克隆中的特征提取技术，创建基于有损压缩的测序序列比对快速方法；(3)设计融合Hash和BWT一体的时空平衡索引结构，适应各种存储受限的并行分布式体系结构。

测序序列比对和代码克隆检测都是寻找一些序列片段的祖先或原版片段，我们称之为序列同源问题，学术界和工业界存在许多这样的问题和应用。我们对两个独立发展的问题在序列同源层面上进行关联研究，挖掘可借鉴的技术和方法，进而在更高层面上提出新概念和新方法。项目以索引关键技术为基础，适配数据组织的算法设计和优化为主线，大规模并行计算技术提升求解能力。项目围绕五项研究内容展开：同源问题共性分析、索引和检索方法、高效适配算法设计、并行加速和优化、差异克隆代码方法成果转化，其中最后一项内容为项目执行期新增加的。. 取得的主要成果和创新：(1)新一代索引技术创新和优化。发展了一种定长Hash索引的变长查询方法，优化了FM-Index的counting计算过程，提升效果显著。相关工作发表在生物信息学重要期刊Bioinformatics和TCBB上。(2)发展了面向差异代码克隆的两类高效检测方法。借鉴测序序列比对中“locate-filter-verify”大数据方法，提出了token类差异代码克隆检测的CCAligner新方法；借鉴近似图核匹配方法，提出了PDG（程序关联图）类差异代码克隆检测的CCGraph快速方法。相关工作发表在软件工程顶会ICSE和ASE上。(3)开展差异克隆检测方法的成果转化。2019年10月份与华为技术有限公司签订一项“大范围、高精度软件克隆检测及度量计算合作项目”的技术开发合同，该工作已于2020年底结题并通过验收。token类克隆检测工具CCAligner2.0对于千万行代码仓实现分钟级时间检测，单个程序片段实现秒级时间检测，整个软件系统得到用户满意和认可。. 差异代码克隆检测相关成果在软件开发和分析中具有广泛的应用前景，在项目执行期间不仅华为公司和我们密切合作，京东集团开发团队也多次询问和咨询了我们的CCAligner工具，现在我们和华为公司正在将差异代码克隆检测软件系统做开源的前期准备工作。