基因組片段填充算法研究

定　價：￥49.00

作　者：	柳楠
出版社：	電子工業(yè)出版社
叢編項：
標　簽：	暫缺

購買這本書可以去

ISBN：	9787121435423	出版時間：	2022-05-01	包裝：	平裝-膠訂
開本：	128開	頁數：		字數：

內容簡介

　　無論是目前世界上肆意流行的各類病毒、以癌癥為首的各種疾病，還是某些被發(fā) 現的新物種，人類對低成本、高效、準確地獲取這些生物的全基因組序列都有著迫切的需求。對于這種大規(guī)模數據的分析和處理，僅靠生物學手段無法高效完成，使用計算機技術將有效節(jié)省處理問題的時間和降低經濟成本。本書研究的基因組片段填充算法是在利用生物測序手段獲取基因組片段后，使用計算機領域的算法思想和技術，協助獲取完整基因組序列的有效手段，具有較好的實際應用意義。本書以科研課題“基因組片段填充算法研究”為背景，以設計各類片段填充算法、分析算法復雜度、提高算法近似性能比為主要目標，對如何使用計算機算法中的貪婪、局部搜索和匹配等算法思想解決基因組片段填充中的難點問題進行了一系列探索。本書涵蓋了基因組片段填充中各類問題的定義、填充原理和算法描述，通過嚴謹的理論推導證明了算法的正確性和近似性能比，并通過實例展示了算法的運行過程和效果。本書可作為從事基因組序列填充問題研究工作的有關人員的參考用書。

作者簡介

　　柳楠，博士、副教授，畢業(yè)于山東大學計算機科學與技術學院。2015年10月至2016年10月于美國蒙大拿州立大學訪學。主要研究領域是生物計算中基因組序列的填充問題，以及計算機算法設計與復雜度分析。以作者在IEEE/ACM Trans. Comput. Biology Bioinform、Algorithmica國際期刊和COCOON、TAMC、COCOA等國際知名學術會議上發(fā)表多篇學術論文，目前主持在研國家自然基金青年項目1項、山東省自然基金面上項目1項，結題山東省青年科學家獎勵項目1項，參與4項國家和省級項目，獲批軟件著作權4項。

圖書目錄

目錄
第 1 章緒論 ·········································································.1
1.1 研究背景和意義 ························································.1
1.2 研究現狀 ···································································.4
1.3 算法知識簡介 ···························································.6
1.3.1 算法及算法的計算復雜性 ···········································.6
1.3.2 P 類、NP 類及 NPC 類問題 ·········································.7
1.3.3 近似算法和近似性能比 ··············································.9
1.3.4 貪婪、局部搜索策略·················································10
1.4 本書的主要貢獻 ························································11
1.4.1 化公共鄰接距離的基因組片段填充問題的定義修正 ·····12
1.4.2 SF-MNCA 問題特殊實例的多項式時間精確算法 ················12
1.4.3 雙面 SF-MNCA 問題的 1.5-近似算法······························13
1.4.4 單面 SF-MNCA 問題的 1.25-近似算法 ····························13
1.4.5 基于加權雙向 overlap 圖的可傳遞約減算法······················13
1.5 本書的組織結構 ························································14
第 2 章基因組片段填充問題介紹········································17
2.1 計算基因組學相關概念·············································17
2.2 鄰接、斷點 ·······························································18
2.3 SF-MNCA 問題 ·························································22
2.4 封閉符號“#”··························································23
2.5 SF-MNCA 問題中的幾個特性 ···································24
2.6 斷點的分類 ·······························································28
2.7 k-Type-1 類型串、k-Type-2 類型串、插入串·············29
VII
第 3 章特殊情況下的多項式時間精確算法 ·························33
3.1 引言 ··········································································33
3.2 算法的前提 ·······························································33
3.3 算法的實現 ·······························································39
3.4 算法可行解的性 ················································43
3.5 算法的時間復雜度分析·············································45
第 4 章雙面 SF-MNCA 問題的 1.5-近似算法介紹 ··············47
4.1 引言 ··········································································47
4.2 公共鄰接數的一個上界·············································48
4.3 雙面填充算法 ···························································61
4.4 算法的時間復雜度分析·············································65
第 5 章單面 SF-MNCA 問題的 1.25-近似算法介紹 ············67
5.1 引言 ··········································································67
5.2 問題描述 ···································································69
5.3 插入 Type-1 串 ··························································69
5.3.1 插入 1-Type-1 串······················································69
5.3.2 插入 2-Type-1 串······················································70
5.3.3 插入 3-Type-1 串······················································72
5.3.4 插入剩余缺失基因 ···················································73
5.3.5 完整算法描述 ·························································75
5.4 近似算法分析 ···························································77
5.4.1 改進的近似下界 ······················································77
5.4.2 近似性能比分析 ······················································79
第 6 章序列拼接的信息約減問題········································89
6.1 引言 ··········································································89
6.2 相關知識簡介 ···························································90
6.2.1 堿基 ····································································90
VIII
6.2.2 加權雙向 overlap 圖 ··················································91
6.3 可傳遞約減算法 ························································93
6.3.1 可傳遞約減原理及正確性證明 ·····································93
6.3.2 可傳遞約減在加權雙向 overlap 圖中的實現······················94
6.3.3 可傳遞約減算法的設計與實現 ·····································95
6.4 實驗及結果分析 ························································97
結束語 ··················································································101
參考文獻 ··············································································105