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

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

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

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

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