標題: 以全域最佳化方法求解DNA序列之共同區間定址問題(I)
A Global Optimization Method for Identifying Common Sites on DNA Sequences (I)
作者: 黎漢林
LI HAN-LIN
交通大學資訊管理研究所
關鍵字: 分子生物;共同區間;全域最佳化;線性0-1 規劃;蛋白質連結
公開日期: 2004
摘要: 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 上發展一分散式計算軟體以處理共同區間定址問題。
官方說明文件#: NSC93-2213-E009-070
URI: http://hdl.handle.net/11536/90938
https://www.grb.gov.tw/search/planDetail?id=1006983&docId=189772
顯示於類別:研究計畫


文件中的檔案:

  1. 932213E009070.pdf