123,123

內(nèi)容簡(jiǎn)介

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

作者簡(jiǎn)介

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

圖書目錄

目錄
第 1 章緒論 ·········································································.1
1.1 研究背景和意義 ························································.1
1.2 研究現(xiàn)狀 ···································································.4
1.3 算法知識(shí)簡(jiǎn)介 ···························································.6
1.3.1 算法及算法的計(jì)算復(fù)雜性 ···········································.6
1.3.2 P 類、NP 類及 NPC 類問(wèn)題 ·········································.7
1.3.3 近似算法和近似性能比 ··············································.9
1.3.4 貪婪、局部搜索策略·················································10
1.4 本書的主要貢獻(xiàn) ························································11
1.4.1 化公共鄰接距離的基因組片段填充問(wèn)題的定義修正 ·····12
1.4.2 SF-MNCA 問(wèn)題特殊實(shí)例的多項(xiàng)式時(shí)間精確算法 ················12
1.4.3 雙面 SF-MNCA 問(wèn)題的 1.5-近似算法······························13
1.4.4 單面 SF-MNCA 問(wèn)題的 1.25-近似算法 ····························13
1.4.5 基于加權(quán)雙向 overlap 圖的可傳遞約減算法······················13
1.5 本書的組織結(jié)構(gòu) ························································14
第 2 章基因組片段填充問(wèn)題介紹········································17
2.1 計(jì)算基因組學(xué)相關(guān)概念·············································17
2.2 鄰接、斷點(diǎn) ·······························································18
2.3 SF-MNCA 問(wèn)題 ·························································22
2.4 封閉符號(hào)“#”··························································23
2.5 SF-MNCA 問(wèn)題中的幾個(gè)特性 ···································24
2.6 斷點(diǎn)的分類 ·······························································28
2.7 k-Type-1 類型串、k-Type-2 類型串、插入串·············29
VII
第 3 章特殊情況下的多項(xiàng)式時(shí)間精確算法 ·························33
3.1 引言 ··········································································33
3.2 算法的前提 ·······························································33
3.3 算法的實(shí)現(xiàn) ·······························································39
3.4 算法可行解的性 ················································43
3.5 算法的時(shí)間復(fù)雜度分析·············································45
第 4 章雙面 SF-MNCA 問(wèn)題的 1.5-近似算法介紹 ··············47
4.1 引言 ··········································································47
4.2 公共鄰接數(shù)的一個(gè)上界·············································48
4.3 雙面填充算法 ···························································61
4.4 算法的時(shí)間復(fù)雜度分析·············································65
第 5 章單面 SF-MNCA 問(wèn)題的 1.25-近似算法介紹 ············67
5.1 引言 ··········································································67
5.2 問(wèn)題描述 ···································································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 改進(jìn)的近似下界 ······················································77
5.4.2 近似性能比分析 ······················································79
第 6 章序列拼接的信息約減問(wèn)題········································89
6.1 引言 ··········································································89
6.2 相關(guān)知識(shí)簡(jiǎ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 圖中的實(shí)現(xiàn)······················94
6.3.3 可傳遞約減算法的設(shè)計(jì)與實(shí)現(xiàn) ·····································95
6.4 實(shí)驗(yàn)及結(jié)果分析 ························································97
結(jié)束語(yǔ) ··················································································101
參考文獻(xiàn) ··············································································105