基于聚类和团求精的模体识别算法

《基于聚类和团求精的模体识别算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要生物体基因的表达借助于具有调控作用的蛋白质和DNA序列中的调控位点的结合来完成，而调控位点出现在相关基因的上游调控区域，并且通常是保守的序列模式，即模体。因此，模体识别对于深入研究基因调控机制、发现生物功能位点有着重要的意义。模体识别问题是生物信息学主要的研究领域之一，是计算生物学的核心问题之一，是近年来研究的热点问题。本文首先介绍了模体识别问题的研究背景和意义，介绍了模体的表示方法、评分标准，和模体识别问题的定义，并对模体识别问题的研究现状进行了介绍。根据模体识别问题的现状，提出了利用基于聚类和

2、团求精的模体识别算法(AClusterandCliqueRefinementApproachtoMotifDiscovery,CCRMD)来解决模体识别问题，基本思想是利用基于信息熵的聚类算法求出一系列的候选模体实例的集合（每个集合就是一个聚类），将每个候选模体实例集转化为图，利用求图的所有团的算法对每个候选模体集进行求满足一定条件的相似字符串的集合，对每个字符串集合求其一致序列，去输入序列中查找模体实例，并求出模体。针对模拟数据和真实数据的仿真实验结果表明，CCRMD算法具有较高的平均性能系数。但是

3、，本文算法不足的地方是仅仅用于解决每条序列中仅含有一条模体实例的模体识别问题，通过改进，可以用于解决每条序列中含有多条模体实例的情况。关键词：模体识别聚类算法团一致序列AbstractExpressionofgenesinorganismsisusuallyfinishedwiththeaidofregulationproteinandtheregulatorysitesinDNA;theregulatorycitesareusuallyupstreamtotheregulatoryregions,a

4、ndconservative,whichiscalledmotif.Asaresult,motifdis-coveryissignificantonfurtherresearchongeneregulatorymechanismsandfindingBiologicalfunctionsites.Therefore,motifdiscoveryisoneofthemainresearchfieldsinbioinformatics.ItisthecoreofComputationalBiologica

5、landthehotresearchissuesinrecentyears.Thispaperintroducesthebackgroundandsignificanceofmotifdiscovery,there-presentationandevaluationstandardofmotif,thedefinitionofmotifdiscovery,andthecurrentsituationofmotifdiscovery.Thenthispaperproposesaclusterandcli

6、quere-finementapproachtomotifdiscovery(CCRMD)tosolvetheproblemofmotifdiscov-ery,itsbasicideaistouseclusteralgorithmbasedoninformationentropytoobtainaseriesofcandidatemotifinstancesets(eachsetisacluster),thenchangeeachcandidatemotifinstancesetintoagraph,

7、andusethealgorithmoffindingallcliquesofagraphtoobtainacollectionofsimilarstringswhichmeetscertainconditionsforeachcandi-datemotifinstanceset,thenfindmotifinstancesintheinputsequencesaccordingtothehomologoussequencesofeachcollectionofstrings,finallyobtai

8、nthemotif.ExperimentalresultsdemonstratethatCCRMDperformswellonbothsimulatedandbiologicalsamples.ThedeficiencyofthisthesisisthatCCRMDonlysolvetheproblemwiththeassumptionofexactlyoneoccurrence(ofmotifinstance)perse-quence,however,