基于比对相似度动态矩阵聚类算法在基因序列中的应用

《基于比对相似度动态矩阵聚类算法在基因序列中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第"$卷第’期计算机应用f:F/"$K:/’!!"##$年’月?:;V@AED=VVF692A6:38=@4/"##$文章编号：&##&%+#’&（"##$）#’%##(,%#(基于比对相似度动态矩阵聚类算法在基因序列中的应用张白妮，骆嘉伟，汤德佑（湖南大学计算机与通信学院，湖南长沙$&##’"）（012345263678632/9:;）摘!要：基于<=>图的聚类算法，利用聚类单元引导类的分割，保证聚类结果不会产生过多的类碎片，但其相似分数阈值?@A:BB初始值和最长公共子串最小长度阈值C1DE81:FG如何确定并没有明确给出。提出基于比对相似度动态矩

2、阵的聚类算法，并在此基础上明确给出了确定9@A:BB初始值和C1DE81:FG阈值的方法。实验结果表明该算法可以获得较好的聚类正确率。关键词：生物序列；聚类；最长公共子串；比对相似度动态矩阵中图分类号：CH(+&/$!!文献标识码：=!""#$%&’$()*(+,-./01&*23%#4*’25$)6(5$’78$)62)2*2942)%2*IJ=K><26L36MNOP)62LQE6MC=K>RELS:@!"#$%&’()*+,"#$$&+-.*’-#+"#//(0(12&+*+3+-4()5-’61"7*+057*2&+*+$&##’"1"7

3、-+*8!1*’5&%’:T@3U6;M(’.MVDE8E3AEGA1E<=>9F@8AED6342F4:D6A1;M5@AG6G1WAEXVF2631:QA:4EAA1E636A62FY2F@E:B9@A:BB23GC1DE81:FGZA1EA1DE81:FGY2F@E:BF:34E8A9:;;:38@58AD634[/E63AD:G@9EG29F@8AD6342F4:D6A1;528EG:3A1E86;6F2D089:DE85EAQEE38E]@E39E8M23GA1E;EA1:GB:DGEAED;63634A1E636A62FY2F@E:B9@

4、A:BB23GA1EY2F@E:BC1DE81:FGGEB636AEFS/^XVED6;E3A8:34E3E8E]@E39E881:QA12AA1682F4:D6A1;1281641EDD2AE:B9:DDE9A3E889F@8AED634/;2<=(53*:56:F:4S8E]@E39E8_9F@8AED634_F:34E8A9:;;:3916FG8AD634_TIR‘ZT6;6F2DI89:DE8RS32;69‘2AD6X[!!随着生物学和医学的迅速发展，特别是人类基因组计划实验所需序列，其中的数据库是欧洲生物信息学研究所［’］的顺利推进以及基因芯

5、片的发明使得同时比较和研究大量基（^

6、聚类算法有了很大提高，这些算法聚类正确率在+#e以上，最高达+’e。都能自动把数量非常庞大的基因数据库进行聚类，但容易产&!相关概念及初始值的确定生聚类不正确、聚类太多及类碎片过多等情况。许多聚类算法都是先读取并计算出所有序列之间的匹配&/&!基于图<=>聚集度?O［.］情况，把序列作为顶点，比对情况作为边来建立相应的图。还这种思想是来自于聚类中最基本的两个概念：类内相似有一些聚类算法所用的序列间的匹配关系不是常用的比较结度（63AEDL9F@8AED86;6F62D6AS）和类间相异度（63AD2L9F@8AED［(］［,］果，例如：?=TCPb利用

7、的是THN=TJ模式识别算法识别G6886;6F62D6AS）。聚类单元?O主要用来引导类的分割，高的簇出的模式来表示序列间的关联关系。甚至在有些情况下，用内相似性和低的簇间相似性对应比较高的?O值，选取?O值二进制数来表示关联关系（如#表示不匹配，&表示匹配）。最大的聚类结果保证不会产生过多的类碎片。［.］T@3U6;等人提出了基于<=>图的聚类算法，并且用了聚定义&!给定一个聚类集合（"&，""，⋯，"9），:"（-5）表示类单元来引导类的分割，保证了聚类结果不会产生过多的类序列5和类"-中多少序列相似，;"-;表示类"-的大小，则序碎片。但基因数

8、据库中的序列数目多得惊人，用无向图来表示如此多的序列以及序列之间的比对相似度非常困难，文献列5