發(fā)布時(shí)間：2020-08-15 14:33

【摘要】：基因組重組,包含了移位、轉(zhuǎn)位、翻轉(zhuǎn)等基本操作,造成了基因組上基因排列順序的變換。基因重組排序問(wèn)題是生物信息學(xué)中的經(jīng)典問(wèn)題之一,即探索不同基因組序列之間的重組過(guò)程并計(jì)算其最少重組次數(shù)。最少重組次數(shù)就意味著通過(guò)最少的基因重組操作完成兩個(gè)基因組的相互轉(zhuǎn)化,這對(duì)于推斷物種的演化過(guò)程,獲得物種間關(guān)系有重要意義。基因組重組排序問(wèn)題的研究開(kāi)始于20世紀(jì)90年代。1993年,Sankoff等人首次定義了基因翻轉(zhuǎn)排序問(wèn)題,并且提出了一個(gè)解決翻轉(zhuǎn)排序問(wèn)題的貪心算法。1997年,Capara將最大歐拉圈分解問(wèn)題規(guī)約到無(wú)向基因組的翻轉(zhuǎn)排序問(wèn)題,從而證明了無(wú)向基因組的翻轉(zhuǎn)排序問(wèn)題是NP-hard的。2001年,Bader設(shè)計(jì)了一個(gè)可以獲得翻轉(zhuǎn)后基因序列,并計(jì)算翻轉(zhuǎn)距離的算法。在2015年,Shao等人提出了一個(gè)運(yùn)行時(shí)間更短的能夠測(cè)算模擬基因序列的斷點(diǎn)距離的算法,之后一年,他們又將算法應(yīng)用到了有重復(fù)基因的模擬基因組數(shù)據(jù)之上。2018年,Zhai等人為帶重復(fù)基因的基因組翻轉(zhuǎn)排序問(wèn)題設(shè)計(jì)了一個(gè)近似性能比為4的近似算法。但是,之前有關(guān)基因組重組的研究大都停留在理論或者模擬數(shù)據(jù)上,并不能通過(guò)重組排序的操作分析真實(shí)基因組上各個(gè)染色體之間的潛在關(guān)系。并且,之前重組排序的研究很少涉及到重復(fù)片段序列上,從而探索染色體上重復(fù)片段的關(guān)系。重復(fù)片段作為基因組中發(fā)生基因重組和基因突變的熱點(diǎn)區(qū)域,研究重復(fù)片段中的基因組重組操作對(duì)探索基因組進(jìn)化歷程具有重要意義。隨著測(cè)序技術(shù)的提高,目前很多大型基因組中的重復(fù)片段信息都已經(jīng)被檢測(cè)并公開(kāi)。本文的研究將基因組重組模型擴(kuò)展至真實(shí)基因組數(shù)據(jù)的重復(fù)片段序列上,研究不同基因組的重復(fù)片段之間的重組過(guò)程,進(jìn)而分析物種間的進(jìn)化距離。本文利用最新重復(fù)片段檢測(cè)算法SDquest識(shí)別出不同基因組之間共有的重復(fù)片段信息,并設(shè)計(jì)合理的算法計(jì)算兩個(gè)基因組重復(fù)片段序列間的重組操作過(guò)程以及次數(shù)。本文的研究目標(biāo)是通過(guò)盡可能少的基因組重組操作,消除兩條序列之間的所有斷點(diǎn)。本文用人類與猩猩真實(shí)基因組數(shù)據(jù)進(jìn)行實(shí)驗(yàn),分析可能影響種族關(guān)系的對(duì)應(yīng)染色體。本文給出的實(shí)現(xiàn)過(guò)程如下所示:(1)將SDquest的識(shí)別結(jié)果對(duì)重復(fù)片段進(jìn)行編號(hào),從而將染色體序列建模成重復(fù)片段序列。并且引入了鄰接塊的概念,對(duì)序列進(jìn)行分塊,減少重組操作過(guò)程中破壞的鄰接。(2)設(shè)計(jì)了一個(gè)利用貪心策略的刪除算法,通過(guò)比較位置得分,刪除數(shù)量不對(duì)稱的重復(fù)片段;將兩條序列鄰接塊分成同位置匹配、異位置匹配和特殊情況(插入),并設(shè)計(jì)了一個(gè)翻轉(zhuǎn)算法,消除序列之間的所有斷點(diǎn),同時(shí)記錄重組的過(guò)程。(3)將人類和猩猩最新染色體數(shù)據(jù)進(jìn)行分組實(shí)驗(yàn),并對(duì)結(jié)果的重組操作次數(shù)進(jìn)行統(tǒng)計(jì)與分析。本文的主要?jiǎng)?chuàng)新點(diǎn):1.設(shè)計(jì)并且實(shí)現(xiàn)一個(gè)基于貪婪策略的刪除算法,以刪除人類與猩猩染色體中不對(duì)稱的重復(fù)片段信息。2.實(shí)現(xiàn)近似性能比為4的翻轉(zhuǎn)排序算法,消除兩個(gè)基因組重復(fù)片段序列的所有斷點(diǎn),匹配兩條序列間的所有鄰接。3.將重組排序問(wèn)題擴(kuò)展到人類和猩猩基因組的重復(fù)片段上,設(shè)計(jì)合理的重組排序模型,并利用重組排序算法計(jì)算人與猩猩基因組中重復(fù)片段的重排次數(shù),以此來(lái)近似估計(jì)物種間的進(jìn)化距離。
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：Q811.4;TP301.6
【圖文】：

基因組中的重復(fù)片段是以鑲嵌結(jié)構(gòu)存在的，這就意味著基因組中的？組重復(fù)逡逑片段可能由一塊或者多塊重復(fù)片段拼接而成。如果直接將ＳＵｑｕｅｓｔ中識(shí)別的重復(fù)逡逑片段進(jìn)行賦值，會(huì)導(dǎo)致建模出現(xiàn)錯(cuò)誤，如遺漏掉一部分重復(fù)片段等。因此，需要逡逑將每一個(gè)嵌套重復(fù)片段中拼接的部分識(shí)別出來(lái)，根據(jù)每個(gè)嵌套部分進(jìn)行切塊，之逡逑后根據(jù)切塊的相似性等特征進(jìn)行賦值，最終完成建模。建模的過(guò)程如下所述：逡逑２．１．邋１重復(fù)片段的合并逡逑為了識(shí)別序列中的嵌套重復(fù)片段，算法將每一個(gè)重復(fù)片段看作是基因組中的逡逑－個(gè)丨ｘ：間，這樣根據(jù)Ｍ復(fù)片段的位置，每一個(gè)重復(fù)片段被標(biāo)記在整個(gè)基因組區(qū)間逡逑中。在基因組中，如果兩個(gè)重復(fù)片段區(qū)間之間是重疊的．或者兩個(gè)重復(fù)片段之間逡逑的距離不超過(guò)設(shè)定的參數(shù)（默認(rèn)為0ｂＰ），那么將其合并，得到一個(gè)更大的區(qū)間。逡逑當(dāng)每一個(gè)區(qū)間個(gè)能再擴(kuò)張時(shí)，它將成為一個(gè)新的重復(fù)片段區(qū)間。合并之后的結(jié)果逡逑如圖２－１所示。逡逑■■■■■邐Ｉ邐１邐■■■■■■邐ｒ—ｒｒｎ逡逑

找與此對(duì)應(yīng)的重復(fù)片段進(jìn)行重復(fù)的編號(hào)，同時(shí)，如果此編號(hào)的部分將嵌套的重復(fù)逡逑片段分割，那就將分割的剩余部分進(jìn)行分塊與編號(hào)。不斷的重復(fù)上述過(guò)程，直至逡逑所有的重復(fù)片段完成分割與編號(hào)。如圖２－２所示例子中，選取最短的重復(fù)片段區(qū)逡逑間進(jìn)行編號(hào)為Ｃ，并將與之對(duì)應(yīng)的部分都編號(hào)為Ｃ，之后將其存在的嵌套重復(fù)片逡逑段進(jìn)行分塊并且編號(hào)為Ｂ、Ｄ，Ｆ、Ｇ。這就完成了所有重復(fù)片段的編號(hào)。逡逑；ｂ邋；邐ｃ邐；邋ｄ邐；邐｜ｆ；邐ｃ邐Ｉ邋ｇ邐Ｉ邐Ｉ邐ｂ邐Ｉ邋ｃ邋Ｉｄ；邐ｉ邋ｆ邋；邐ｃ邐；ｇ；逡逑……ｉ；．邋ｎ？；邐

找與此對(duì)應(yīng)的重復(fù)片段進(jìn)行重復(fù)的編號(hào)，同時(shí)，如果此編號(hào)的部分將嵌套的重復(fù)逡逑片段分割，那就將分割的剩余部分進(jìn)行分塊與編號(hào)。不斷的重復(fù)上述過(guò)程，直至逡逑所有的重復(fù)片段完成分割與編號(hào)。如圖２－２所示例子中，選取最短的重復(fù)片段區(qū)逡逑間進(jìn)行編號(hào)為Ｃ，并將與之對(duì)應(yīng)的部分都編號(hào)為Ｃ，之后將其存在的嵌套重復(fù)片逡逑段進(jìn)行分塊并且編號(hào)為Ｂ、Ｄ，Ｆ、Ｇ。這就完成了所有重復(fù)片段的編號(hào)。逡逑；ｂ邋；邐ｃ邐；邋ｄ邐；邐｜ｆ；邐ｃ邐Ｉ邋ｇ邐Ｉ邐Ｉ邐ｂ邐Ｉ邋ｃ邋Ｉｄ；邐ｉ邋ｆ邋；邐ｃ邐；ｇ；逡逑……ｉ；．邋ｎ？；邐

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 冉金玉;張新功;;總加權(quán)誤工損失的兩個(gè)代理單機(jī)排序問(wèn)題[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2019年01期

2 韓飛;;高中數(shù)學(xué)一道數(shù)列典型題解法的探究[J];數(shù)學(xué)學(xué)習(xí)與研究;2016年23期

3 豆俊梅;孫彩賢;;單機(jī)排序問(wèn)題的研究[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年24期

4 胡覺(jué)亮;楊佳雯;蘇曉彤;董建明;;機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問(wèn)題[J];浙江理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年06期

5 仲維亞;馬曉茹;;帶有運(yùn)輸且加工具有靈活性的無(wú)等待流水作業(yè)排序問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2016年04期

6 隋楠;羅成新;;具有維護(hù)活動(dòng)及公共工期的加工時(shí)間依賴資源的單機(jī)排序問(wèn)題[J];沈陽(yáng)航空航天大學(xué)學(xué)報(bào);2016年06期

7 林浩;何程;;關(guān)于工期分配與加權(quán)誤工數(shù)的雙指標(biāo)排序問(wèn)題（英文）[J];工程數(shù)學(xué)學(xué)報(bào);2017年01期

8 趙傳立;張蕾;;帶有交貨期窗口和加工時(shí)間可控的排序問(wèn)題[J];沈陽(yáng)師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期

9 王申重;杜海龍;;具有學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的單機(jī)排序問(wèn)題研究[J];棗莊學(xué)院學(xué)報(bào);2017年02期

10 陳蕾;張安;陳永;陳光亭;;資源定時(shí)投放的單機(jī)排序問(wèn)題[J];杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年02期

相關(guān)會(huì)議論文 前10條

1 張蓮珠;;關(guān)于六角鏈的極值和排序問(wèn)題的一些結(jié)果[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

2 呂緒華;楊漢興;;求解裝配式排序問(wèn)題的歸并算法及其性能比研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問(wèn)題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問(wèn)題[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

5 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

6 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

7 胡榮;呂緒華;;3TMF排序問(wèn)題的計(jì)算復(fù)雜性及分支定界法[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

8 柏孟卓;唐國(guó)春;;加工時(shí)間可控的同時(shí)加工排序問(wèn)題[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

9 樊保強(qiáng);;帶倉(cāng)儲(chǔ)約束的準(zhǔn)時(shí)排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

10 吳翠連;;有尺寸的單機(jī)分批排序問(wèn)題的近似算法[A];中國(guó)企業(yè)運(yùn)籌學(xué)[2011（1）][C];2011年

相關(guān)重要報(bào)紙文章 前3條

1 楊文波;淺談方位詞“東、西、南、北”的詞語(yǔ)排序問(wèn)題[N];語(yǔ)言文字周報(bào);2018年

2 山東 趙玉勇;小博士編程[N];電腦報(bào);2004年

3 何靖;全國(guó)計(jì)算機(jī)應(yīng)用技術(shù)證書(shū)考試（NIT）[N];中國(guó)電腦教育報(bào);2003年

相關(guān)博士學(xué)位論文 前10條

1 李融奇;在線排序和批排序問(wèn)題研究[D];浙江大學(xué);2018年

2 沈佳煜;不確定情形下若干排序問(wèn)題的研究[D];南京理工大學(xué);2017年

3 高園;新型排序問(wèn)題的計(jì)算復(fù)雜性研究[D];鄭州大學(xué);2018年

4 殷娜;依賴于資源分配的排序問(wèn)題研究[D];上海大學(xué);2015年

5 李好好;若干排序問(wèn)題研究[D];浙江大學(xué);2014年

6 王吉波;工件加工時(shí)間可變的現(xiàn)代排序問(wèn)題[D];大連理工大學(xué);2005年

7 羅潤(rùn)梓;平行機(jī)半在線排序問(wèn)題[D];上海大學(xué);2005年

8 季敏;當(dāng)代工業(yè)中的若干排序問(wèn)題研究[D];浙江大學(xué);2006年

9 葉德仕;通訊網(wǎng)絡(luò)中排序問(wèn)題的若干在線和高性能算法[D];浙江大學(xué);2005年

10 李文華;關(guān)于分批排序問(wèn)題的研究[D];鄭州大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 曹移林;平行多階段作業(yè)排序問(wèn)題的研究[D];華東理工大學(xué);2019年

2 王亞男;具有退化維護(hù)和資源分配的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2019年

3 李石;與資源相關(guān)加工時(shí)間可變的單機(jī)排序問(wèn)題[D];沈陽(yáng)師范大學(xué);2019年

4 姜曉燕;MapReduce排序問(wèn)題的若干算法研究[D];北京郵電大學(xué);2019年

5 康宇紅;具有錯(cuò)位限制的重新排序問(wèn)題研究[D];重慶師范大學(xué);2019年

6 羅鼎暉;大金山島不同植物群落下土壤動(dòng)物群落特征[D];華東師范大學(xué);2019年

7 郭亞敏;飼糧能量水平對(duì)藏羊瘤胃氮素轉(zhuǎn)運(yùn)及利用效率的影響[D];蘭州大學(xué);2019年

8 王睿智;基因組比較分析的算法與軟件[D];山東大學(xué);2019年

9 叢穩(wěn);工件可拒絕的單機(jī)重新排序問(wèn)題[D];鄭州大學(xué);2019年

10 潘婷婷;帶資源、學(xué)習(xí)效應(yīng)、惡化效應(yīng)、維護(hù)活動(dòng)和工期窗口的排序問(wèn)題的研究[D];蘇州大學(xué);2018年

本文編號(hào)：2794243