跳到主要內容
:::
登入
註冊
網站導覽
展開搜尋
全站搜尋
熱門關鍵字:
半導體
精準醫療
太空
煙火
關閉搜尋
您的瀏覽器不支援此script語法,請點選
搜尋
使用搜尋功能。
分類
分類項目
關閉分類項目
地理
天文
化學
醫學
科技
社會科學
人類文明
地科
心理
物理
數學
環境
生物
生活科學
醫療
地球科學
Menu
關於我們
文章
熱門文章
最新文章
精選文章
科學專題
科發月刊
影音
TechTalk
科普影片
活動
學生專區
夥伴
認證
公務人員
網站導覽
English
首長信箱
常見問答
雙語詞彙
關於我們
文章
文章
熱門文章
最新文章
精選文章
科學專題
科發月刊
影音
影音
TechTalk
科普影片
活動
學生專區
夥伴
認證
認證
公務人員
:::
首頁
Pleace Login!
×
請先登入
facebook
twitter
line
中
列印
書籤
:::
生物資訊:高密度片段的尋找–生物資訊學的問題重整
94/12/08
瀏覽次數
5670
呂學一
|
臺灣大學資訊工程學系
「問題重整」(problem reduction)是資訊科學很重要的觀念與技巧,科學家遇到一個不熟悉的問題時,會把原始的問題轉換成比較熟悉的「形式」(formulation),進而藉由新形式相關領域中的工具解決原先的問題。在生物資訊研究中,這種「問題重整」的例子屢見不鮮。
「生命科學」、「電腦」與「幾何」可以有怎樣的關聯呢?「演算法」的技術很巧妙地把似乎沒有交集的三個領域串連在一起。
生命科學
先從生命科學談起吧。
半個世紀以前,科學家對於去氧核醣核酸(DNA)的結構並沒有太多的認識,而顯微鏡可憐的放大倍數,也很難提供肉眼可見的影像。直到1949年查爾葛夫與維雪才確定DNA是由腺嘌呤(adenine, A)、鳥糞嘌呤(guanine, G)、胞嘧啶(cytosine, C)、胸腺嘧啶(thymine, T)4種成分所組成。稍後薩門霍夫加入這個團隊,開始對DNA的4種成分進行定量的分析。
當時普遍猜測A、G、T、C在DNA裡的比率應該相去不遠,但3人獲得的實驗數據卻完全不是這麼回事,他們發現在不同DNA當中,A、G、T、C的比率並不相同。最有趣的是,不管4種成分的比率如何變化,A與T的數量總是非常相近,G與C的數量也幾乎相同。當時查爾葛夫甚至在論文中寫下:「我們的定量分析觀察到一個令人驚訝,但或許是毫無意義的規律性。」
幾年之後全世界才恍然大悟,原來查爾葛夫等人所觀察到的規律性,有非比尋常的重大意義。1953年華生與克里克提出DNA的「雙螺旋結構」,結構中互相纏繞的兩道DNA序列裡,A總是黏著T,而G總是與C為伍。那篇短短兩頁不過900字的論文,深深影響過去這半個世紀生命科學的研究發展。為此華生與克里克在1962年與威爾金斯獲得諾貝爾生理與醫學獎的殊榮。
雖然查爾葛夫等人所觀察到的規律性已經有了清楚的解釋,但是A-T與G-C的數量在不同DNA序列為什麼會有明顯的差異,至今科學家還是有兩派意見,誰也不服誰。倒是有一些研究顯示,在G-C密度比較高的片段當中,通常會有比較豐富的生物意義。於是這裡衍生出一個電腦演算法的問題,就是怎麼在一個DNA序列中找到一個G-C密度最高的片段。
電腦
以上這個題目讓我們想到「電腦」。電腦的快速計算能力,這幾年成了「生命科學」相關研究的一具強力噴射引擎,使得DNA定序的進展一日千里。過去生物學家必須埋頭苦幹好幾年才能完成的實驗,如今靠著電腦的幫忙,可以在短短幾天之內完成。
不過要讓電腦幫忙,得靠程式設計人員撰寫程式。電腦跑得快不快,跟程式寫得好不好大有關係,而一個程式寫得好不好,又跟程式背後那個解決問題的想法,也就是「演算法」(algorithm)有絕對的關聯。
比較演算法孰優孰劣有一套粗略但相當客觀的標準,就是演算法解決問題時所需要的運算時間,跟所輸入資料的長度之間是怎樣的關係。如果是成線性的關係,這個演算法就是最佳的解題法,如果是平方的關係,這個演算法就沒有那麼受人青睞,萬一是立方的關係,這個演算法就不切實際了。
以上面提到的例子來說:我們手中有一個長度是n的DNA序列,而想要寫個程式找出這個序列當中長度不短過m,而且G-C的密度最高的片段。這個程式所需要的運算時間如果與m×n成正比(即所謂成平方關係),程式背後的演算法就還有待改進。如果程式所需要的運算時間與n成正比(即所謂成線性關係),這個程式背後的演算法便是最佳的解題方法。
這個「G-C密度最高片段」的問題,很自然地可以重整成一個「數列」的問題:輸入一個長度是n的數列,其中每個數字非0即1(A或T用0代表,G或C就用1代替),要求輸出該數列一個不短過m的片段,使得這片段的平均值為最高。而所謂平均值就是,這個片段當中數字的和除以片段的長度。
這個數列上的問題,很容易就有一個平方時間的演算法,道理很簡單,因為長度是n的數列最多只有n2個片段,只須挑出這個片段當中長度大於或等於m,且平均值為最高的一個片段即可。簡簡單單就讓平方時間的演算法完成任務。不過如果想讓執行時間跟數列長度的關聯降低到線性關係,數列演算法好像沒有現成的工具可以直接套用,這時候就需要「幾何」來幫忙了。
幾何
幾何學是一門非常古老的學問,上至天文,下至地理,莫不與幾何密切相關。過去這20年在「計算幾何」這個領域當中,有許多問題被研究得非常透徹。舉例來說,如果給定平面上n個點,如何快速從這n個點當中挑出兩個點,使得通過這兩點的那條直線的斜率為最大,這就是曾被深入研究過的「斜率選擇」問題。
其實上述的最高均值片段的問題,正可以「重整」成一個特別的「斜率選擇」問題。乍聽之下這兩個問題似乎毫不相干,但是底下這個轉換,說穿了一點也不稀奇。
把數列當中的n個數字分別對應到平面上面的n個點:第i個數字的x座標就是i。至於y座標,為了方便起見,我們想像有個第0點在平面的原點(0,0)上,也就是第0點的y座標是0。此後第i個點的y座標,就是第i-1個點的y座標加上第i個數字。有了這n+1個在平面上的點,尋找平均值最高的數列片段,就變成尋找兩個x座標相差大於或等於m的兩個點,使得通過這兩個點的直線有最大的斜率。
由於「計算幾何」領域當中,有諸多現成的演算法工具可以處理各式各樣「斜率選擇」問題的變形,所以稍為再費點心思,線性時間的演算法就唾手可得。
換個角度看
科學家在著手研究的時候,有高「智商」(IQ,intelligence quotient)固然吃香,但是高CQ或許更要緊。甚麼是CQ呢﹖就是「創意商數」(creativity quotient)。當年愛因斯坦用微分幾何發展出相對論,近年來不管是在生命科學研究當中引進電腦演算法,或是利用物理上「量子」的性質來解決數學上「因數分解」的大難題,背後全都是「問題重整」的創意。
您手中有甚麼懸宕已久的難題嗎?換個角度來看看吧,做個「問題重整」或許就會「山窮水盡疑無路,柳暗花明又一村」呢!
資料來源
《科學發展》2005年12月,396期,24 ~ 29頁
科發月刊(5221)
推薦文章
114/06/30
誰說止痛藥只能止痛?它可能是下一款美白成分主角!
曾繁安
|
科技大觀園特約編輯
儲存書籤
114/03/28
從空中看災區、用資料拚速度 AI + 遙測讓防災更精準
寒波
|
科技大觀園特約編輯
儲存書籤
114/06/30
別讓防曬美意變環境負擔!看農業廢棄物如何變身科技材料,吸附水中有害環境荷爾蒙
余國賓
|
國立陽明交通大學 環境與職業衛生研究所教授
儲存書籤
114/07/31
從黑潮找電力,從鯨豚找答案 能源轉型走向海洋
陳彥諺
|
科技大觀園特約編輯
儲存書籤
OPEN
關於我們
關於我們
文章
熱門文章
最新文章
精選文章
科學專題
影音
科普影片
TechTalk
活動
活動
學生專區
學生專區
回頂部