(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210565096.0 (22)申请日 2022.05.23 (71)申请人 清华大学 地址 100084 北京市海淀区双清路3 0号清 华大学清华园北京 100084-82信箱 (72)发明人 刘洋　普艳红　 (74)专利代理 机构 北京路浩知识产权代理有限 公司 11002 专利代理师 张金玲 (51)Int.Cl. H04L 9/08(2006.01) G16B 20/00(2019.01) G06F 21/62(2013.01) (54)发明名称 基于多方安全计算的隐私保护序列NJ树构 建方法及系统 (57)摘要 本发明提供基于多方安全计算的隐私保护 序列NJ树构建方法及系统， 包括： 基于对齐的基 因序列， 第一参与方和第二参与方在明文条件下 计算距离矩阵中各自持有序列对应部分； 在第一 参与方和第二参与方计算完成后， 将计算结果通 过秘密共享协议将份额分享给对 方； 根据双方秘 密共享的结果， 第一参与方和第二参与方在原对 齐序列秘密共享条件下联合计算距离矩 阵中剩 余部分， 并通过秘密共享协议输出距离矩阵计算 份额给各方； 通过得到的距离矩阵计算结果， 在 双方只持有距离矩阵的份额矩阵条件下进行NJ 树构建。 本发明解决了现有 NJ树构建过程中容易 出现基因序列泄露的问题， 以实现在NJ树构建过 程中对基因序列的隐私保护。 权利要求书2页 说明书12页 附图2页 CN 115102693 A 2022.09.23 CN 115102693 A 1.基于多方安全计算的隐私保护序列NJ树构建方法， 其特 征在于， 包括： 基于对齐的基因序列， 第 一参与方和第二参与方在明文条件下计算距离矩阵中各自持 有序列对应部分； 在第一参与方和第二参与方计算完成后， 将计算结果通过秘密共享协议将份额分享给 对方； 根据双方秘密共享的结果， 第 一参与方和第二参与方在原对齐序列秘密共享条件下联 合计算距离矩阵中剩余部分， 并通过秘密共享协议输出距离矩阵计算份额给 各方； 通过得到的距离矩阵计算结果， 在双方只持有距离矩阵的份额矩阵条件下进行NJ树构 建。 2.根据权利要求1所述的基于多方安全计算的隐私保护序列NJ树构建方法， 其特征在 于， 所述基于对齐的基因序列， 第一参与方和第二参与方在明文条件下计算距离矩阵中各 自持有序列对应部分， 具体包括： 所述第一 参与方在明文条件下计算拥有的m条序列对应的距离矩阵的得分； 所述第二 参与方在明文条件下计算拥有的n条序列对应的距离矩阵的得分； 第一参与 方和第二参与 方单独计算完成后， 将计算结果通过秘密共享协议将份额发送 给对方。 3.根据权利要求1所述的基于多方安全计算的隐私保护序列NJ树构建方法， 其特征在 于， 所述在第一参与方和第二参与方计算完成后， 将计算结果通过秘密共享协议将份额分 享给对方， 具体包括： 在整数秘密共享过程中， 第一参与方生成第一随机数， 并将第一随机数发送给第二参 与方， 自己保留序列中扣除第一随机数的剩余部分； 第二参与方生成第二随机数， 并将第二随机数发送给第一参与方， 自 己保留序列中扣 除第二随机数的剩余部分。 4.根据权利要求1所述的基于多方安全计算的隐私保护序列NJ树构建方法， 其特征在 于， 所述根据双方秘密共享的结果， 第一参与方和第二参与方在原对齐序列秘密共享条件 下联合计算距离矩阵中剩余部分， 并通过秘密共享协议输出距离矩阵计算份额给各方， 具 体包括： 第一参与 方和第二参与 方联合计算距离矩阵中剩余部分后， 输出整体距离矩阵的秘密 份额给各方， 针对整体距离矩阵的结果中的每 个元素与215做乘积， 进行小数表示。 5.根据权利要求1所述的基于多方安全计算的隐私保护序列NJ树构建方法， 其特征在 于， 所述通过得到的距离矩阵计算结果， 在双方只 持有距离矩阵的份额矩阵条件下进行NJ 树构建， 具体包括： 双方在份额矩阵条件下计算横向差异矩阵， 将整体距离矩阵进行标准化处理即可得到 横向差异 矩阵， 且横向差异 矩阵计算结果 也通过秘密份额形式输出 给各方； 双方在只持有横向差异 矩阵份额条件下计算选取距离最小的两个节点； 将两个节点连接产生 新的节点， 并更新 新节点到其它未 连接节点的距离； 重复以上步骤， 双方在秘密共享条件下不断用新的节点连接合并原节点并更新距离， 只到所有节点均连接在一 起， 即完成NJ树构建。 6.根据权利要求5所述的基于多方安全计算的隐私保护序列NJ树构建方法， 其特征在权　利　要　求　书 1/2 页 2 CN 115102693 A 2于， 所述将两个节点连接 到新的节点上并更新距离 。 具体包括： 选取的节点 为f,g， f,g连接 到新的节点u上， 则f,g到新节点u距离计算公式为： δ(g， u)＝d(f， g) ‑δ(f， u)。 7.一种基于多方安全计算的隐私保护序列NJ树构建系统， 其特 征在于， 所述系统包括： 距离矩阵计算模块， 用于基于对齐的基因序列， 第一参与方和第二参与方在明文条件 下计算距离矩阵中各自持有序列对应部分； 分享模块， 用于在第一参与方和第二参与方计算完成后， 将计算结果通过秘密共享协 议将份额分享给对方； 联合计算模块， 根据双方秘密共享的结果， 第一参与方和第二参与方在原对齐序列秘 密共享条件下联合计算距离矩阵中剩余部 分， 并通过秘密 共享协议输出距离矩阵计算份额 给各方； NJ树构建模块， 通过得到的距离矩阵计算结果， 在双方只持有距离矩阵的份额矩阵条 件下进行NJ树构建。 8.一种电子设备， 包括存储器、 处理器及存储在所述存储器上并可在所述处理器上运 行的计算机程序， 其特征在于， 所述处理器执行所述程序时实现如权利要求1至6任一项所 述基于多方安全计算的隐私保护序列NJ树构建方法。 9.一种非暂态计算机可读存储介质， 其上存储有计算机程序， 其特征在于， 所述计算机 程序被处理器执行时实现如权利要求1至6任一项所述基于多方安全计算的隐私保护序列 NJ树构建方法。 10.一种计算机程序产品， 包括计算机程序， 其特征在于， 所述计算机程序被处理器执 行时实现如权利要求1至 6任一项所述基于多方安全计算的隐私保护序列NJ树构建方法。权　利　要　求　书 2/2 页 3 CN 115102693 A 3