計(jì)算基因組學(xué)中許多問題都是NP難問題,人們可以利用近似算法、啟發(fā)式算法、隨機(jī)算法來解決這些問題。但是,計(jì)算基因組學(xué)歸根究底的研究目的是為生物學(xué)、藥理學(xué)、病理學(xué)做貢獻(xiàn),這些領(lǐng)域關(guān)乎生命,所以問題的解必然是越精確越好。因此,參數(shù)化算法在解決計(jì)算基因組學(xué)問題時(shí)不失為一種好方法。對遺傳信息進(jìn)行數(shù)據(jù)分析之前,需要保證基因圖譜中沒有冗余數(shù)據(jù)和干擾數(shù)據(jù)。最長帶恢復(fù)問題（Maximal Strip Recovery,簡稱為MSR）就是對基因圖譜中的數(shù)據(jù)進(jìn)行處理,使之沒有錯(cuò)誤和模糊的干擾數(shù)據(jù)。其補(bǔ)問題（Complementary Maximal Strip Recovery,簡稱為CMSR）與其等價(jià)。本文主要針對CMSR問題進(jìn)行具體的核心化算法研究,提出了改進(jìn)的核心化算法,具體的研究內(nèi)容包括:首先,對于參數(shù)計(jì)算與復(fù)雜性理論的發(fā)展背景進(jìn)行了簡單的介紹,同時(shí)對于我們所研究的CMSR問題介紹了相關(guān)理論和技術(shù),比如參數(shù)算法和核心化技術(shù)的相關(guān)理論。其次,本文根據(jù)當(dāng)前關(guān)于CMSR問題最好結(jié)果的核心化思想,進(jìn)一步分析了 CMSR問題的結(jié)構(gòu)特性,提出了新的更有助于分析的輔助圖,我們在每一個(gè)同源塊之間生成邊而不是每個(gè)超級... 

【文章頁數(shù)】：59 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 研究背景
    1.2 研究內(nèi)容
    1.3 研究意義
    1.4 組織結(jié)構(gòu)
第二章 參數(shù)計(jì)算及核心化技術(shù)介紹
    2.1 參數(shù)計(jì)算及復(fù)雜性理論概述
    2.2 核心化技術(shù)介紹
        2.2.1 基于最大匹配的核心化技術(shù)
        2.2.2 線性規(guī)劃技術(shù)
        2.2.3 皇冠分解技術(shù)
        2.2.4 極值歸納技術(shù)
        2.2.5 隨機(jī)方法
    2.3 本章小結(jié)
第三章 最長帶恢復(fù)問題的42K核心化算法
    3.1 問題介紹
    3.2 核心化算法
        3.2.1 相關(guān)術(shù)語
        3.2.2 簡化規(guī)則
        3.2.3 核大小分析
    3.3 本章小結(jié)
第四章 最長帶恢復(fù)問題的26K核心化算法
    4.1 己有規(guī)則和相關(guān)術(shù)語
    4.2 新規(guī)則
    4.3 優(yōu)化的核
    4.4 本章小結(jié)
第五章 總結(jié)與展望
    5.1 主要貢獻(xiàn)和創(chuàng)新點(diǎn)
    5.2 展望
參考文獻(xiàn)
致謝
附錄A 攻讀碩士學(xué)位期間所發(fā)表的學(xué)術(shù)論文及成果
附錄B 攻讀碩士學(xué)位期間參加的項(xiàng)目


【參考文獻(xiàn)】：
期刊論文
[1]參數(shù)計(jì)算中核心化技術(shù)及其應(yīng)用[J]. 李紹華,王建新,馮啟龍,陳建二.  軟件學(xué)報(bào). 2009(09)
[2]P2-Packing問題參數(shù)算法的改進(jìn)[J]. 王建新,寧丹,馮啟龍,陳建二.  軟件學(xué)報(bào). 2008(11)



本文編號：3702836