本文關(guān)鍵詞：生物高通量測序片段拼接與分子標記識別算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：快速準確的獲取生物體的遺傳信息是生命科學研究的基石,基因組是生物體全部遺傳信息的載體。測序技術(shù)能夠獲得基因組的遺傳信息,進而較全面的揭示生物體的復雜性和多樣性,因而在生命科學研究中具有十分重要的作用。隨著科學的進步,下一代測序技術(shù)迅速發(fā)展并廣泛應用,使得生物序列數(shù)據(jù)的獲取效率和費用成本的快速下降都達到了前所未有的程度,這些對基因組的深度測序和重測序研究產(chǎn)生了極大的推動作用。序列數(shù)據(jù)生產(chǎn)速度越來越快,由此產(chǎn)生了數(shù)量巨大的生物序列數(shù)據(jù),而如何高效準確的對大數(shù)據(jù)量的生物序列數(shù)據(jù)進行分析和比較,成為了生物信息學領(lǐng)域的新挑戰(zhàn)。近幾年來計算機運算性能的增長趨于緩慢,為應對大數(shù)據(jù)時代的需求出現(xiàn)了Map Reduce、Spark等云計算技術(shù),但目前生物信息領(lǐng)域的各種工具和方法還未能充分利用這些新技術(shù)。因此,本文以序列分析為基礎(chǔ),利用Map Reduce技術(shù)結(jié)合序列比對、串和圖等算法,深入研究了高通量序列拼接與分子標記識別兩方面的幾個問題,主要內(nèi)容如下。(1)提出了基于Map Reduce的高通量序列數(shù)據(jù)的聚類分析算法。生物序列聚類可以為下游序列分析工作提供基礎(chǔ),高通量測序也為序列聚類提出了新內(nèi)容和新挑戰(zhàn)。針對這一問題,本文提出了基于兩種相似度的結(jié)合Map Reduce技術(shù)的貪心聚類方法。首先,從相似序列會共享一定數(shù)量k-mer這一事實出發(fā),本文提出了基于窗口內(nèi)非交疊共享k-mer計數(shù)的相似度計算方法,可以過濾掉不相關(guān)序列間的比對計算,從而大幅度提高比對效率;然后,對于相似序列的精確比對,本文提出了基于共享k-mer擴展塊的塊比對相似度計算方法。利用本文方法可對大規(guī)模序列數(shù)據(jù)如EST、高通量測序讀片段等進行聚類分析。(2)提出了基于序列聚類和Seeds Graph的高通量測序片段拼接算法。全基因組高通量測序數(shù)據(jù)的拼接,主要困難在于高通量序列數(shù)據(jù)讀長短、數(shù)量大和錯誤率高。本文針對這三方面的困難提出了基于Map Reduce和序列聚類的全基因組de novo拼接方法Seeds Graph。該方法利用云計算平臺解決數(shù)據(jù)量大的問題,用序列聚類將短片段以簇表示,并定義可容錯的seed結(jié)構(gòu)來糾正測序錯誤。然后利用seed為頂點建立的SeedsGraph圖來指導測序片段的拼接過程。最后,本文采用路徑相容分析技術(shù)和雙端讀片段信息方式解決重復序列導致的復雜路徑問題。實驗表明Seeds Graph有良好的可擴展性,可處理較大規(guī)�；蚪M的拼接問題。(3)提出了多供體高通量測序數(shù)據(jù)的基因組結(jié)構(gòu)變異分子標記識別算法。目前對生物個體重測序的研究普遍存在測序?qū)ο髷?shù)量較多而測序深度不夠的現(xiàn)象。在這種測序個體較多但深度都不大的數(shù)據(jù)中進行全基因組結(jié)構(gòu)變異識別,往往因為深度不夠而不能獲得準確的結(jié)果。本文針對這一問題,提出了基于多供體高通量重測序數(shù)據(jù)的全基因組結(jié)構(gòu)變異識別方法。該方法利用Map Reduce技術(shù)解決數(shù)據(jù)量巨大的問題,結(jié)合雙端讀片段和讀片段分隔方法進行結(jié)構(gòu)變異事件的識別;利用改進的仿射空位罰分的半全局序列比對算法,預測結(jié)構(gòu)變異精確的斷點位置。(4)綜合本文在序列分析的算法成果,設(shè)計并實現(xiàn)了基于同源搜索和集成分類的mi RNA分子標記識別方法。該方法利用已知mi RNA為參考,對EST或高通量測序數(shù)據(jù)進行同源搜索,使用RNAfold軟件分析發(fā)夾環(huán)結(jié)構(gòu),獲得粗略的mi RNA前體候選集。為了解決該候選集中假陽性率過高的不平衡分類問題,本文提出了基于投票機制的集成學習分類方法。利用已知mi RNA作為正例和適當選擇的反例以不平衡數(shù)據(jù)分類問題的策略訓練多種分類器,再集成為一個單獨的分類器,并對候選集進行分類。利用該方法可得到輸入數(shù)據(jù)集中高可信度的miRNA候選,可以用于指導下游mi RNA識別和分析的研究工作。
【關(guān)鍵詞】：序列比對 序列聚類 基因組拼接 結(jié)構(gòu)變異 高通量測序
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：TP391.4
【目錄】：

• 摘要4-6
• ABSTRACT6-14
• 第1章 緒論14-30
• 1.1 課題背景及意義14-16
• 1.1.1 研究背景14-15
• 1.1.2 研究意義15-16
• 1.2 相關(guān)知識介紹16-24
• 1.2.1 序列分析技術(shù)簡介16-17
• 1.2.2 測序技術(shù)簡介17-22
• 1.2.3 基因組結(jié)構(gòu)變異簡介22
• 1.2.4 非編碼RNA簡介22-23
• 1.2.5 Map Reduce技術(shù)簡介23-24
• 1.3 國內(nèi)外研究現(xiàn)狀24-28
• 1.3.1 高通量數(shù)據(jù)的聚類與拼接24-26
• 1.3.2 生物分子標記的識別26-28
• 1.4 本文主要工作28-30
• 第2章 基于MAPREDUCE的生物序列聚類算法30-54
• 2.1 引言30-34
• 2.1.1 問題描述31-32
• 2.1.2 相關(guān)算法32-34
• 2.2 基于共享k-mer計數(shù)的序列相似度計算方法34-38
• 2.2.1 基于共享k-mer計數(shù)的序列相似度34-35
• 2.2.2 基于Map Reduce的序列共享k-mer計數(shù)算法35-38
• 2.3 基于塊比對的序列相似度計算方法38-47
• 2.3.1 全局比對和局部比對算法38-40
• 2.3.2 基于共享k-mers擴展塊的局部塊比對40-43
• 2.3.3 邊加權(quán)有向無環(huán)圖單源最長路徑算法43-46
• 2.3.4 局部塊比對的優(yōu)化46-47
• 2.4 序列聚類算法47-49
• 2.5 實驗與分析49-52
• 2.6 本章小結(jié)52-54
• 第3章 基于讀片段聚類的高通量數(shù)據(jù)拼接算法54-79
• 3.1 引言54-59
• 3.1.1 拼接方法及相關(guān)算法55-57
• 3.1.2 問題描述57-59
• 3.2 NGS讀片段聚類算法59-65
• 3.2.1 數(shù)據(jù)預處理59
• 3.2.2 生成k-mer群組59-61
• 3.2.3 讀片段的聚類61-65
• 3.3 基于歐拉路徑的contig建立算法65-69
• 3.3.1 Seeds Graph的構(gòu)建65-66
• 3.3.2 Seeds Graph中重復路徑的分析66-68
• 3.3.3 Contigs的生成方法68-69
• 3.4 基于mate-pair的scaffold建立方法69-72
• 3.4.1 Contigs間的相對方向70-71
• 3.4.2 Contigs的定位方法71-72
• 3.4.3 填充gap和生成scaffolds72
• 3.5 實驗與分析72-77
• 3.6 本章小結(jié)77-79
• 第4章 基于高通量測序的多供體結(jié)構(gòu)變異識別算法79-104
• 4.1 引言79-85
• 4.1.1 結(jié)構(gòu)變異及其重要作用80-81
• 4.1.2 結(jié)構(gòu)變異識別方法的研究現(xiàn)狀81-82
• 4.1.3 問題描述82-85
• 4.2 基于Map Reduce的讀片段定位方法85-89
• 4.2.1 不一致的讀片段對86
• 4.2.2 基于Map Reduce的篩選算法86-89
• 4.2.3 合并多供體的候選讀片段89
• 4.3 結(jié)構(gòu)變異的識別算法89-97
• 4.3.1 小型indel事件的識別方法90-91
• 4.3.2 插入事件的識別方法91-92
• 4.3.3 缺失事件的識別方法92-93
• 4.3.4 倒位事件的識別方法93-94
• 4.3.5 易位事件的識別方法94-95
• 4.3.6 重復事件的識別方法95-96
• 4.3.7 識別算法96-97
• 4.4 斷點精確預測算法97-100
• 4.4.1 基于split-read的斷點預測方法97-99
• 4.4.2 基于soft clipping的斷點預測方法99-100
• 4.5 實驗與分析100-103
• 4.6 本章小結(jié)103-104
• 第5章 基于同源搜索與集成分類的MIRNA識別方法104-116
• 5.1 引言104-108
• 5.1.1 相關(guān)研究105-107
• 5.1.2 識別流程107-108
• 5.2 基于Map Reduce的同源序列搜索方法108-111
• 5.2.1 數(shù)據(jù)的預處理108
• 5.2.2 同源序列搜索108-111
• 5.3 基于集成學習的分類器111-113
• 5.3.1 樣本集的選擇111
• 5.3.2 集成分類器的構(gòu)建111-113
• 5.4 實驗與分析113-114
• 5.5 本章小結(jié)114-116
• 結(jié)論116-118
• 參考文獻118-132
• 攻讀博士學位期間發(fā)表的論文及其它成果132-136
• 致謝136-137
• 個人簡歷137

  本文關(guān)鍵詞：生物高通量測序片段拼接與分子標記識別算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：393192