單體型組裝問(wèn)題枚舉算法研究.pdf

1、分析和識(shí)別單體型對(duì)復(fù)雜疾病致病基因的精確定位有重要作用。單體型組裝問(wèn)題是利用個(gè)體DNA測(cè)序片段數(shù)據(jù)推出該個(gè)體一對(duì)單體型的計(jì)算問(wèn)題。根據(jù)不同的優(yōu)化準(zhǔn)則，單體型組裝問(wèn)題有最少SNP(Single Nucleotide Polymorphisms)位點(diǎn)刪除模型(Minimum SNP Removal，MSR)，最少片段刪除模型(Minimum Fragment Removal，MFR)和最少錯(cuò)誤更正模型(Minimum Error Corre

2、ction，MEC)等計(jì)算模型，這些模型旨在得到問(wèn)題的一個(gè)最優(yōu)解，即兩條單體型。對(duì)生物學(xué)家來(lái)說(shuō)，一個(gè)解對(duì)于復(fù)雜的生物問(wèn)題往往是不夠的。基于上述目的，本文為MSR、MFR和MEC設(shè)計(jì)了能給出多個(gè)最優(yōu)解的模型和相應(yīng)的參數(shù)化枚舉算法。
　　MSR模型是試圖刪除最少SNP位點(diǎn)來(lái)確定個(gè)體的單體型的計(jì)算問(wèn)題。在此基礎(chǔ)上，我們定義MSR的k枚舉模型(k-Minimum SNP Removal Enumeration，K_MSR):對(duì)于給定的一個(gè)

3、SNP矩陣M，一個(gè)小正整數(shù)k，為MSR模型枚舉最多k個(gè)解，即得到一個(gè)元素個(gè)數(shù)為k的最優(yōu)解的集合。我們?cè)O(shè)計(jì)求解K_MSR的算法的時(shí)間復(fù)雜度為O(nk1k2+nkk1+mlogm+mk1)，空間復(fù)雜度為O(nkk1)，其中m為片段數(shù)，n為SNP位點(diǎn)數(shù)，k1為單個(gè)片段覆蓋的最大SNP位點(diǎn)數(shù)，k2為覆蓋任意SNP位點(diǎn)的最大片段數(shù)。
　　MFR模型是試圖刪除最少片段來(lái)確定個(gè)體單體型的計(jì)算問(wèn)題，在MFR模型的定義的基礎(chǔ)上我們提出K_MFR(k

4、-Minimum Fragment Removal Enumeration)模型:給定一個(gè)SNP矩陣M和一個(gè)小正整數(shù)k，為MFR模型枚舉最多k個(gè)最優(yōu)解。我們?cè)O(shè)計(jì)求解該模型算法的時(shí)間復(fù)雜度為O(mkk22+mkk1k2+mlogm+nk2)，空間復(fù)雜度為O(mk1+mkk22)。在MEC模型定義的基礎(chǔ)上，我們提出MEC的k枚舉模型(k-Minimum Error Correction Enumeration，K_MEC)，并設(shè)計(jì)了時(shí)間復(fù)雜