基于DP的若干序列比對(duì)算法構(gòu)件開發(fā)及其裝配生成

發(fā)布時(shí)間：2020-07-04 12:14

【摘要】：序列比對(duì)是一種通過排列基因組序列來識(shí)別序列相似性區(qū)域,從而獲得待比對(duì)序列之間的功能、結(jié)構(gòu)或進(jìn)化關(guān)系的技術(shù)。隨著人類基因組計(jì)劃的實(shí)施,測(cè)序技術(shù)的發(fā)展產(chǎn)生了大量的有關(guān)生物分子的原始序列數(shù)據(jù),面對(duì)如此豐富的基因組序列數(shù)據(jù),如何去高效處理和分析這些數(shù)據(jù),比較兩序列之間的相似區(qū)域和保守性位點(diǎn),尋求序列同源結(jié)構(gòu),揭示生物遺傳、變異和進(jìn)化等問題,成為了序列比對(duì)算法研究的主要?jiǎng)恿χ�。目�?比對(duì)算法的研究大部分集中于序列比對(duì)算法問題域中的特定問題或者特定算法優(yōu)化,而較少面向于整個(gè)序列比對(duì)算法問題域,難以得到一個(gè)具有更高抽象層次且適用于序列比對(duì)算法問題域的算法構(gòu)件庫,在一定程度上導(dǎo)致了序列比對(duì)算法的冗余性以及人為選擇算法可能造成的誤差等問題,也使得人們難以有效地了解算法結(jié)構(gòu),無法保證算法的正確使用,甚至于降低了序列比對(duì)結(jié)果的準(zhǔn)確性。由于現(xiàn)有算法的專用性和低抽象性,不僅導(dǎo)致研究人員需要花費(fèi)大量時(shí)間去學(xué)習(xí)和使用該類算法,降低了算法的可維護(hù)性和復(fù)用性,而且難以定位和解決算法產(chǎn)生的錯(cuò)誤,加重了序列相似性分析的負(fù)擔(dān)。通過深入分析基于動(dòng)態(tài)規(guī)劃的雙序列比對(duì)算法(Dynamic Programming-based Pairwise Sequence Alignment Algorithm,DPPSAA)領(lǐng)域,利用產(chǎn)生式編程方法設(shè)計(jì)并建立了DPPSAA領(lǐng)域特征模型,其中主要包含特征模型和特征交互模型。然后利用PAR平臺(tái)的高抽象程序設(shè)計(jì)語言Apla將上述領(lǐng)域特征模型中的特征作為構(gòu)件進(jìn)行形式化實(shí)現(xiàn),并詳細(xì)敘述了實(shí)現(xiàn)過程,建立了一個(gè)基于Apla程序的高抽象性的DPPSAA構(gòu)件庫,展示了基于該構(gòu)件庫裝配形成Needleman-Wunsch算法的具體步驟。同時(shí),利用PAR平臺(tái)的C++程序轉(zhuǎn)換系統(tǒng),通過手動(dòng)和自動(dòng)結(jié)合的方式將上述構(gòu)件庫轉(zhuǎn)換成為相對(duì)應(yīng)的C++程序代碼,并裝配實(shí)現(xiàn)和運(yùn)行了Needleman-Wunsch算法,結(jié)果表明通過DPPSAA構(gòu)件庫具有一定的實(shí)用性,在算法學(xué)習(xí)和實(shí)現(xiàn)方面有一定優(yōu)勢(shì),為形式化裝配實(shí)現(xiàn)序列比對(duì)算法提供了可能。之后以DPPSAA構(gòu)件庫為基礎(chǔ),改進(jìn)和增加了部分構(gòu)件庫構(gòu)件,使其能夠支持裝配基于DPPSAA構(gòu)件庫的多序列比對(duì)領(lǐng)域算法,并利用該擴(kuò)充構(gòu)件庫,裝配并實(shí)現(xiàn)了星比對(duì)算法,實(shí)驗(yàn)結(jié)果表明裝配生成的星比對(duì)算法具有一定的實(shí)用性,不僅驗(yàn)證了DPPSAA構(gòu)件庫的復(fù)用性,且擴(kuò)充了DPPSAA領(lǐng)域構(gòu)件的適用范圍。
【學(xué)位授予單位】：江西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：Q811.4;TP301.6
【圖文】：