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

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

径,进而丢失出现〈1,3,4,8〉.
第1层 1 4 6 7

第2层 3 5

第3层 4 6 7

第4层 8 9
Fig.2 NetTree of pattern P=a[0,1]t[0,1]a[1,3]g in sequence S=actataagg
图 2 模式 P=a[0,1]t[0,1]a[1,3]g 在序列 S=actataagg 上的网树
(2) 本文设计了具有回溯机制的最左孩子路径的求解算法,并理论证明了该算法的完备性.
在此基础上,进一步证明了除了该方法以外,还可以存在其他 3 种方式,并对这 4 种求解方式的解的特点进
行了分析.
2 问题定义及分析

2.1 问题定义

定义 1. 长度为 n 的序列串 S 可以表示为 S=s 1 s 2 …s i …s n (1≤i≤n),序列串 S 是一个有序的字母表,s i ∈Σ,Σ代
表一种符号集.
在 DNA 序列中,Σ为集合{A,C,G,T};而在音乐序列中,Σ是由数字构成的集合.
定义 2. 具有间隙约束的模式 P 可以表示为 P=p 1 [min 1 ,max 1 ]p 2 …[min j−1 ,max j−1 ]p j …[min m−1 ,max m−1 ]p m
(1<j≤m),其中,min j−1 和 max j−1 是给定的两个非负整数,分别指 p j−1 和 p j 之间可以通配的最小和最大间隙,这样的
间隙称为非负间隙.本文只考虑非负间隙下的模式匹配问题.
定义 3. 序列 S 中一组位置索引 L=〈l 1 ,l 2 ,…,l j ,…,l m 〉,其中,1≤l j ≤n,1<j≤m,并满足以下条件:
s = p ,
j l j
min j− 1 l − ≤ j l j− 1 − 1≤ max j− 1 ,
MinLen ≤ l −+ 1≤ Maxlen ,
l
1
m
则称 L 是模式 P 在序列 S 中满足间隙约束及长度约束的一个出现,其中,l m −l 1 +1 为出现的长度,而 MinLen 和
MaxLen 分别表示出现的最小长度和最大长度约束.长度约束可表示为 LEN=[MinLen,MaxLen].
例 4:假设序列串 S=aattatatt,模式串 P=a[0,1]t[0,1]a,MinLen=3,MaxLen=4.若不考虑长度约束,那么 P 中一共
有 4 个满足间隙约束的出现,分别为〈1,3,5〉,〈2,3,5〉,〈2,4,5〉,〈5,6,7〉.出现〈1,3,5〉的长度是 5,即 5−1+1=5.在长度约束
LEN 为[3,4]的情况下,5 不在这个区间内,因此该出现不满足长度约束.
定义 4. 给定模式 P 在序列 S 中的两个出现 L=〈l 1 ,l 2 ,…,l j ,…,l m 〉和 L′ = 〈 l′′ l′ l′ 〉 ,若对于所有的 j(1≤j≤
, ,..., ,...,l
1 2 j m
m)都满足 l ≠ l′ ,则称 L 和 L′是两个无重叠出现.
j j
定义 5. 假设出现 L=〈l 1 ,l 2 ,…,l j ,…,l m 〉是模式 P 在序列 S 上的一个出现,对于模式 P 在序列 S 上的其他出现
l′
表示为 L′ l′ 1 , ,..., ,...,l′ =〈 2 l′ j l′ m 〉 ,若对于任意的 j(1≤j≤m), l ≤ 恒成立,则称出现 L 为模式 P 在序列 S 上的最小出
j
j
现.同理可得最大出现的定义.
定义 6. 令集合 R 表示模式 P 在序列 S 中的所有出现,其出现数量用|R|表示.假设集合 C 是集合 R 的一个
子集,若集合 C 中任意两个出现均满足无重叠条件,则称集合 C 为一个无重叠出现集,其出现数量用|C|表示.若不
存在无重叠出现集 C′,使得|C′|>|C|成立,则称集合 C 为最大无重叠出现集.无重叠严格模式匹配问题是指寻找模
式 P 在序列 S 上的最大无重叠出现集 C,并计算|C|的值.
例 5:给定与例 4 相同的序列串与模式串,且 LEN=[3,4].模式 P 在序列 S 中满足间隙约束及长度约束的出现
有 3 个,即 R={〈2,3,5〉,〈2,4,5〉,〈5,6,7〉},|R|=3.根据定义 6 可知,最大的无重叠出现集 C={〈2,3,5〉,〈5,6,7〉}或 C={〈2,4,