一种基丁贪心EM的改进预测算法摘要：本文主要研究了Mot讦预测算法，在贪心EM预测算法基础上进行分析优化，并形成新的预测方法。工作重点是在参数的初始化，对参数模型的重新划分并引入Kd-树的层次聚类的方法，建立新的PKG算法。预测结果表明，在预测较大数据集方面新算法有一定的优势，尤其是对同一物种的序列预测具有更强的搜索和分类能力，在没有影响时间复杂度的前提下显著的提高了搜索的效率。Abstract:Motiffindingalgorithmwasstudiedasthekey-pointinthispaper.OptimizationwasbasedontheEM-baced-greedyalgorithmandthenpredictingmethodwasestab-lished.Parametersinitialization,there-divisionoftheparame-termodelandintroductionofKd-treehierarchicalclustering-method,andtheestablishmentofPKGalgorithmwerepaid-moreatteriUoninthispaper.TheresultsindicatedPKGalgo-rithmhassomeadvantagesinpredictingmotifsinlarge-datasets,especiallyinthepredictionofsequencesinthesame-species・Withadvantagesinsequeneesearchandclassifica-tioncapabilities,thesearchefficiencywasimprovedbyPKGal----本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---gorithmsign讦icantlywithoutaffectingcomplexi-tyinthetime.关键词：Motif预测；贪心EM算法；PKG算法Keywords:Mo廿ffinding；EM-basedgreedyalgo-rithm；PKGalgorithm：TP39文献标识码：A：1006-4311(2011)17-0141-020引言当人类基因组研究进入系统测序阶段时，大量已测定的但未知功能或未经注释的DNA序列，急需可靠的自动的基因组序列注释方法和技术进行处理。人们利用相关测序后DNA序列建立了大量转录因子(TF)数据库，为转录调控的进一步研究提供了丰富的资源，它是用计算机方法构建转录预测模型的基础。大量的数据促进了识别Motif算法和相关预测程序包的发展。目前，对识别Mot讦的算法研究是一个热点，它们大部分都基于一致性序列和矩阵模型。在应用软件预测Motif时，可以运用的方法，有用不同的预测软件比较后取长补短，参考各软件的预测结果，从而提出新的预测方案，最终得到最佳的预测结果［1］。采用不同的算法来比较预测，通过预测结果对比来选择---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---合适的算法。还可在已有算法的基础上来进行改进，在原有序列的基础上进行比较预测，结果更具有说服力。木文就是在贪心EM算法的基础上，通过筛选优化参数修定序列的预测长度范围，从而改进算法的整体预测效率。1贪心EM算法的应用基础贪心EM算法是实现机器学习（GMM）综合学习的一种有效方法，它以递增的方式线性组合多个“弱”模型（单高斯分量），进而得到一个具有很高似然度的“强”模型（高斯混合模型），使得最后所得到的混合模型可以有效地逼近任意复杂的概率分布［2］o3算法测试结果从PRINTS数据库下载部分拟南芥家族序列，随机产生由4条长度在200~250bp之间的拟南芥序列集合,通过多次实验设定Kd-树划分值为6,在一定的序列长度区间内，测试结果如图3所示。其中黑色柱表示MEME的预测数量，灰色柱代表PKG算法的预测数量。PKG算法可降低Mot讦的重叠率，而且还能保证Motif候选序列参照一致的规则进行处理，如表1所示，通过迭代减少了全局搜索时间，与MEME算法相比，相邻的Motif字符串从数据集中剔除。---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---每一次输入一个新的Motif序列时需要假定这个序列是真实存在的，从而限制了MEME模型中两部分的联系，PKG算法通过增加混合密度估计改进了这个问题。算法实现了预测性能的一定改进，但其特异性的绝对水平依然很低。此外，算法产生了大量假阳性结果，这是导致此现象的直接原因，限于当前的认识水平，假阳性结果中有些可能确实是尚未发现的结合位点，其功能需要后续实验来验证。参考文献：⑴张斐，谭军，谢竞博.基于不同算法的mot讦预测比较分析与优化[J].计算机工程，2009,Vol.35(22)：94-96.[2]王维彬，钟润添.一种基于贪心EM算法学习GMM的聚类算法[J].计算机仿真.2007,24(2)：6...