基因組片段填充算法研究

定　價：￥49.00

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

購買這本書可以去

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

目錄
第 1 章緒論 ·········································································.1
1.1 研究背景和意義 ························································.1
1.2 研究現(xiàn)狀 ···································································.4
1.3 算法知識簡介 ···························································.6
1.3.1 算法及算法的計算復(fù)雜性 ···········································.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 基于加權(quán)雙向 overlap 圖的可傳遞約減算法······················13
1.5 本書的組織結(jié)構(gòu) ························································14
第 2 章基因組片段填充問題介紹········································17
2.1 計算基因組學(xué)相關(guān)概念·············································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 算法的實現(xiàn) ·······························································39
3.4 算法可行解的性 ················································43
3.5 算法的時間復(fù)雜度分析·············································45
第 4 章雙面 SF-MNCA 問題的 1.5-近似算法介紹 ··············47
4.1 引言 ··········································································47
4.2 公共鄰接數(shù)的一個上界·············································48
4.3 雙面填充算法 ···························································61
4.4 算法的時間復(fù)雜度分析·············································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 相關(guān)知識簡介 ···························································90
6.2.1 堿基 ····································································90
VIII
6.2.2 加權(quán)雙向 overlap 圖 ··················································91
6.3 可傳遞約減算法 ························································93
6.3.1 可傳遞約減原理及正確性證明 ·····································93
6.3.2 可傳遞約減在加權(quán)雙向 overlap 圖中的實現(xiàn)······················94
6.3.3 可傳遞約減算法的設(shè)計與實現(xiàn) ·····································95
6.4 實驗及結(jié)果分析 ························································97
結(jié)束語 ··················································································101
參考文獻 ··············································································105