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

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

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

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

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

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

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

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

7、sandprocessingofthesebiologicaldata．Efficientalgorithmsarerequiredtobedesignedtosolvetheseproblems．DNAandproteinstudiesaretwobasicsubjectsinthestudyofmolecularbiolgy．WestudysomeproblemsintheanalysisofDNAandproteinsequence．HaplotypeisthesequenceofsomespecialDNA