基于离散度量进化树的构建方法地地研究

《基于离散度量进化树的构建方法地地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、◆、、、m№吲m⋯埘眦怕耐山崦呲乱㈣嬲必discretemeasureByXinyuanZhouB．E．(HarbinInstituteofTechnology)2002AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringlnCollegeofinformationscienceandengineeringintheGraduateSchoolofHunanUniversitySupe

2、rvisorProfessorB0LiaoNovember，2010湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。／1／作者签名：心＼卅彰L日期：列矿年／Z_乒JS-日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留

3、并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于l、保密口，在年解密后适用本授权书。2、不保密团。(请在以上相应方框内打“4”)作者签名：导师签名：·组言白姨一辫荫日期：2．OlV年日期：劫7年，Z月厂日I胡j一13摹丁

4、离敞庋鼍的进化树构建方法研究摘要系统进化分析是生物信息学中的重要研究领域，它的主要研究手段是从一组同源的DNA或蛋白质序列出

5、发，计算各个序列之间的进化距离，进而构建反映物种进化关系的进化树。构建进化树的方法主要分为三类，即距离法、简约法和似然法。其中，距离矩阵法以结构简单，具有良好的理论基础等特点获得广泛应用。本文将对距离法做一些探索性的改进研究。基于距离矩阵法是构建进化树方法中比较常用的一类方法，但是传统的基于距离矩阵法是建立在序列比对基础上的，使一些主观因素破坏数据的原始状态，导致计算结果因人而异。并且序列比对提高了进化树构建的成本，经过序列比对得到的距离易受序列长度影响，与真实进化距离的差别较大。所以本文为了解决这个问题

6、，提出了新的相似距离度量算法．离散度量，这种度量法度量序列之间的距离不需要序列比对，没有主观因素干涉，而且比较直观，计算量小。并在此离散度量的基础上，提出来一种横纵法的改进算法，原横纵法在构造出连通图后，需要对所有的边的权重进行排序，而改进后的算法不需要进行排序，构造连通图的同时就可以直接构建进化树。基于离散度量的距离矩阵法是建立在信息理论法基础上提出来的。这种方法是在先将分子序列转换成可以让现有的线性代数、统计理论、信息理论等数学工具处理和分析的对象，进而再定义向量之间的两两相似度或不相似度。在文中采用

7、信息增益来度量序列之间的相似性。该方法首先运用K串对DNA序列进行编码，提取序列之间的共同之处，然后计算信息增益来表示两两序列之间的相似度，再构建相似距离矩阵，然后在该相似距离矩阵的基础上构建进化树，并与其他方法进行了比较。基于LabVIEW平台的进化树构建系统，可以方便的从Excel或TXT文件中批量导入相似距离矩阵数据，并以图形化的形式表示出相应的进化树。为了评估该基于离散度量的构建进化树的方法，本文选取了10种胎生哺乳动物的线粒体全基因序列作为实验数据，并采用PHYLIP软件中的Neighbor．e

8、xe程序来评估的，通过做实验来验证算法的可行性。关键词：进化树；离散度量；距离矩阵；信息增益；信息理论V硕士学f蕾论文AbstractPhylogeneticanalysisisoneimportantfieldinbioinformatics；itsmaintaskistoreconstructaphyiogenetictreefromagroupofhomologousDNAorproteinsequences，showingtheevolutionaryrelationshipbetweenthos

9、esequences．Therearemainlythreetypesoftree--buildingmethods：distance，parsimonyandlikelihood．Distancematrixmethodhaswideapplicationsbecauseofitssimplicityandsolidtheory．Thisthesiswilldosomeexploratoryresearchestoimpro