生物資訊:高密度片段的尋找–生物資訊學的問題重整

「問題重整」(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)。當年愛因斯坦用微分幾何發展出相對論,近年來不管是在生命科學研究當中引進電腦演算法,或是利用物理上「量子」的性質來解決數學上「因數分解」的大難題,背后全都是「問題重整」的創意。

您手中有甚么懸宕已久的難題嗎?換個角度來看看吧,做個「問題重整」或許就會「山窮水盡疑無路,柳暗花明又一村」呢!

除非注明,其他來源均為石飛博客整理發布,轉載請以鏈接形式標明本文地址

標簽: