计算机应用

作者：李功丽, 李钰, 张恩, 尹天宇

单位：1. 河南师范大学 计算机与信息工程学院, 河南 新乡 453007;2. "智慧商务与物联网技术" 河南省工程实验室(河南师范大学), 河南 新乡 453007

关键词：基因比对,相似度计算,隐私保护,不经意随机存取,混淆电路

基金：国家自然科学基金资助项目（U1604156，61772176，61602158）；河南省科技攻关计划项目（172102210045，192102210131）。

针对当前的基因序列比对协议普遍要求一个可信赖的第三方，可能因此造成大范围的隐私数据泄漏的问题，提出了一种基于线性扫描的基因比对方案。首先对两方的基因序列进行基于混淆电路（GC）的编码，然后线性扫描整个基因组数据库并用混淆电路实现客户的基因序列与库中所有基因序列的比对。上述方案可以在保护双方用户隐私的前提下，实现基因比对。不过该方案需要扫描整个基因组数据库，时间复杂度为O（n），在基因组数据库较大时效率较低。为了提高基因比对的效率，进一步提出了基于不经意随机存取（ORAM）的基因比对方案，先将基因数据存储在ORAM上，然后只需把目标路径上的数据项取出并用混淆电路进行基因比对。该方案的比对次数和数据库的大小呈亚线性关系，时间复杂度为O（log n）。实验结果表明，基于ORAM的基因比对方案在实现隐私保护的同时，把比对次数由O（n）减小到了O（log n），明显降低了比对操作的时间复杂度，可以用来进行疾病诊断，尤其适用于基因组数据库较大的场景。

来源：2020年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2020年第1期