資源描述：
《基于距離進(jìn)化樹的構(gòu)建算法地地研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、國內(nèi)圖書分類號：TP301.6U.D.C.:681.3.06工學(xué)碩士學(xué)位論文基于距離的進(jìn)化樹構(gòu)建算法研究碩士研究生：于季芝導(dǎo)師：郭茂祖教授申請學(xué)位：工學(xué)碩士學(xué)科、專業(yè)：計算機科學(xué)與技術(shù)所在單位：計算機科學(xué)與技術(shù)學(xué)院答辯日期：2007年7月授予學(xué)位單位：哈爾濱工業(yè)大學(xué)ClassifiedIndex:TP301.6U.D.C.:681.3.06DissertationfortheMasterDegreeofEngineeringDISTANCE-BASEDPHYLOGENETICMETHODRESEARCH
2、Candidate:YuJizhiSupervisor:Prof.GuoMaozuAcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerScienceandTechnologyAffiliation:SchoolofComputerScienceandTechnologyDateofDefence:July,2007Degree-Conferring-Institution:HarbinInstituteofTechnology哈爾
3、濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文摘要進(jìn)化樹是描述物種進(jìn)化順序和進(jìn)化關(guān)系的一種拓?fù)浣Y(jié)構(gòu)。構(gòu)建進(jìn)化樹在生物學(xué)中有重要的應(yīng)用，研究高效準(zhǔn)確的構(gòu)建進(jìn)化樹算法有實際的應(yīng)用價值。本文針對進(jìn)化樹構(gòu)建問題進(jìn)行研究。進(jìn)化樹構(gòu)建問題是一個NP完全問題，因而構(gòu)建算法都是啟發(fā)式的。通常使用的方法分為三大類：(1)距離法，(2)最大簡約法，(3)最大似然法。本文使用基于最大似然法的距離法構(gòu)建進(jìn)化樹，主要分為兩個階段：首先估計所有分類群之間的進(jìn)化距離，只有序列進(jìn)化距離越精確，構(gòu)建的進(jìn)化樹才會越準(zhǔn)確；然后基于這些距離值之間的關(guān)系構(gòu)建進(jìn)化樹
4、。本文工作主要包括以下兩個階段：在第一階段，對距離估計方法和最大似然法進(jìn)行了研究，改變了傳統(tǒng)的進(jìn)化距離估計方法，把序列比對由兩個序列比對擴大到多重序列比對；利用基于quartet的最大似然法對進(jìn)化模型進(jìn)行優(yōu)化并使用最小二乘法快速重構(gòu)所有可能的quartet拓?fù)浣Y(jié)構(gòu)，并優(yōu)化其分支長度，對兩兩序列間距離進(jìn)行估計，為進(jìn)化樹的構(gòu)建提供了更加準(zhǔn)確的距離矩陣。在第二階段，主要對鄰接法構(gòu)建進(jìn)化樹進(jìn)行改進(jìn)，改進(jìn)工作分為兩部分：一是針對在第一階段得到的距離矩陣并不總是滿足可加性的問題，引入了距離的方差和協(xié)方差，采用加權(quán)的
5、計算公式更新距離矩陣，使算法構(gòu)建的拓?fù)浣Y(jié)構(gòu)更加準(zhǔn)確。二是改進(jìn)了鄰接法的貪心特性，由于鄰接法每次只聚合速率校正距離最小的兩個分類單元，進(jìn)而導(dǎo)致整個體系的偏差，實驗證明速率校正距離最小的配對并不一定是在真實的進(jìn)化樹中進(jìn)化距離最近的，基于此，改進(jìn)算法每次聚合速率校正距離滿足“neighbor”的兩個分類單元，使算法不總是搜索分支長度之和最短的進(jìn)化樹，很大程度減少了這種體系偏差對真實進(jìn)化關(guān)系的影響，并通過實驗驗證了該算法的準(zhǔn)確性。最后，基于以上的研究成果，實現(xiàn)了一個進(jìn)化樹構(gòu)建系統(tǒng)。關(guān)鍵詞進(jìn)化樹；距離法；鄰接法；
6、最大似然法-I-哈爾濱工業(yè)大學(xué)工學(xué)碩士學(xué)位論文AbstractPhylogenetictreeisakindoftypologicalstructurefordescribingthesequenceandrelationshipofspeciesrevolution.Itissignificanttoconstructphylogenetictreeinthebiologyfieldwhoseefficientandprecisealgorithmscouldyieldtoagreatdealofpr
7、acticalvalue.WestudytheproblemofconstructingPhylogenetictreeinthepaper.ThisproblemisaNPcompleteproblemwhosealgorithmsareallheuristic.Thereareusuallythreemainmethodsfortheproblem:(1)based-distance,(2)maximumparsimony,(3)maximumlikelihood.Wewillmergemaximu
8、mlikelihoodmethodtothebased-distancealgorithmprocessofconstructingphylogenetictreeonthebasisofadvantagesofbothbased-distanceandmaximumlikelihoodmethods.Therearetwomainphasesintheprocess:firstly,weestimatephylogeneticdistan
