基因組片段填充算法研究

目 錄
第 1 章 緒論 ·········································································.1
1.1 研究背景和意義 ························································.1
1.2 研究現(xiàn)狀 ···································································.4
1.3 算法知識簡介 ···························································.6
1.3.1 算法及算法的計(jì)算復(fù)雜性 ···········································.6
1.3.2 P 類、NP 類及 NPC 類問題 ·········································.7
1.3.3 近似算法和近似性能比 ··············································.9
1.3.4 貪婪、局部搜索策略·················································10
1.4 本書的主要貢獻(xiàn) ························································11
1.4.1 化公共鄰接距離的基因組片段填充問題的 定義修正 ·····12
1.4.2 SF-MNCA 問題特殊實(shí)例的多項(xiàng)式時(shí)間精確算法 ················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 計(jì)算基因組學(xué)相關(guān)概念·············································17
2.2 鄰接、斷點(diǎn) ·······························································18
2.3 SF-MNCA 問題 ·························································22
2.4 封閉符號“#”··························································23
2.5 SF-MNCA 問題中的幾個(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 問題的 1.5-近似算法介紹 ··············47
4.1 引言 ··········································································47
4.2 公共鄰接數(shù)的一個(gè)上界·············································48
4.3 雙面填充算法 ···························································61
4.4 算法的時(shí)間復(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 改進(jìn)的近似下界 ······················································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 圖中的實(shí)現(xiàn)······················94
6.3.3 可傳遞約減算法的設(shè)計(jì)與實(shí)現(xiàn) ·····································95
6.4 實(shí)驗(yàn)及結(jié)果分析 ························································97
結(jié)束語 ··················································································101
參考文獻(xiàn) ··············································································105