分別以連鎖不平衡及拉式鬆弛法 選取代表性單核苷酸多型性之研究

Presentation on theme: "分別以連鎖不平衡及拉式鬆弛法 選取代表性單核苷酸多型性之研究"— Presentation transcript:

1 分別以連鎖不平衡及拉式鬆弛法 選取代表性單核苷酸多型性之研究
指導老師: 王逸琳　教授 　　　　　李宇欣　教授 　　　　　蔡青志　教授 　　　　　洪一薰　教授 　　　　　黃耀廷　教授 　報告者: 馬家宜 各位老師好,我的論文主題是…..

2 大綱 簡介 研究問題 文獻回顧 求解演算法 總結 研究背景& 動機 生物資訊背景 tagSNP選取問題 集合涵蓋問題
在文獻回顧部分 著重於 Diversity Block LD以及tagSNP的介紹 最後講到求解此為題的多重解, 介紹求解的演算法步驟及範例 NCKU _IIM_2008/05/30_大綱

3 簡介

4 研究背景 SNP (Single Nucleotide Polymorphism) Haplotype 人類基因組計畫 DNA,蛋白質序列
生物資訊的應用 SNP (Single Nucleotide Polymorphism) 單核苷酸多型性 在DNA序列上單一核苷酸鹼基對發生的變異 出現頻率超過1% Haplotype 相鄰的SNP鹼基所組成之序列 在背景部份,首先我先介紹一下何謂SNP,SNP就是單核甘酸多型性,他指的是DNA序列上單一個鹼基發生變異.在人類基因序列中出現的頻率很高 若將相鄰的SNP串成一序列則稱為Haplotype (由於人類基因組計畫的完成,生物資訊領域成為熱門的研究議題 研究一開始著重於如何儲存DNA RNA 蛋白質序列等各式各樣的生物資訊 接著,將重點轉至如何從這些資料中找到有用的資訊, 藉由分析資訊找出影響及病的問題所在 為幫助接下來了解研究問題,首先介紹幾個常用的專有名詞 DNA, variations, mutations, SNP, haplotype) NCKU _IIM_2008/05/30_簡介_研究背景

5 Chromosome 1 Chromosome 1a Chromosome 1b Individual 1 Individual 2
Locus 1 Locus 8 Chromosome 1 Chromosome 1a Chromosome 1b Locus Individual 1 Individual 2 Individual 3 Individual 4 −A T T C G G A G − −A T T T G G A C − −A A T C G G A C − −A T T C G G A C − Haplotype 1 Haplotype 2 Haplotype 3 Haplotype 4 T C G T T C A C C T C C 以圖來說明,投影片上是一個雙套染色體1,,將它拆解成單套染色體1a 及1b 從染色體1a中擷取基因座locus1 到locus8,按照此序列排列如下 取4個不同個體在此段locus的資料 在這些序列中發現 locus 2 ,4, 8 有變異的情形, 這些即稱為SNP 分標示1 2 3 將這些SNP排列在一起,即成為haplotype如右圖 SNP1 SNP2 SNP3 NCKU _IIM_2008/05/30_簡介_研究背景

6 研究動機 SNP是DNA序列上最常見的一種遺傳變異 應用於病理研究，提升醫療防治 SNP資料十分龐大
選取出部分具代表性SNP (稱為tagSNP) 提升資料庫的處理效率 減少儲存空間 縮短搜尋時間 接下來介紹我的研究動機 由於SNP是最常見的遺傳變異,且由SNP組成的haplotype對於研究疾病上時分有幫助 但是因為SNP的資料很多,目前發現的SNP數量已超過400萬筆,對如此龐大的資料作應用會造成資料處理上的困難 且由相關研究發現, 其實僅需要SNP中的一部分,就能透露大部分的資訊,將這些SNP稱為tagSNP 透過選取tagSNP可減少資料的儲存空間,且在後續應用上會縮短搜尋時間,大大提升資料庫的處理效率,因此衍生出選取tagSNP的議題 且由於使用的目的不同,tagSNP的定義也會有所不同,本研究採用tagSNP是用於辨識Haplotype序列樣式的差異 NCKU _IIM_2008/05/30_簡介_研究動機

7 研究問題 接下來講解我的研究問題

8 tagSNPSP 問題描述 選取一組元素個數最少之SNP的子集合，使其可辨識所有不同的Haplotype樣式 1 2 3 4 5 6 7 8
9 10 1 4 9 1 6 h1 1 1 投影片上看到的是四筆包含10個SNP的Halotype資料,由於每個基因座位置上不是AT就是CG,因此可以用只包含0,1的二元資料表示 假設我手上有一筆資料hi,以往要知道hi位於資料庫中的哪裡時,必須逐一比對,以投影片上的例子來看,必須比對40次 倘若從中選出…. 因此我的研究問題就是要找到最少個數且可辨識所有不同Haplotype樣式的SNP的子集合, h2 1 1 h3 1 1 1 h4 1 1 1 1 1 1 hi 1 NCKU _IIM_2008/05/30_研究問題 (tagSNP Selection Problem )

9 問題模式- tagSNPSP 轉為數學模式 給定 n 個SNP組成之Haplotype序列 m 筆 轉為二元矩陣資料
對一組Haplotype pair比對單點SNP 將他轉為數學模型,首先用m乘n的二元矩陣資料表示全部的序列, 為辨識Haplotype之差異,定義辨識的變數…. E1,2 NCKU _IIM_2008/05/30_問題模式 (tagSNP Selection Problem )

10 也就是說…. 矩陣ES為一個adjacency matrix,將此轉換成圖形後就是一個bipartite graph 我的問題就是要以最少個S節點連結到所有的E節點 NCKU _IIM_2008/05/30_問題模式 (tagSNP Selection Problem )

11 PtagSNP 模式 也就是說,我…. 以數學模式表示整個問題,每個xj便是代表是否選取SNPj,目標式是最小化Xj個數,限制式的意義是代表每個E節點至少要被S節點連結一次 若將每個S節點可連結到的E節點視為一個集合,此問題可視為一個SCP,SCP在1979年已被證實是一個NP-complete的問題,無法在多項式時間內獲得最佳解,加上此問題是包含多重最佳解 因此我的論文主要分成兩個方向,第一個是在小規模問題上,從多個最佳解中找到一個更具生物意義的推薦解 在大規模問題上則是發展一個具有較高效率的求解演算法 NCKU _IIM_2008/05/30_問題模式 (tagSNP Selection Problem )

12 文獻回顧

13 生物背景應用 限制Diversity與Block結構 Block1 Block2 Block3 首先講解依下Block結構
NCKU _IIM_2008/05/30_文獻回顧_生物背景應用

14 Linkage Disequilibrium (LD)
連鎖不平衡 任兩個基因座具某種關連程度 重組率很大(≃ 0.5)時，LD 隨代數的增加而減小 重組率很小(≃ 0)，LD 將持續很多代 計算LD值之方法 Devlin and Risch(1995) 關係係數 r2 (其值介於0~1) 標準化的連鎖不平衡參數 D́ (其值介於 -1~1) linkage disequilibrium,連鎖不平衡,簡稱LD 由於DNA序列中,任兩個基因座上的等位基因不是隨機分配.具有某種關連程度,此現象稱之為LD 若序列中具有LD,在重組率很大時….. 反之…… NCKU _IIM_2008/05/30_文獻回顧_生物背景應用

15 Haplotype Block之定義 tagSNP之定義
限制Haplotype diversity (Patil et al., 2001) LD-based Blocks (Gabriel et al., 2002) 過去發生重組之資料 (Wang et al., 2002) tagSNP之定義 辨識Haplotype樣式 (Patil et al., 2001) 符合Diversity之門檻值 (Johnson et al., 2001) LD-bin (Carlson et al., 2004) 由於原始的Haplotype序列龐大,如果直接對此Haplotype作研究十分不易 因此許多學者參考了一些生物概念衍伸出多種不同的Bloke定義 投影片上是比較常見的定義 本研究採用的是第一種也就是限制每個bloke的divesity至少要超過某一定定之比例 在選取tagSNP上,由於不同的使用目的也延伸出多種不同的定義 投影片上是最常看見的3種定義,本研究採用的是第一種定義,也就是辨識不同的haplotype樣式 NCKU _IIM_2008/05/30_文獻回顧_生物背景應用

16 tagSNP選取問題文獻 相關問題模式 極大化可擷取的序列資訊 (Bafna et al., 2003)
最小化tagSNP數 (Ke & Cardin, 2003) 切割Block (限制Diversity ) ，最小化 tagSNP數 (Patil et al., 2001; Zhang et al., 2002) 涵蓋最大的Haplotype序列 (Zhang & Jin, 2003) 最大化Haplotype資訊 (Zhang et al., 2002a; Weale et al., 2003) 預測Haplotype序列 (Halperin et al., 2005) 因為上述多種不同的Bloke與tagSNP定義,因此多位學者以不同的角度切入選取tagSNP問題 本研究的選取問題與patil&Zhang這兩位學者的題目定義最相近, 不同處在於本研究不考慮的haolotype切割問題,而是直接對已經切割後的結果去做選取的問題 NCKU _IIM_2008/05/30_文獻回顧_tagSNP選取問題文獻

17 求解方法與結果 已給定切割為Block之資訊
列舉的方式(simple numerical algorithm) (Avi-Itzhak et al., 2003) 完全辨識：非洲人→節省25%的SNP 高加索人→節省36%之SNP 不完全辨識：非洲人→節省38%的SNP 高加索人→節省49%之SNP 兩種貪婪演算法 (Huang et al., 2005) 求解品質與效率極佳 遺漏部分資訊：Greedy2優於Greedy1 在求解方法上 多位學者提出多種不同的演算法,在此不逐一細說,其中值得注意的現象是 NCKU _IIM_2008/05/30_文獻回顧_tagSNP選取問題文獻

18 切割Block之方法 貪婪演算法 (Patial et al.,2001) 動態規劃 (Zhang et al.,2002)
24047個SNP：4135個Block 　　　　　　 　tagSNP → 4563個SNP 動態規劃 (Zhang et al.,2002) 24047個SNP：2575個Block 　　　　　　 　tagSNP → 3562個SNP Block切割差異影響tagSNP之選取結果 Patil & Zhang他們模擬相同資料,由他們的求解結果可推論當Bloke數切的越多,代表每一Bloke中的資料較少,因此對此Bloke作tagSNP的選取相對而言求解速度較快,其結果也較佳,但當Bloke切割越多,一般而言,總tagSNP選取數量也會相對增加 NCKU _IIM_2008/05/30_文獻回顧_tagSNP選取問題文獻

19 集合涵蓋問題 Set Covering Problem（SCP） 問題簡介
NP-complete（Garey and Johnson, 1979） 模式 PSCP 由於tagSNP問題換個角度來看可是為一個set covering問題,因此統整部份SCP的相關文獻 首先先概數一下什麼式set covering問題,由图中 NCKU _IIM_2008/05/30_文獻回顧_集合涵蓋問題

20 求解方法 啟發式演算法 使用上下界夾擠之方法尋找精確解 貪婪演算法(Chvatal,1979；Slavík,1996)
機率演算法(Feo et al.,1989) 類神經網路法(Hifi et al., 2000；Ohlsson et al., 2001) 基因演算法(Al-Sultan,1996) 使用上下界夾擠之方法尋找精確解 上界 → 任意一組可行解 下界 → 放鬆問題 (Relaxation) NCKU _IIM_2008/05/30_文獻回顧_集合涵蓋問題

21 拉氏鬆弛法( Ceria et al., 1998；Haddadi, 1997；
Caprara et al., 1999) 保持原整數變數之限制條件 放鬆整個限制式→移至目標式 次梯度法(subgradient) 線性鬆弛法 放鬆整數變數之限制條件 目標式與其他限制式不變 NCKU _IIM_2008/05/30_文獻回顧_集合涵蓋問題

22 Multi-TagSNP演算法 (多重解)
文獻回顧介紹到此,接下來介紹我的第一個演算法MultiTagSNP,發展此演算法最主要的目的在於….,因選取tagSNP問題已是一個困難問題,在求解出他的所有多重解釋更困難之問題,因此本演算法僅適用於求解問題規模較小的選取問題,可將此小規模問題定義為給定切割Block資訊後之問題

23 求解tagSNPSP之多重解 研究目的 PtagSNP問題存在多重最佳解 過去研究著重求解方法及效率 未探討多重最佳解間之差異
引入 LD 概念 滿足PtagSNP 之目標且所挑選之tagSNP彼此關連性最高 此問題存在……. NCKU _IIM_2008/05/30_求解tagSNPSP之多重解最佳解_研究目的

24 演算法步驟 Step 1： 刪除矩陣H中重複及互補的column 記錄所刪除的column群組 Step 2： 建立bipartite網路圖
將E節點中degree為1者對應之S節點放入tagSNP set中，刪除相連結之節線節點 更新S節點之degree Example 這是我的演算法流程,位幫助說明,我直接以範例說明 NCKU _IIM_2008/05/30_求解tagSNPSP之多重解最佳解_求解演算法

25 Step 3： Step 4： 計算辨識m條haplotype所需的最少SNP個數 從剩餘之S節點中再挑選剩餘所需之tagSNP數
檢驗候選組合中的S節點degree總合 Step 4： 檢驗Step 3中剩餘組合是否可與剩下的E節點完全連結 若全部皆無法通過此檢驗，將Step 2的k值加1，並重複Step 3 候選組合可以通過此檢驗者，即為最佳解。 NCKU _IIM_2008/05/30_求解tagSNPSP之多重解最佳解_求解演算法

26 Step 5： 對每組多重最佳解檢驗每個SNP，若在Step 1中有重複或互補之其它SNP，則置換此SNP位置產生另一組多重最佳解群組(其LD值無差異) 以此類推，推導出所有的多重最佳解 Step 6： 針對每組多重最佳解，計算其LD估算值 選取LD平均估算值最高者作為本演算法所建議之最佳解 NCKU _IIM_2008/05/30_求解tagSNPSP之多重解最佳解_求解演算法

27 雙目標數學規劃模式 模式 由於整個MultuTagSNP考慮了兩種不同的選取準則,因此本論文建立的一個選取tagSNP的雙目標數學模型
　　　模式 由於整個MultuTagSNP考慮了兩種不同的選取準則,因此本論文建立的一個選取tagSNP的雙目標數學模型 NCKU _IIM_2008/05/30_雙目標數學規劃模式

28 w1 w2 w1/w2 X1 X2 X3 X5 X8 Z1 Z2 權重 斜率 效率解 非劣解 1 - 3 0.362 2 -2 0.500
- 3 0.362 2 -2 0.500 -1 0.917 -0.917 0.916 -0.916 4 1.417 0.563 -0.563 0.562 -0.562 5 1.980 0.1 -0.1 NCKU _IIM_2008/05/30_雙目標數學規劃模式_範例

29 最大化 值 LD 最少化tagSNP個數 NCKU _IIM_2008/05/30_雙目標數學規劃模式_範例

30 小結 本研究提出以圖形演算法為基礎求解多重最佳解方法(結合連鎖不平衡觀念) 由範例可看出多重最佳解中確實存在較高LD值之解
提出一個雙目標數學規劃模型 NCKU _IIM_2008/05/30_求解tagSNPSP之多重解最佳解_小結

31 LRH演算法 (單一組解) 接下來介紹我的第二個演算法LRH,此演算法主要目的在於用較高的效率解決大規模問題,

32 拉氏乘數(Lagrangian multiplier)
拉氏鬆弛法求解tagSNPSP 採用拉氏鬆弛法放鬆PtagSNP 拉氏乘數(Lagrangian multiplier) 由於選取tagSNP問題放鬆成拉氏問題可變成一簡單問題,且多位學者提出拉氏鬆弛法求解SCP問題效率及品質都很好 因此本演算法採用拉氏鬆弛法作為求解此問題的基礎 NCKU _IIM_2008/05/30_拉氏鬆弛法求解

33 次梯度法 拉氏乘數初始值 拉氏乘數更新式 (Caprara et al.,1999) 拉氏乘數更新的方向 幅度參數(step length)
最佳解所在的區間範圍 更新的範圍限制 小→較快獲得收斂的解 拉氏乘數更新的方向 幅度參數(step length) 大→表示欲前進的方向誤差越大 NCKU _IIM_2008/05/30_拉氏鬆弛法求解

34 求解PLtagSNP NCKU _IIM_2008/05/30_拉氏鬆弛法求解

35 固定欄位 Y N 讀入SNP資料 設定變數初始值： 1. UB設為N 2. 設定λ值 3. 計算初始拉氏乘數u0 求解拉式問題：
1. 找到其對應之解 2. 更新檢驗式s(u) 檢驗是否符合原問題限制 1.更新上界值與拉氏乘數uk 2.判斷是否更新UB值 是否到達設定遞迴次數 找到近似解或是最佳解 記錄此組解及對應之其他相關變數值 刪除此組解 Y N 固定欄位 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_演算流程

36 修正之拉氏鬆弛法 修正求解PLtagSNP UB=3 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_修正演算法

37 固定欄位縮減問題規模 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_修正演算法

38 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_修正演算法

39 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_修正演算法

40 模擬結果 模擬問題 n m 50 100 150 15 P15×50 P15×100 P15×150 30 P30×50 P30×100
45 P45×50 P45×100 P45×150 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_模擬結果

41 LRH演算法之收斂情況

42 P15˙50 P15˙100 P15˙150 P30˙50 P30˙100 P45˙50 P30˙150 P45˙100 P45˙150 P15×50 P15×100 P15×150 P30×50 P30×100 P45×50 P30×150 P45×100 P45×150 CPLEX 5.2 5.0 8.0 7.2 9.6 7.0 8.8 8.5 LRH (OPT gap) 6.9 12.2 12.0 14.5 13.8 16.3 15.3 32.69% 44% 60% 50% 66.67% 51.04% 49.27% 85.27% 80% MIX 6.2 5.8 9.0 8.6 10.8 7.6 10.2 19.23% 16% 4% 12.5% 19.44% 8.57% 15.9% 12.94% NCKU _IIM_2008/05/30_拉氏鬆弛法求解_模擬結果

43 P15×50 P15×100 P15×150 P30×50 P30×100 P45×50 P30×150 P45×100 P45×150 P15×50 P15×100 P15×150 P30×50 P30×100 P45×50 P30×150 P45×100 P45×150 CPLEX (NT) 0.16 0.78 2.50 4.84 256 41 1029 8071 19719 0.8 3.59 9.26 20.17 711 121 2144 13017 22666 LRH 0.26 0.79 1.12 0.83 1.43 1.49 2.02 2.70 3.58 1.30 4.15 3.46 3.97 4.38 4.21 4.35 4.11 MIX 0.20 0.22 0.27 0.24 0.36 0.34 0.48 0.62 0.87 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_模擬結果

44 P15×50 P15×100 P15×150 P30×50 P30×100 P45×50 P30×150 P45×100 P45×150 LRH Max 3 5 6 8 7 Min 1 2 4 Avg. 1.8 4.4 4.8 MIX 0.8 0.2 1.4 1.2 0.6 由上述的模擬結果顯示,LRH可以快速獲得一組近似解,但似近似解的品質仍不夠好,若想有較好的求解品質,可藉由Mix的方式,也就是以LRH先快速求得近似解縮減問題規模,再以CPLEX解縮小規模後的精確解,由模擬節果顯示,MIX方法同時具高效率及高品質 NCKU _IIM_2008/05/30_拉氏鬆弛法求解_模擬結果

45 總結 提出Multi-TagSNP演算法用以求解多重最佳解 建立tagSNP選取問題雙目標數學規劃模式 適用小規模問題
加入LD值作為第二評選準則 建立tagSNP選取問題雙目標數學規劃模式 最小化tagSNP個數 最大化LD值 NCKU _IIM_2008/05/30_總結

46 修正選取對應解與與固定欄位之規則以提升求解品質及效率 LRH可快速獲得一個近似解，適用於求解大規模問題
調整幅度參數提升求解品質  耗費許多人工時間 採用MIX之二階段方式(LRH與CPLEX結合)獲得高效率極高品質之結果 NCKU _IIM_2008/05/30_總結

47 未來建議 加入其他更具生物意義的條件作為新的評選方法。 從其他角度切入求解此tagSNPSP 。
在求解放鬆後的拉氏問題時，可改用其他收斂方式，而非次梯度法，如Bundle Method等。 增加跳脫固定欄位之限制，使求解結果跳脫局部解。 模擬真實生物資訊資料。 NCKU _IIM_2008/05/30_未來建議

48 Thanks for your attention!!!
Q&A? NCKU _IIM_2008/05/30