利索能及
我要发布
收藏
专利号: 2025105253955
申请人: 烟台大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-07-01
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于syncmer的基因组双序列比对方法,其特征在于,包括:

S1:获取目标序列和查询序列,利用syncmer策略分别提取目标序列和查询序列的子序列,若两个相邻子序列的间距大于间距阈值,则在两个相邻子序列区间插入至少一个子序列,使得两个相邻子序列的间距不大于间距阈值,得到目标序列的子序列、查询序列的子序列;

基于目标序列的子序列、查询序列的子序列,分别构建哈希索引后,得到目标序列索引、查询序列索引;

S2:根据目标序列索引、查询序列索引,查询序列的每个子序列,在目标序列中进行匹配,将匹配的两个子序列记为匹配锚点;基于匹配锚点分别对查询序列、目标序列进行区间划分,得到目标序列的比对区间、查询序列的比对区间;

根据两个相邻比对区间的间距、比对区间的长度或比对区间之间的重叠情况,分别对目标序列的比对区间、查询序列的比对区间进行优化,得到相应的优化比对区间;

S3:每个优化比对区间经双序列比对算法处理,得到局部最优比对路径;根据匹配锚点位置,将相邻优化比对区间的局部最优比对路径进行拼接,生成比对结果。

2.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S2,根据两个相邻比对区间的间距、比对区间的长度或比对区间之间的重叠情况,分别对目标序列的比对区间、查询序列的比对区间进行优化,得到相应的优化比对区间,具体为:对于目标序列或查询序列,若两个相邻比对区间的间距小于预设阈值,则将两个相邻比对区间进行合并,得到相应的优化比对区间;其中,预设阈值为根据待优化比对区间的序列特征进行设置;

若比对区间的长度小于预设长度,则将该比对区间与相邻比对区间进行合并,得到相应的优化比对区间;

若比对区间之间存在重叠,则将存在重叠的比对区间进行合并,得到相应的优化比对区间。

3.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S3,根据匹配锚点位置,将相邻优化比对区间的局部最优比对路径进行拼接,生成比对结果,具体为:根据匹配锚点位置,若相邻优化比对区间的局部最优比对路径在目标序列和查询序列上的偏移量相同,则将相邻优化比对区间的局部最优比对路径合并为一条连续比对路径;

若相邻优化比对区间的局部最优比对路径存在重叠或矛盾,则采用动态规划回溯策略,基于局部最优比对路径的权重,生成全局最优路径;

对所有匹配锚点位置对应的相邻优化比对区间的局部最优比对路径拼接完毕,生成比对结果。

4.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S2,基于匹配锚点分别对查询序列、目标序列进行区间划分,得到目标序列的比对区间、查询序列的比对区间,具体为:对查询序列、目标序列的匹配锚点分别进行排序,以两个相邻锚点为边界,划分查询序列或目标序列后,以两个相邻锚点中前者的终止位置为查询序列或目标序列的起始位置,以两个相邻锚点中后者的起始位置为查询序列或目标序列的终止位置,得到目标序列的比对区间、查询序列的比对区间。

5.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S2,根据目标序列索引、查询序列索引,查询序列的每个子序列,在目标序列中进行匹配,将匹配成功的两个子序列记为匹配锚点,具体为:以查询序列的子序列的碱基序列为键,在目标序列的哈希索引中进行查找,若查找到匹配的子序列,则将匹配成功的两个子序列记为匹配锚点,并记录该子序列的碱基序列、该子序列在目标序列中的位置和该子序列在查询序列中的位置。

6.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S1,利用syncmer分别提取目标序列和查询序列的子序列,具体为:在包含多个k‑mer的滑动窗口内选择一个k‑mer,若s‑mer在该k‑mer的起始位置或末端位置,则将该k‑mer视为一个子序列;当前窗口继续滑动,提取子序列,直至将目标序列和查询序列的子序列提取完毕。

7.根据权利要求1所述的基于syncmer的基因组双序列比对方法,其特征在于,所述S1,基于目标序列的子序列、查询序列的子序列,分别构建哈希索引,为以目标序列的子序列的碱基序列为哈希表的键,以目标序列的子序列在目标序列中出现的位置为哈希表的值;

以查询序列的子序列的碱基序列为哈希表的键,以查询序列的子序列在查询序列中出现的位置为哈希表的值。

8.根据权利要求3所述的基于syncmer的基因组双序列比对方法,其特征在于,所述比对结果,包括全局比对得分、全局比对路径、比对区间、匹配碱基数、错配碱基数、插入或缺失碱基数。

9.一种基于syncmer的基因组双序列比对系统,其特征在于,包括:

索引构建模块:用于获取目标序列和查询序列,利用syncmer策略分别提取目标序列和查询序列的子序列,若两个相邻子序列的间距大于间距阈值,则在两个相邻子序列区间插入至少一个子序列,使得两个相邻子序列的间距不大于间距阈值,得到目标序列的子序列、查询序列的子序列;

基于目标序列的子序列、查询序列的子序列,分别构建哈希索引后,得到目标序列索引、查询序列索引;

比对区间优化模块:根据目标序列索引、查询序列索引,查询序列的每个子序列,在目标序列中进行匹配,将匹配的两个子序列记为匹配锚点;基于匹配锚点分别对查询序列、目标序列进行区间划分,得到目标序列的比对区间、查询序列的比对区间;

根据两个相邻比对区间的间距、比对区间的长度或比对区间之间的重叠情况,分别对目标序列的比对区间、查询序列的比对区间进行优化,得到相应的优化比对区间;

比对结果生成模块:每个优化比对区间经双序列比对算法处理,得到局部最优比对路径;根据匹配锚点位置,将相邻优化比对区间的局部最优比对路径进行拼接,生成比对结果。