基于貪心算法與最短路徑的基因組組裝最優(yōu)拼接問題

《基于貪心算法與最短路徑的基因組組裝最優(yōu)拼接問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、基于貪心算法與最小路徑的基因組組裝優(yōu)化問題摘要隨著人類基因組計(jì)劃的實(shí)施和飛速發(fā)展，基因組測序拼接作為生物信息學(xué)的核有著極其重要的應(yīng)用價值。新的測序技術(shù)大量涌現(xiàn)，產(chǎn)生的reads長度更短，數(shù)量更多，覆蓋率更大，能直接讀取的堿基對序列長度遠(yuǎn)小于基因組長度。本文通過如何在保證組裝序列的連續(xù)性、完整性和準(zhǔn)確性的同時設(shè)計(jì)耗時短、內(nèi)存小的組裝算法，建立數(shù)學(xué)模型來解決基因組組裝問題。針對問題一，首先，利用相應(yīng)的軟件對原基因組G進(jìn)行切割，利用全基因鳥槍法測序?qū)η懈詈蟮亩袒蜻M(jìn)行測序，得到較小的基因組,通過對比多條任意切割后相似的基因組從而找出個別堿基對存在的識別錯誤。而對于基因組中存

2、在的重復(fù)片段可以通過兩個read之間的DNA片段的長度滿足一定的分布規(guī)律即paredendread來解決。接下來對比任意兩個和是否相等，通過MATLAB軟件建立nm階的關(guān)聯(lián)矩陣，最后利用圖論中的最短路徑方法使更多的基因組能拼接在一起，盡可能使拼接出來的基因組在原基因組的覆蓋率達(dá)到最大。針對問題二，先把附件給出的數(shù)據(jù)提取出來導(dǎo)入MATLAB中，再結(jié)合問題一給出的模型對基因組進(jìn)行重組，從而得到新的基因。最后，基于對基因組組裝的研究，為使重組基因能更接近原基因序列，對問題一提出模型進(jìn)行合理性的評價。關(guān)鍵詞：基因組組裝全基因鳥槍法測序貪心算法最短路徑一、問題的重述1.1問題背

3、景快速和準(zhǔn)確地獲取生物體的遺傳信息對于生命科學(xué)研究具有重要的意義。對每個生物體來說，基因組包含了整個生物體的遺傳信息，這些信息通常由組成基因組的DNA或RNA分子中堿基對的排列順序所決定。獲得目標(biāo)生物基因組的序列信息，進(jìn)而比較全面地揭示基因組的復(fù)雜性和多樣性，成為生命科學(xué)領(lǐng)域的重要研究內(nèi)容。1.2問題提出確定基因組堿基對序列的過程稱為測序（sequencing）。測序技術(shù)始于20世紀(jì)70年代，伴隨著人類基因組計(jì)劃的實(shí)施而突飛猛進(jìn)。從第一代到現(xiàn)在普遍應(yīng)用的第二代，以及近年來正在興起的第三代，測序技術(shù)正向著高通量、低成本的方向發(fā)展。盡管如此，目前能直接讀取的堿基對序列長度

4、遠(yuǎn)小于基因組序列長度，因此需要利用一定的方法將測序得到的短片段序列組裝成更長的序列。通常的做法是，將基因組復(fù)制若干份，無規(guī)律地分?jǐn)喑啥唐魏筮M(jìn)行測序，然后尋找測得的不同短片段序列之間的重合部分，并利用這些信息進(jìn)行組裝。例如，若有兩個短片段序列分別為ATACCTTGCTAGCGTGCTAGCGTAGGTCTGA則有可能基因組序列中包含有ATACCTTGCTAGCGTAGGTCTGA這一段。當(dāng)然，由于技術(shù)的限制和實(shí)際情況的復(fù)雜性，最終組裝得到的序列與真實(shí)基因組序列之間仍可能存在差異，甚至只能得到若干條無法進(jìn)一步連接起來的序列。對組裝效果的評價主要依據(jù)組裝序列的連續(xù)性、完整

5、性和準(zhǔn)確性。連續(xù)性要求組裝得到的（多條）序列長度盡可能長；完整性要求組裝序列的總長度占基因組序列長度的比例盡可能大；準(zhǔn)確性要求組裝序列與真實(shí)序列盡可能符合。利用現(xiàn)有的測序技術(shù)，可按一定的測序策略獲得長度約為50–100個堿基對的序列，稱為讀長（reads）?；蚪M復(fù)制份數(shù)約為50–100?；蚪M組裝軟件可根據(jù)得到的所有讀長組裝成基因組，這些軟件的核心是某個組裝算法。常用的組裝算法主要基于OLC（Overlap/Layout/Consensus）方法、貪婪圖方法、deBruijn圖方法等。一個好的算法應(yīng)具備組裝效果好、時間短、內(nèi)存小等特點(diǎn)。新一代測序技術(shù)在高通量、低成本

6、的同時也帶來了錯誤率略有增加、讀長較短等缺點(diǎn)，現(xiàn)有算法的性能還有較大的改善空間。具體解決問題如下：問題一：試建立數(shù)學(xué)模型，設(shè)計(jì)算法并編制程序，將讀長序列組裝成基因組。你的算法和程序應(yīng)能較好地解決測序中可能出現(xiàn)的個別堿基對識別錯誤、基因組中存在重復(fù)片段等復(fù)雜情況。問題二：現(xiàn)有一個全長約為120,000個堿基對的細(xì)菌人工染色體（BAC），采用Hiseq2000測序儀進(jìn)行測序，測序策略以及數(shù)據(jù)格式的簡要說明見附錄一和附錄二，測得的讀長數(shù)據(jù)見附錄三，測序深度（sequencingdepth）約為70×，即基因組每個位置平均被測到約70次。試?yán)媚愕乃惴ê统绦蜻M(jìn)行組裝，并使之具

7、有良好的組裝效果。二、問題分析2.1問題一分析本題要求我們的算法和程序應(yīng)能較好地解決測序中可能出現(xiàn)的個別堿基對識別錯誤、基因組中存在重復(fù)片段等復(fù)雜情況。故在下列分別對個別堿基識別錯誤和基因組中存在重復(fù)片段進(jìn)行分析。2.1.1個別堿基對識別錯誤分析read中每一個堿基都有一個質(zhì)量值，來表示該堿基被正確測出的概率。一般來說，5'端的堿基正確的概率較大，而3'端1到3個堿基可能是錯誤的。這就要求拼接軟件在拼接時能夠糾錯，但是，可糾錯的軟件也可能把正確的堿基當(dāng)作錯誤來糾正。所以不僅要求拼接軟件在拼接時能夠糾錯，盡可能多的發(fā)現(xiàn)真正的錯誤，而且要求拼接軟件盡可能