生物序列分析算法的研究及其應(yīng)用

《生物序列分析算法的研究及其應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、中國科學(xué)技術(shù)大學(xué)博士學(xué)位論文生物序列分析算法的研究及其應(yīng)用姓名：趙裕眾申請學(xué)位級別：博士專業(yè)：計算機軟件與理論指導(dǎo)教師：陳國良20100501摘要隨著人類基因組計劃的完成，人們獲得了大量的生物學(xué)數(shù)據(jù)。在對這些生物數(shù)據(jù)進行處理和分析的過程中，涌現(xiàn)出了大量的數(shù)學(xué)問題。這些數(shù)學(xué)問題亟需通過有效的計算手段進行解決。DNA和蛋白質(zhì)研究是分子生物學(xué)中兩項核心的研究課題，我們針對DNA和蛋白質(zhì)序列分析中出現(xiàn)的一些數(shù)學(xué)問題進行研究。單體型是一些特定的DNA位點組成的序列。單體型分析可以幫助我們了解基因與疾病之間的關(guān)聯(lián)，這在遺傳疾病的研究方面具有重要意義。模體是一些保守的DNA片段，模體發(fā)現(xiàn)

2、對基因轉(zhuǎn)錄及其調(diào)控的研究很有幫助。蛋白質(zhì)的空間結(jié)構(gòu)決定了它的功能，基于蛋白質(zhì)序列，我們可以對蛋白質(zhì)的結(jié)構(gòu)進行預(yù)測，從而為病毒檢測以及生物制藥等研究提供幫助。本文圍繞單體分型、模體發(fā)現(xiàn)和蛋白質(zhì)結(jié)構(gòu)預(yù)測等問題展開研究，主要的研究內(nèi)容包括：(1)提出一種群體數(shù)據(jù)集上的單體分型算法由于成本的限制，單體型難以通過實驗手段大量獲得。但是單體型可以利用基因型數(shù)據(jù)通過計算手段進行求解，其中分塊-合并策略被廣泛地應(yīng)用于多個算法中，用以提高算法的效率。在傳統(tǒng)的分塊一合并策略中，分塊是均勻的，但很多研究表明單體型具有特有的塊結(jié)構(gòu)，分塊并不均勻。基于此我們統(tǒng)計不同位點間的關(guān)聯(lián)強度，并使用動態(tài)規(guī)劃算

3、法設(shè)計了更合理的分塊策略，利用貪心算法對相鄰分塊進行合并，我們將新的分塊．合并策略其應(yīng)用于EM單體分型算法中。(2)提出一種家系數(shù)據(jù)集上的單體分型算法近來，通過一些新的生物實驗手段，可以獲得一種新類型的數(shù)據(jù)——異或基因型?；诋惢蚧蛐偷膯误w分型成為一項新的研究課題。研究者們對群體數(shù)據(jù)集上基于異或基因型的單體分型算法做了很多研究，但基于家系數(shù)據(jù)的研究還很少?；谕昝肋M化樹模型，我們將家系上的異或基因型分型問題轉(zhuǎn)化為圖論中的圖實現(xiàn)問題進行求解，家系結(jié)構(gòu)為問題求解提供了更多的約束，使得問題有更大的概率獲得唯一解。(3)提出一種序列模體發(fā)現(xiàn)算法模體在轉(zhuǎn)錄因子綁定及蛋白質(zhì)間相互作用

4、中起著重要作用，對它的發(fā)現(xiàn)會有助于我們了解基因的功能。植入(fJd)模體發(fā)現(xiàn)是其中一類經(jīng)典的問題，但不幸的是，這一問題是NP難解的。研究者們提出了很多算法。由于問題的NP難解性，精確算法難以在有效時間內(nèi)對其進行求解。結(jié)合哈希表和剪枝策略，我們提出一種更有效的序列模體發(fā)現(xiàn)精確算法。(4)提出一種蛋白質(zhì)二級結(jié)構(gòu)預(yù)測算法蛋白質(zhì)結(jié)構(gòu)的確定對我們了解蛋白質(zhì)的功能至關(guān)重要。以往的蛋白質(zhì)結(jié)構(gòu)預(yù)測算法大多是基于序列以及數(shù)據(jù)庫比較摘要的。我們結(jié)合化學(xué)位移信息和蛋白質(zhì)序列來對蛋白質(zhì)的二級結(jié)構(gòu)進行預(yù)測。通過NMR實驗，我們可以獲得蛋白質(zhì)中每個氨基酸對應(yīng)原子的化學(xué)位移信息。利用這些化學(xué)位移信息，我

5、們提出一種新的蛋白質(zhì)二級結(jié)構(gòu)預(yù)測算法。算法首先使用KNN方法對蛋白質(zhì)二級結(jié)構(gòu)進行初步預(yù)測，之后在利用BCJR算法對預(yù)測結(jié)果進行平滑。按照研究內(nèi)容分類，本文的貢獻和創(chuàng)新之處在于：(1)群體數(shù)據(jù)集單體分型根據(jù)單體型固有的塊結(jié)構(gòu)，提出了一種更合理的單體型分塊．合并算法，并將其應(yīng)用于群體數(shù)據(jù)集單體分型中，提高了分型的準確性。(2)家系數(shù)據(jù)集單體分型基于一種新型的異或基因型數(shù)據(jù)，結(jié)合家系信息，提出一個多項式時間的算法對單體型進行求解。和群體數(shù)據(jù)集相比，家系數(shù)據(jù)集有更大概率獲得唯一解。(3)序列模體發(fā)現(xiàn)提出了一種新的序列模體發(fā)現(xiàn)算法，設(shè)計了一個完美哈希函數(shù)，對解空間進行哈希，并在計算的

6、過程中對不可能的解進行剪枝，和已有的算法相比，該算法取得了更高的效率。(4)蛋白質(zhì)二級結(jié)構(gòu)預(yù)測基于化學(xué)位移數(shù)據(jù)和蛋白質(zhì)序列，利用KNN方法對蛋白質(zhì)二級結(jié)構(gòu)進行預(yù)測，并使用BCJR算法對結(jié)果進行平滑，和已有的算法相比，該算法取得了較高的預(yù)測準確性。關(guān)鍵詞：生物信息學(xué)、單核苷多態(tài)性(SNP)、單體分型、模體發(fā)現(xiàn)、蛋白質(zhì)二級結(jié)構(gòu)預(yù)測‘AbstractWiththecompletionoftheHumanGenomeProject，wegetalargemountofbiologicaldata．Manymathematicalproblemsarisefromtheanalysi

7、sandprocessingofthesebiologicaldata．Efficientalgorithmsarerequiredtobedesignedtosolvetheseproblems．DNAandproteinstudiesaretwobasicsubjectsinthestudyofmolecularbiolgy．WestudysomeproblemsintheanalysisofDNAandproteinsequence．HaplotypeisthesequenceofsomespecialDNA