公共鄰接距離基因組片段填充問題研究.pdf

1、近年來，隨著基因測(cè)序技術(shù)的發(fā)展，人們能夠獲得越來越多生物體的基因組，然而這些基因組并不完整。不完整的基因組被稱為基因組框架。在很多計(jì)算生物學(xué)研究領(lǐng)域，無法直接使用基因組框架進(jìn)行科學(xué)研究，可行的方法是將其補(bǔ)充完整再投入應(yīng)用，基因組片段填充問題由此產(chǎn)生，并逐漸成為計(jì)算生物學(xué)的一個(gè)熱門研究領(lǐng)域。片段填充問題通過參照相近物種的基因組來填充基因組框架，目的是使基因組框架變得完整并盡量接近原始的基因組信息。根據(jù)參照基因組的完整與否，片段填充問題又細(xì)

2、分為單面填充和雙面填充。
　　 在本文中，用一個(gè)字符表示一個(gè)基因家族，用字符串表示基因組。當(dāng)基因組中不包含重復(fù)出現(xiàn)的基因時(shí)，片段填充問題在斷點(diǎn)距離或DCJ距離下都是多項(xiàng)式時(shí)間可解的;當(dāng)基因組包含重復(fù)出現(xiàn)的基因時(shí)，片段填充問題在斷點(diǎn)距離或公共鄰接距離下都是NP-完全的。
　　 目前主要的研究都集中在一般情況下的包含重復(fù)基因的基因組片段填充問題上，即允許在基因組框架的同一個(gè)位置上連續(xù)填充任意多個(gè)基因。但是在實(shí)際的基因組填充計(jì)

3、算中，在同一個(gè)位置連續(xù)填充多個(gè)基因的情況并不多見，往往是在一個(gè)位置上填充1或2個(gè)基因，因此本文考慮下面的問題:在包含重復(fù)基因的基因組片段填充問題中，以公共鄰接數(shù)目作為基因組之間距離的度量，以最大化公共鄰接數(shù)為目的，如果填充長(zhǎng)度為l的字符串到基因組框架的同一位置使得公共鄰接數(shù)增加l+1，則l的取值僅為1或2。本文將該問題簡(jiǎn)稱為SF-MNCA(2)(Scaffold Filling to Maximize the Number of Com

4、mon Adjacencies)。文中對(duì)SF-MNCA(2)問題進(jìn)行了研究討論。本文的主要貢獻(xiàn)如下:
　　 (1)證明了SF-MNCA(2)是NP-完全問題。本文采用NP-完全性的理論證明方法，通過理論分析，找到適合用于歸約的已知NP-完全問題:3DM，通過將3DM問題在多項(xiàng)式時(shí)間內(nèi)歸約為單面SF-MNCA(2)問題，首次證明了單面SF-MNCA(2)是NP-完全的。
　　 (2)為單面SF-MNCA問題設(shè)計(jì)了簡(jiǎn)單的2-