基于dna计算的clique聚类算法研究

《基于dna计算的clique聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP391.7密级：UDC：004.9编号：201222102008河北工业大学硕士学位论文基于DNA计算的CLIQUE聚类算法研究论文作者：白晓丽学生类别：全日制学科门类：工学硕士学科专业:计算机科学与技术指导教师：石陆魁职称：副教授DissertationSubmittedtoHebeiUniversityofTechnologyforTheMasterDegreeofComputerScienceAndTechnologyRESEARCHONCLIQUEALGORITTHMBASEDONDNACOMPUTINGbyBaiXiaol

2、iSupervisor:AssociateProf.ShiLukuiNovermber2014原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文不包含任何他人或集体已经发表的作品内容，也不包含本人为获得其他学位而使用过的材料。对本论文所涉及的研究工作做出贡献的其他个人或集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：日期：关于学位论文版权使用授权的说明本人完全了解河北工业大学关于收集、保存、使用学位论文的以下规定：学校有权采用

3、影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供本学位论文全文或者部分内容的阅览服务；学校有权将学位论文的全部或部分内容编入有关数据库进行检索、交流；学校有权向国家有关部门或者机构送交论文的复印件和电子版。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：日期：导师签名：日期：摘要随着全球科技的发展，世界网络化程度日益加深，互联网的普及导致信息量激增，对海量信息的数据挖掘已经引起了信息产业界的极大关注。聚类是数据挖掘的重要手段，然而现代计算机已经很难满足传统聚类算法对速度和存储能力的要求，因此设计新的高效的聚类算法势在必行。DN

4、A计算是借助DNA分子和生化操作实现数学运算的一种新兴的学科交叉计算模式，它将电子计算机解决的问题转换到特定编码的DNA序列上，通过杂交、电泳、提纯等一系列的生物反应得到问题的解空间，具有并行性高、速度快、存储能力强的特点。本文将DNA计算与经典网格聚类算法CLIQUE相结合，提出了一种基于DNA计算的CLIQUE算法，仿真实验结果表明，该算法可以有效降低网格聚类的时空复杂度，提高计算速度，具有一定应用前景。本文的研究内容和主要成果如下：首先，提出基于DNA计算的CLIQUE算法。将CLIQUE网格中的单元格转换成节点并连接那些候选节点成图，利

5、用Adleman博士解决哈密尔顿路径问题的模型，建立适合转换图的DNA计算模型，在DNA分子进行生化反应后的产物中提取聚类结果。其次，通过仿真实验检测DNA计算模型效果。仿真实验通过计算机模拟顶点和连接边的DNA编码，然后进行杂交、电泳、提纯等整个生化反应过程，生成生化操作的所有可能解，从中提取出聚类结果。仿真实验用人工合成的少量数据证明了DNA计算解决CLIQUE算法的可行性，与原CLIQUE算法相比，新算法在保证聚类效果的前提下提高了执行效率。最后，在乳腺癌病历三维数据集上进行仿真实验。将该三维数据集映射到二维平面上，形成三个二维数据集，通

6、过计算机模拟得出这三个二维数据集的聚类结果，再取其交集获得三维聚类结果，得出的乳腺癌发病高峰期和完全治愈时间与实际数据的分析结果相符合。关键字：DNA计算Adleman模型数据挖掘CLIQUE算法网格聚类IIIABSTRACTWiththedevelopmentoftheworld'sscienceandtechnology,thedegreeofworldnetworkedismoreandmoredeepening.TheInternet'suniversalcausesinformationexplosion,andthendatamin

7、ingfromagreatamountofinformationhascausedalotofattention,ininformationindustry.Clusteringisanimportantmeansofdatamining,however,moderncomputershasbeendifficulttomeetthetraditionalclusteringalgorithmtotherequirementofspeedandstoragecapacity.Therefore,itisimperativetodesignnew

8、efficientclusteringalgorithms.DNAcomputingisacross-disciplinarycomputingmod