Page 21 - 《软件学报》2021年第11期

武优西 等:无重叠条件严格模式匹配的高效求解算法 3347

S1-S5
1400
1200
出 1000
现 800
600
数 400
200
0
P1 P2 P3 P4 P5 P6 P7 P8 P9
NetBack-rrtl 127 597 968 556 1196 1035 699 373 791
NetBack-rltr 127 597 968 556 1196 1035 699 373 791
NetBack-lltr 127 597 968 556 1196 1035 699 373 791
NetBack 127 597 968 556 1196 1035 699 373 791

Fig.10 Total number of occurrences of patterns P1~P9 on sequences S1~S5
图 10 模式 P1~P9 在序列 S1~S5 上的总出现数
Table 6 Total running time of patterns P1~P9 on sequences S1~S5
表 6 模式 P1~P9 在序列 S1~S5 上的总运行时间
运行时间(ms)
算法
P1 P2 P3 P4 P5 P6 P7 P8 P9
NetBack-rrtl 58.73 99.96 185.51 121.33 125.62 72.76 84.99 51.81 57.79
NetBack-rltr 59.02 99.71 186.27 120.78 125.74 73.46 86.11 52.26 58.89
NetBack-lltr 57.78 99.68 186.13 121.83 123.94 72.52 84.47 52.22 58.67
NetBack 58.34 100.28 184.73 121.32 123.85 72.79 84.26 51.8 57.38

4.4 在序列模式挖掘中的应用
为进一步说明本文算法的高效性,我们在 DNA 序列上进行了序列模式挖掘实验,具体数据见表 7.将使用
NetBack 算法计算支持度的挖掘算法 NOSEP-back 与文献[26]提出的不采用回溯策略的挖掘算法 NOSEP 算法
进行对比,预设最小支持度为 500,长度约束为[1,30],间隙约束为[0,5].图 11 为 NOSEP-back 算法和 NOSEP 算法
在序列 DNA1~DNA5 上频繁模式的个数,表 8 为这两种挖掘算法在序列 DNA1-DNA5 上的运行时间.
Table 7 Biological sequence fragment
表 7 生物序列片段
序号 来源 长度
DNA1 Homo Sapiens AL158070 6 000
DNA2 Homo Sapiens AL158070 8 000
DNA3 Homo Sapiens AL158070 10 000
DNA4 Homo Sapiens AL158070 12 000
DNA5 Homo Sapiens AL158070 14 000

DNA序列

300
频 250
繁 200
模 150
式
个 100
数 50
0
DNA1 DNA2 DNA3 DNA4 DNA5
NOSEP 14 36 82 175 274
NOSEP-back 14 36 82 175 274

Fig.11 Comparison of mining frequent patterns on sequences DNA1~DNA5
图 11 在序列 DNA1~DNA5 上挖掘频繁模式数量对比