一种新的生物序列模式挖掘算法

一种新的生物序列模式挖掘算法

作者：常磊玲,朱春鹤

来源：《电脑知识与技术》2010年第19期

摘要:针对传统模式挖掘方法挖掘生物序列会生成大量不必要的短而且无用的模式,导致效率降低,在多支持度思想的基础上提出了基于邻近频繁模式段的模式挖掘算法JBioPM。首先,产生邻近短频繁模式段,然后组合这些短频繁模式段,产生新的长频繁模式。通过实验分析, 该方法在相似性很强的序列数据库中比BioPM 算法效率高。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。

关键词:相邻频繁模式段;模式组合;生物序列;模式挖掘;数据挖掘;生物信息学 中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)19-5140-03 Mining Algorithm for Biological Sequence Pattern CHANG Lei-ling, ZHU Chun-he

(Information Engineering College,Shanghai Maritime University,Shanghai 200135,China) Abstract:Traditional algorithms face efficiency problem because of generating a huge number of unnecessary and useless short pattern in the process of mining.To attack these problems,a novel mining algorithm called JBioPM (Joined Biology sequence Pattern Mining)is presented based on joined frequent pattern segment approach and multi-supports ideology,First, the joined short frequent pattern segments are produced.Then, longer frequent patterns can be obtained by combining the above segments.The experiment shows JBioPM has better performance than BioPM.Through dealing with the real protein family database, it is proved that the algorithm can deal with biology sequence data efficiently.

Key words: joined frequent pattern segment; pattern combination; biological sequence; pattern mining; data mining; bioinformatics

生物信息学[1]是一门综合运用生物学、计算机科学和数学等方法研究生物数据中所包含生物学意义的新型交叉学科,对生物序列分析如何快速而高效地挖掘生物序列中的序列模式已十分重要。通过多年来的不断努力,已经提出了很多发现模式的算法。但由于序列数据的快速增长,这些方法大多面临效率问题。基于前缀投影数据库的BioPM算[2]提出多支持度的概念,该算法克服了传统算法的缺点,在性能和效率方面有明显改善。然而,由于生物序列匹配的模糊性,使得这些算法都会在挖掘过程中产生无用模式,因此,算法效率有待提高。

由于生物序列的特殊性,导致生物序列模式的匹配一般都是模糊匹配,即生物序列可能包含任意长度间隔的具有约束限制的生物序列模式,现有的一些带有约束的序列模式挖掘算法没有

龙源期刊网 http://www.qikan.com.cn

考虑生物序列模式的各种约束特征。2004年Wang等人根据生物序列的特点,提出了一种有效挖掘包含任意长度间隔生物序列模式的两阶段(Two-Phase)算法。

本文提出一种新算法JBioPM(Joined Biology sequence Pattern Mining),在基于多支持度挖掘的基础上引入两阶段算法的部分思想,从而相比于传统模式挖掘算法挖掘的效率得到大大提高,同时也产生了更加有用的模式。经过一系列实验表明,JBioPM算法的性能明显高于其他相关算法。

1 相关工作

为更高效地挖掘具有生物意义的频繁序列模式,文献2引入多支持度思想,提出了基于前缀投影数据库的BioPM算法。以下为其相关定义:

定义1 生物序列:其可看作一串定义在有限字符集∑上的数量为r的字符串。 对于DNA序列, ∑={A,C,G,T},对于蛋白质序列,∑={A,C,D,E,F,G,H,I,K,L,M,N,P,Q,S,T,V,W,Y}

一条生物序列记作S,由M条生物序列构成的有限序列集记为D,则D={S1,S2,…,SM}。 定义2 局部支持度:给定序列集D,在D的某一序列S中子序列T出现的次数称为局部支持度。子序列T的局部支持度是S中包含子序列T的数目,记为loc_supD(T)。

定义3 分布支持度:给定序列集D,在D中包含子序列T的序列数称为分布支持度。子序列T的分布支持度是D中包含子序列T的数目,记为dis_supD(T)。

在引入了多支持度思想之后,BioPM算法就能满足多种挖掘需求,其中包括保守序列模式的挖掘、重复序列模式的挖掘及两者结合的挖掘。同时,由于BioPM算法是基于前缀投影数据库的原理,因此不用多次重复扫描序列数据库,还不会产生大量候选序列模式,为了控制模式增长,还设置了一个窗口值W来进一步提高算法的性能和效率。 以下为BioPM算法的过程:

1)对于D中的每一条序列S,寻找长度满足最小局部支持度阈值min_sup2的频繁项组成频繁项集PF。

2)对于PF中每一个频繁项P做长度为W的投影,构建投影数据库M,调用FindFreSegs(ref AryH,D,min_sup2,prefix,W,s);

3)将序列S中得到的频繁项,存入ArrayList型数组MAry的MAry[i]中。

龙源期刊网 http://www.qikan.com.cn

4)对于MAry数组中的每一个频繁项,如果满足分布支持度min_sup1,则将其加入ArrayList型元素FinalAry

FindFreSegs(ref AryH,D,min_sup2,prefix,W,s),其步骤如下:

1)在序列集D中按照prefixspan方法找出满足支持度s2的频繁的前缀存入ArrayList型prefixAry。

2)对于prefixAry中每一个频繁项P,如果P的长度为W,则将P存入AryH中,否则就以prefix+p作为前缀,在原始序列originS上再作长度为W的投影,构建投影数据库N,然后再递归调用FindFreSegs(ref AryH,D,min_sup2,prefix,W,s);

从算法的流程中可以看出,BioPM算法在寻找频繁项都用的是精确匹配,这样可能会生很多短而无用的序列序列模式,事实上,很多生物序列的匹配大多都是模糊匹配,太短的精确匹配模式对生物序列很可能没有意义,根据以上分析,本文提出了JBioPM算法,该算法能够进行模糊匹配,找到更有生物意义的长的蛋白质序列,提高了算法性能,并且避免了产生大量没有生物意义的短模式。

2 JBioPM算法

JBioPM算法在对BioPM算法改进的同时,也采取了其多支持度的优良思想,使JBioPM算法也可以进行多种序列挖掘。 2.1 JBioPM算法原理[3]

一条序列由若干个不包含间隔的短序列组成,即X1*X2*X3*…*Xn (n≥2),其中Xi是不包含任何的空位或间隔的连续的序列,*则代表空位或若干个字符。如果某模式和某序列相匹配,只要该序列中同时存在各个段(X1,X2…Xn)即可,这些段之间可以有若干间隔不必相连。如果该模式个数大于最小支持度,则说明该模式为频繁模式。

定义4 一个序列模式X1*X2*X3*…*Xn 频繁必须符合两个条件:1)这些组成序列模式的各个频繁段必须同时出现在该条序列中,而且这种的序列个数必须大于等于最小支持度;2)每个频繁段|Xi|≥MinLen, n≥i≥1, 其中MinLen 为最短频繁模式长度。

通过以上两步就可得到较长的频繁模式。第一步,从原始序列中挖掘满足条件的短频繁模式段Xi;第二步,将第一步产生的短频繁模式段进行组合,得到长的频繁模式。 定义5 对于一个序列模式M=X1*X2*X3*…*Xn,另一个序列模式

N=X1*X2*X3*…*Xn*Xn+1,如果Xn+1 不为空,那么称序列模式M是序列模式N的前缀。

龙源期刊网 http://www.qikan.com.cn

2.2 连续频繁模式段的产生

类似prefixspan方法由2步组成:1) 将原序列数据库转换成一系列的投影序列数据库。2)在这些投影序列数据库上挖掘频繁序列模式。 2.3 频繁模式的产生

首先对原始序列数据库进行一次扫描,记录下上述频繁模式段在每条序列中最后产生的位置。

定义6 频繁模式段P 在某条序列中的偏移位置为P即在该序列中第一次出现后的位置。 定理 如果对于频繁序列模式段P 和Q同时出现的某序列中,并且P 在该序列中的偏移位置小于Q 出现的最后位置的序列个数大于MiniSup,那么P*Q就是频繁模式。 下面分几步阐述产生频繁模式的过程。

1)产生邻近短频繁模式段投影数据库,并分别标记该频繁模式段在每条序列中的偏移位置以及最后出现位置;

2)将Mi 与各个短频繁模式段进行组合,根据上述定理,在频繁模式段Ni 和Mi同时出现的序列中, 如果Ni 的最后出现的位置大于等于Mi 的偏移量,并且有大于MiniSup的序列条数满足上述条件,那么Mi*Ni就是频繁模式;

3)不断重复步骤2)以产生更长的频繁模式, 直到不再产生新的频繁模式为止。 2.4 JBioPM算法的主要参数

最小支持度阈值r:模式支持度大于等于该值的模式为频繁模式,为进一步提高算法的效率,同时设置一个窗口值w来控制模式增长。 以下为JBioPM算法的伪代码:

参数:生物序列集合D,最小分布支持度阈值min_sup1,最小局部支持度阈值min_sup2,每次投影最大长度W。

输出:所有满足最小分布支持度阈值和局部支持度阈值的序列模式。 1) For each S D { //D是序列数据集

2) 扫描序列S,生成大于等于最小局部支持度的频繁1-序列模式及其支持数,组成频繁项集PF。

龙源期刊网 http://www.qikan.com.cn

3) For each P∈PF {

4) 对于每个P做长度为W的投影,构建投影数据库M。

5) 调用 FindFreSegs(ref AryH,M,min_sup2,prefix,winGap,s)寻找频繁项。}; 6) 将得到的频繁项都存入MAry[i]中。}

7) 调用FindLongFreSegs(AryH,l),将产生的序列存入AryH1中。 //对短频繁项序列进行组合形成长频繁序列 8) For(int i=0;i

9)For each element MAry[i] {

10)如果element的个数大于等于分布支持度min_sup1,则将其存入FinalAry中} 11) }

12) 输出结果集FinalAry。

// 下面是在任意一条序列中寻找以频繁1项为前缀的频繁序列,为了防止每次投影数据库过大,特设置最大//投影长度W,其中AryH是来保存当前处理序列所得到的频繁项,M是每次产生的投影数据库,s2是局部支持//度,prefix是前缀,originS是原始序列。

1) FindFreSegs(ref ArrayList AryH,string[] M,int s2,string prefix,int W,string originS){ 2) 在投影数据库M中寻找频繁的前缀P,并将其存入ArrayList型prefixAry。 3) For each P prefixAry{

4) 如果频繁前缀P的长度小于W,则将频繁项P存入AryH中,同时产生P在该序列中的最后出现位置P-L偏移位置P-D。

7) 否则以prefix+P为前缀,在原始序列S上继续作长度为W的投影,构建投影数据库N 8) 即FindFreSegs(ref ArrayList AryH,string[] M,int s2,string prefix,int W,string originS) 9) } 13) }

龙源期刊网 http://www.qikan.com.cn

FindLongFreSegs(AryH,l)

输入:AryH为存放组合前的短频繁序列,l为组合的短频繁序列段数 输出:组合后短频繁序列段数增加1的长频繁序列集合 AryH1为存放组合后的频繁序列 1)For(i=0;i 2)For(j=1;j

3)If(满足Pi-L≥Pj-D的序列个数大于MiniSup),那么Pi*Pj就是频繁模式,存入AryH1中 4)Return

3 实验结果和分析

为证明JBioPM算法的有效性,我们给出JBioPM算法与BioPM算法比较。实现环境为Windows XP平台,内存1G,Pentium dual-core 1.86GHz。采用JAVA语言编写的。数据集来自Pfam[4](http://www.sanger.ac.Up/Software/Pfam/)数据库蛋白质序列组成的数据集。

通过图1可知,在相同的支持度阈值的情况下,2种算法的运行时间都是随着序列数目的增加而增加,但是,JBioPM算法的运行时间比BioPM算法少,因为JBioPM算法能利用从第一阶段获得的局部模式信息Xi降低第二阶段全局模式X1*…*Xn搜索的时间,同时也提高了对具有生物意义的序列模式搜索的效率。 4 结束语

本文在多支持度概念的基础上提出了一种新具有约束限制的模糊匹配的生物序列模式算法JBioPM。该算法考虑生物序列模式的各种约束特征。这种策略适合挖掘包含任意长度间隔的模式,通过对真实的蛋白质家族序列数据库进行处理,证明该算法效率优于BioPM算法是可行有效的。 参考文献:

[1] Luscombe N M,Greenbaum D,Gerste M.What Is Bioinformatics:A Proposed Definition and Overview of the Field[J].Methods Information in Medicine,2001,40(4):346-358. [2] Xiong Yun,Zhu Yangyong.BioPM:An Efficient Algorithm for Protein Motif Mining[C]//Proc.of ICBBE’07.IS.I.J:IEEE Press,2007.

龙源期刊网 http://www.qikan.com.cn

[3] Wang K,Xu Y,Yu J X.Scalable sequential pattern mining for biological

sequences[C]//Proceeding of the 13th ACM International Conference on Information and Knowledge Management.New York:ACM Press,2004:178-187.

[4] Bateman A,Bimey E,Cerruti L,et al.The Pfam Protein Families Database[J].Nucleic Acids Res,2002,30(1):276-288.