MCL聚类算法求解植入(l,d)模体识别问题  

MCL Clustering Algorithm Solving Planted(l,d) Motif Identification

作　　者：陈昆[1] 张小骏[1] 

机构地区：[1]西安电子科技大学计算机学院,西安710021

出　　处：《河南大学学报（自然科学版）》2015年第1期102-107,共6页Journal of Henan University:Natural Science

摘　　要：模体识别是指寻找一系列功能相近且形式相似的基因片段.为此将MCL聚类算法引入模体识别应用,设计出一种适用于这个问题的新算法,在一组目标DNA序列中找到拟识别的模体.该方法基于马尔科夫链原理,构建概率转移矩阵,按随机游走方式对矩阵进行扩展、膨胀迭代,最终形成各个样本的分类.在此基础上进行贪心算法求精计算,得出若干组模体.实验表明该算法是有效的.The motif identification is to find a series of gene fragments with similar functional and similar forms,so we put the MCL clustering algorithm into solving the problem of the motif identification in order to design a new algorithm for the problem,which is used to find the motif in a set of target DNA sequence.The method is based on Markov chain theory,by which we build the probability transition matrix,carry out the expansion and inflation iteration according to the random walking on matrix extension,and finally obtain the samples clustering.On this basis,the greedy algorithm refinement calculation is used for getting some motifs.The experiment indicates that this algorithm is valid.

关 键 词：模体识别 MCL聚类算法 马尔科夫链 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]