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

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

(1,1) (3,3) (7,7) (9,9) (12,12) (16,16)
1 3 7 9 12 16
(7,7) (7,9) (12,12) (12,12) (16,16) (16,16)

(1,1) (1,3) (3,3) (7,9) (12,12) (12,12)
2 4 6 10 13 14
(7,7) (7,7) (9,9) (12,12) (16,16) (16,16)

(1,3) (3,3) (7,9) (12,12)
5 8 11 15
(7,7) (9,9) (12,12) (16,16)

(1,3) (3,3) (7,9) (12,12)
7 9 12 16
(7,7) (9,9) (12,12) (16,16)
Fig.8 Rightmost child path
图 8 最右孩子路径
综上,只要采用最大策略,无论是最右孩子路径方式还是最右双亲路径方式,均能得到无重叠最大出现集.

4 实验结果与分析

4.1 实验环境与数据
本文采用的真实生物数据为测试序列可以从美国国家生物计算信息中心下载(http://www.ncbi.nlm.nih.
gov/-genomes/FLU/SwineFlu.html),具体数据见表 3,S1~S8 为测试序列,表 4 给出了实验所需的 9 种模式串.
实验运行的环境为:Intel(R)Core(TM)i5-7200U 处理器,主频 2.50GHZ,内存 8GB,Windows 7,64 位操作系统
的计算机.程序开发环境为 VC++6.0.

Table 3 Real biological sequence
表 3 真实生物序列

序号 来源 长度
S1 Homo Sapiens CY058563 2 286
S2 Homo Sapiens CY058562 2 299
S3 Homo Sapiens CY058561 2 169
S4 Homo Sapiens CY058556 1 720
S5 Homo Sapiens CY058559 1 516
S6 Homo Sapiens CY058558 1 418
S7 Homo Sapiens AX829178 5 393
S8 Homo Sapiens AX829174 10 011

Table 4 Patterns
表 4 模式串
序号 模式串 长度约束
P1 a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a[0,3]t[0,3]a [5,49]
P2 g[1,5]t[0,6]a[2,7]g[3,9]t[2,5]a[4,9]g[1,8]t[2,9]a [7,65]
P3 g[1,9]t[1,9]a[1,9]g[1,9]t[1,9]a[1,9]g[1,9]t[1,9]a[1,9]g[1,9]t [10,101]
P4 g[1,5]t[0,6]a[2,7]g[3,9]t[2,5]a[4,9]g[1,8]t[2,9]a[1,9]g[1,9]t [8,96]
P5 a[0,10]a[0,10]t[0,10]c[0,10]g[0,10]g [6,56]
P6 a[0,5]t[0,7]c[0,9]g[0,11]g [5,37]
P7 a[0,5]t[0,7]c[0,6]g[0,8]t[0,7]c[0,9]g [7,49]
P8 a[5,6]c[4,7]g[3,8]t[2,8]a[1,7]c[0,9]g [22,52]
P9 c[0,5]t[0,5]g[0,5]a[0,5]a [5,25]

4.2 对比算法简介
为了测试本文 NetBack 算法的求解质量与效率,与 4 种已有的算法进行对比:INSGrow [22] 、NETLAP-
Nonpruning [25] 、NETLAP-Best [25] 和 NETGap [26] .这 4 种算法概要说明如下.