·494· 北京科技大学芈报 2006年第5期 (25)free(N.poslist); 有频繁情节p.episodes及其支持计数p.support, (26)return root; 加入到频繁模式集FES中.(3~10)对频繁模式 算法说明：(1)~(2)初始化存放序列的空链， 集的每一模式p,以所有前缀为规则前件后缀为 将序列读入链表中，(3)~(4)初始化每个事件(1 规则后件生成事件预测规则，其信任度为情节力 -情节)的位置列表，扫描序列以建立每个1-情节 的支持度与前件情节g的支持度的比值.由于q 的位置列表集.(5)建立模式树根结点.(6)~ 为p的子情节，因此g的支持度不小于p的支持 (11)对所有出现次数大于最小支持度的事件：将 度，所以g必存在于频繁模式集FES中.travel- 该事件加入频繁1-情节集、将该事件添加为根结 frequent-epi_tree采用深度优先遍历频繁事件树 点的孩子结点、将结点加入待处理队列中，对出现 T,每一结点的情节由父结点的情节和本结点的 次数大于最小支持度的事件释放其位置列表集. 标签node.label串联得到， (12)~(13)若待处理队列不空，反复取出队头结 点N处理.(14)~(15)清空当前情节的后续事 4对并行和混合情节的处理方法 件集，清空每一频繁件的发生位置集，以记录结 算法同样适用于并行和混合情节频繁情节发 点N的后续事件的发生位置.（16)~(18)若当 现，只需在频繁情节树逐层构造过程中允许进行 前情节的后续事件为频繁事件、满足限制，若其位 并行情节扩充.例如设父结点对应的频繁情节为 置未出现在后续事件集中则添加.(19)~(20)对 (AB),需对(AB〉位置集中所有满足限制的后续 后续事件集的每一事件，将其发生位置添加到所 事件的组合进行扩充，设为(AB〉后续出现的满足 属事件类型的发生位置集中，(21)~(24)对当前 限制的事件有C,D,E,设允许的最大并行事件 情节N每一类型的后续事件，若其支持度大于最 为2，则其扩充为(ABC),〈ABD),〈ABE),〈AB 小支持度则创建N的孩子结点，加入该孩子结点 (CD)》,(A(DE)》,(A(CE)》,()表示其中件 到待处理队列中，(25)结点N处理完成后释放 先后顺序无限制.前三个为满足限制的串行扩 其发生位置列表，以减少内存占用， 充，后三个为满足限制的并行扩充，算法中可根据 通过遍历构建的频繁情节模式树可以生成事 发掘任务添加限制，如情节最大持续期等 件预测规则，算法描述如下， 算法2：事件预测规则生成算法 5实验结果 输人：频繁情节模式树T,最小支持数min- 实验目的主要是将本文GSTA算法与基于 supp,最小信任度minconf,序列总长度len. 候选生成的(Aprior-like)的频繁情节发现算法进 输出：预测规则集ruleset. 行比较，以检验其优越性，算法采用VC++6.0 (1)FES=NULL; 实现，运行环境为plII800,256M内存，win2000 (2)FES travel-frequent-epi-tree (T, 平台.实验数据采用Geneva大学ExPASy(Ex- currentpatterr='); pert Protein Analysis System)服务器上的 (3)for each p∈FES PROSITE数据库(http:∥www.expasy.org/ (4)for i=1 to length(p)-1 prosite/index,html)中的表达蛋白序列， (5)generate rule R.rule=p[1..i ]p[i+ PROSITE包含具有生物学意义的DNA和表达 1..length(p)] 蛋白模式，主要用于识别蛋白质序列所属类别. (6)find episodes g in FES such that g.pat- 因为数据集中的模式是已知的，所以实验目的主 tern=p[1..i] 要是对比验证该算法的有效性和优越性.选择 (7)R.supp=p.supp/(len/length(p)); DNA失配修复蛋白(DNA mismatch repair pro- (8)R.conf=p.supp/q.supp teins1,PROSITE entry PS00058)的79个序列组 (9）ifR.supp≥min-supp and R.conf≥ 合并视为一个件序列，将其空间顺序视为时间， min-conf then 在不同序列之间放置结束符$以避免情节跨越不 (10)add R to ruleset; 同序列.序列的总长度为53130，包含20种不同 (11)return ruleset; 事件类型，失配修复蛋白的特征模式为 算法2说明：(1)初始化频繁情节集合FES GFRGEAL.以下对本文提出的GST-based算法 为空.(2)调用travel-.frequent-epi-tree得到所 进行有效性和可伸缩性实验，并与Apriori-like算. 4 9 4 . 北 京 科 技 大 学 学 报 20 0 ` 年第 s 期 ( 2 5 ) f r e e ( N . p o s li s t ) ; ( 2 6 ) er t u rn or t ; 算法说 明 : ( l) 一 ( )2 初始化存放序列 的空链 , 将序列 读入链 表中 . ( 3) 一 ( 4) 初始化每个 事件 ( 1 一情节 )的位置 列表 , 扫描序列 以建立 每个 1一情节 的位置 列表 集 . ( 5) 建立 模式树根结点 . ( 6) 一 ( 1 1) 对所有出现 次数大于 最小支持度的事件 : 将 该事件加入频繁 1一情节集 、 将该事件添 加 为根结 点的孩 子结点 、 将结点加入待处理 队列 中 , 对出现 次数大于最小支持度的事件释 放其位置 列 表集 . ( 12 ) 一 ( 1 3 )若待处 理 队列不 空 , 反 复取 出队头 结 点 N 处 理 . ( 1 4 ) 一 ( 1 5) 清空 当前情节 的后 续事 件集 , 清空每一频 繁事件的发生位置 集 , 以记录 结 点 N 的后 续事件的发 生 位置 . ( 16) 一 ( 18) 若当 前情节的后续 事件为频 繁事件 、 满足限制 , 若其位 置未出现 在后续事件集中则添加 . ( 19) 一 ( 2 0 )对 后续事件集的每一 事件 , 将其发生 位置 添加到 所 属事件类型的发生 位置集中 . ( 21 ) 一 ( 2 4 )对 当前 情节 N 每一 类型 的后续事件 , 若其支持度大于最 小支持度则 创建 N 的孩子结点 , 加入该 孩 子结点 到待处理 队列 中 . ( 2 5) 结点 N 处 理 完成后 释 放 其发 生 位置列 表 , 以减少 内存占用 . 通过 遍历 构建的频 繁情节模式树可以生成事 件预 测规 则 , 算法描述如 下 . 算法 2 : 事件预测规 则 生成算法 . 翰人 : 频繁情节模式树 T , 最小支持 数 m i n - s u p p , 最小信任度 m i n co n f , 序列总长 度 l e n . 输出 : 预测规则 集 ur les et . ( l ) F E S = N U I J L ; ( 2 ) F E S = t r a v e l 一 f r e q u e n t 一 e p i 一 t er e ( T , e u r r e nt p a t t e r r = ` ’ ) ; ( 3 ) fo r e a e h P e F E S ( 4 ) fo r i = 1 t o l e n g t h ( p ) 一 l ( 5 ) g e n e r a t e r u l e R . r u l e = P [ 1 二 i ]” P [ i + l 二 l e n g t h ( P ) ] ( 6 ) fi n d e p iso d e s 9 i n F E S s u e h t h a t 9 . p a t - t e r n = P [ 1 二 i ] ( 7 ) R . s u p p = P . s u p p / ( l e n / l e n g t h ( P ) ) ; ( 8 ) R . co n f = p . s u p p / q . s u p p ( 9 ) i f R . s u p p 妻 m i n 一 s u p p a n d R . e o n f ) m i n _ e o n f t h e n 10 ) a d d R t o r u l e s e t ; 1 1 ) r e t u r n r u l e s e t : 算法 2 说 明 : ( l) 初 始化频 繁情节 集 合 FE S 为空 . ( 2 ) 调 用 t r a v e l 一 f r e q u e n t 一 e p i 一 t r e e 得 到 所 有频 繁情节 p . eP i sod es 及 其支持计数 P . s 叩op rt, 加入 到频 繁模式集 F E S 中 . ( 3一 1 0) 对 频 繁模式 集的每一 模式 P , 以所有前缀 为规 则前件后缀 为 规则后 件生成事件预测 规 则 , 其信任度 为情节 P 的支持度与前件情节 q 的支持度的比值 . 由于 q 为 P 的子情节 , 因此 q 的支持度不小于 P 的支持 度 , 所以 q 必 存在于频繁模式集 F E s 中 . t ar ve ! - fr eq ue nt 一 e iP 一 tr e e 采用深 度优先遍 历频繁事件树 T , 每一结点的情节由父结点的情节和 本结点的 标签 n o d e . lab el 串联得 到 . 4 对并行和混合情节的处理方法 算法 同样适 用于 并行和混合情节频 繁情节发 现 , 只需在频繁情节树逐 层 构造 过 程 中允 许进 行 并行情节扩充 . 例如设 父结点对应 的频 繁情节为 <A B > , 需对 <A B >位置 集中所有满足 限制的后 续 事件的组 合进行扩充 , 设为 <A B >后续出现的满足 限制的事件有 C , D , E , 设 允许的最大并行 事件 为 2 , 则其扩 充 为 <A B C > , <A B D > , <A B E > , ( A B ( C D ) ) , <A ( D E ) > , <A ( CE ) > , ( )表示 其 中 事件 先后 顺序无 限 制 . 前三 个 为满 足 限制的 串行扩 充 , 后 三个为满足限制的并行扩充 , 算法 中可根据 发掘 任务 添加 限制 , 如情节最 大持续期等 . 5 实验结果 实验 目的 主要 是 将本文 G S T A 算法与基 于 候选生成的 ( A rP i or 一 h k e ) 的频 繁情节发现 算法进 行比较 , 以检验其优越性 , 算法 采用 v C + + 6 . 0 实现 , 运 行环 境为 p l l l 8 0 0 , 2 5 6 M 内 存 , w in2 0 OO 平台 . 实验 数据采用 G e n e v a 大学 E x P A s y ( E x - p e r t p or t e i n A n a l y s i s S y s t e m ) 服 务 器 上 的 P R OS IT E 数 据 库 ( h t t p : / w w w . e x p a s y . o r g / p or s i t以i n d e x . h t m l ) 中 的 表 达 蛋 白 序 列 , P R O SI T E 包含具 有 生 物 学 意 义 的 D N A 和 表达 蛋 白模式 , 主要 用于 识别蛋 白质序列 所 属 类别 . 因为数据集中的模式是 已知的 , 所以 实验 目的主 要 是 对 比验证 该算法 的有效性 和优越 性 . 选 择 D N A 失配 修复蛋 白 ( D N A m i s m a t e h r e p a i r p or - t e i n s l , P R ( )S I T E e n t r y P印0 0 5 8 )的 7 9 个序列组 合并视为一 个 事件序列 , 将其空间顺序视 为时 间 . 在不 同序列之 间放置结束符班 以避 免情节跨越 不 同序列 . 序列的总长度为 5 3 13 0 , 包 含 20 种不 同 事 件 类 型 , 失 配 修 复 蛋 白 的 特 征 模 式 为 G F R G E A L . 以 下对 本 文 提 出 的 G S T 一 bas ed 算法 进行有效性和 可伸缩性实验 , 并与 A rP i or i 一 ilk e 算