以全域最佳化方法求解DNA序列之共同區間定址問題(I)

Abstract

DNA 序列之共同區間定址問題從過去20 年至今一直被廣泛討論。目前許多求解 CSI(Consensus Sequence Identification)問題的方法多引用最大相似技術[Stormo 1989, Ecker et al 2002]。這類方法不僅無法確認得到的解答是否為全域最佳解，而且無法處理 包含有上百筆序列之大尺度CSI 問題。本研究計畫提出一新的方法以求解大尺度CSI 問題以得到全域最佳解。我們首先將CSI 問題轉成一非線性0-1 規劃問題；此一問題可 經由線性化的處理後轉化成一線性0-1 規劃問題。給定L 筆DNA 序列資料，欲找出在 此L 條序列中長度為k 的共同區間，則我們可將其相關的CSI 問題轉化為一隻含有4k 個0-1 變數之線性0-1 規劃問題。由於L（序列的筆數）不會影響0-1 變數的個數，我 們的模式可以處理大筆數的CSI 問題。因此我們可以發展一分散式計算系統求解包含數 百筆DNA 序列的問題。本研究計畫擬分三年進行。第一年著重於發展CSI 問題的最佳 化求解模式。第二年為拓展此模式尋找多個次佳解，以提供生物學家更多CSI 的參考答 案。第三年則為在PC 上發展一分散式計算軟體以處理共同區間定址問題。