(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210451340.0 (22)申请日 2022.04.26 (71)申请人 安徽农业大 学 地址 230000 安徽省合肥市蜀山区琥珀街 道长江西路13 0号安徽农业大 学 (72)发明人 徐淳　吴云志　乐毅　董梦龙　 马志宇　陈佳玲　 (74)专利代理 机构 安徽思沃达知识产权代理有 限公司 342 20 专利代理师 戴晓丹 (51)Int.Cl. G16B 40/00(2019.01) G06F 16/22(2019.01) G06F 16/2453(2019.01) G06F 16/2455(2019.01)G06F 16/2458(2019.01) (54)发明名称 基于携带缓存Trie树加速生物基因的检索 方法 (57)摘要 本发明公开了基于携带缓存Trie树加速生 物基因的检索方法， 属于数据查询技术领域， 该 检索方法具体步骤如下： (1)构建Tire树并将数 据导入Tire树中； (2)对Tire树进行性能优化； (3)对基因序列簇进行 缓存优化； (4)对T ire树查 询效率进行对比分析； 本发明通过构建Trie树与 哈希表结合的方式对各组生物基因数据进行查 询， 能够利用有限的内存空间加速基因索引的检 索。 权利要求书2页 说明书4页 附图1页 CN 114758727 A 2022.07.15 CN 114758727 A 1.基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 该检索方法具体步骤 如下： (1)构建Tire树并将数据导入Tire树中： 工作人员构建Tire树， 同时将生物基因数据导 入Tire树中进行存 储； (2)对Tire树进行性能优化： 将Tire树进行压缩处理， 同时生成一组索引表以对Tire树 在精准匹配时效率进行性能优化； (3)对基因序列簇进行缓存优化： 将生成的各组基因序列簇缓存至内存中， 同时通过 LRU算法对各组基因序列簇进行选择淘汰； (4)对Tire树查询效率进行对比分析： 收集并分析MySQL与Redis查询效率， 同时检测 Tire树查询效率， 并将收集到的三组查询效率进行对比分析。 2.根据权利要求1所述的基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 步骤(1)中所述Tire树构建具体步骤如下： 步骤一： 对各组生物基因数据的基因序列进行分析， 并提取 “MSTRG”和“CSS”两组标识； 步骤二： 创建Trie树根节点， 同时该根节点不包含字符， 依据分析结果将各组生物基因 数据的字符录入除根节点以外的每 个节点中， 同时每 个节点只包 含一个字符； 步骤三： 当工作人员查询某一组或多组生物基因数据时， 从根节点到某一节点， 路径上 经过的字符连接起来， 为该生物基因数据对应的字符串， 且每个节点的所有子节点包含的 字符都不相同。 3.根据权利要求1所述的基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 步骤(2)中所述 性能优化具体步骤如下： 第一步： 遍历Trie树各连续分支， 并将非根内部节点只有一个子节点进行标记， 并将该 节点视为冗余； 第二步： 将标记的各组长度为一的连续分支节点压缩为一串字符串， 并将其作为该 Trie树索引的单一分支节点， 同时存储空间从标准Trie树的O(n)降低到压缩后的O(k)， 其 中， n为Trie树中总字符串长度， k 为插入基因的最长 长度； 第三步： 在内存中构 建一张索引表， 在进行模糊查询时通过Trie树做索引查询， 进行精 确查找时查询索引表， 且所有基因索引表在内存中只会保存一份， Trie树与索引表最后指 向同一块内存地址 。 4.根据权利要求3所述的基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 第三步中所述索引表可替换为缓存表， 同时系统在Trie树上进行精准查询时， 将查询结果 缓存到缓存表中。 5.根据权利要求1所述的基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 步骤(4)中所述选择淘汰具体步骤如下： S1： 依据Trie树的LRU顺序， 通过LRU链表对各组启动链表头部进行进一步链接， 收集最 少查询的基因序列簇信息， 并将该基因序列簇的启动链表 安排在LRU链表的首位， 并依次进 行排序； S2： 在Trie树启动阶段跟踪访问信息前， 内存模块在Trie树启动之前清除所有更新页 表项的访问位， 若在Trie树启动期间访问了某个基因序列簇， 会将该基因序列簇添加到启 动链表中；权　利　要　求　书 1/2 页 2 CN 114758727 A 2S3： 在Trie树启动时间结束之前， 内存模块重新检查所有基因序列簇的访问位， 若在其 它阶段也访问某个基因序列簇， 则将该基因序列簇将从启动链表中删除， 并移到 常规LRU链 表中， 确定 完成后对启动链 表中的各组基因序列簇进行 数据更新； S4： 内存模块从LRU链表的头部选择最少查询的应用基因序列簇， 并将其淘汰， 同时缓 存中只保存那些高频查询的基因序列簇 。 6.根据权利要求1所述的基于携带缓存Trie树加速生物基因的检索方法， 其特征在于， 步骤(5)中所述对比分析 具体步骤如下： Q1： 分别给予MySQL、 Redis以及Trie树10个线程数， 并执行5次接口访问， 分别收集50个 样本数据； Q2： 分析各组样本数据， 在只提供5个及以下的关键字情况下， Trie的吞吐量比MySQL与 Redis高， 且当给 的关键字足够多， 能够筛选走一部分数据时， Trie最快能到达3 ×104/s吞 吐量； Q3： 将数据装到一台2核2G、 公网带宽1Mbps的机器中， 同时收集各组样本数据进行分 析； Q4： 依据分析结果， Redis作为内存数据库其性能大于MySQL类别的磁盘数据库， 而同样 将数据存放在内存中的Trie树， 其 性能远大于 MySQL与Redis。权　利　要　求　书 2/2 页 3 CN 114758727 A 3