標籤： 演化, 遺傳

阿簡生物筆記

http://a-chien.blogspot.com/2006/02/blog-post_18.html

二、研究計畫摘要─請對研究計畫之問題依下列各項述明：
(1)研究動機與研究問題􀀡
􀀡 在生物學以及分類學中有許多相當重要的問題，而其中一個就是
演化樹的建立[1,􀀡 2]。前人也有許多的研究論文[1-9,􀀡 12]，本研究問題
也將以此為題。在研究動植物的物種史包含了(1)建立正確的物種族譜
(2)分析不同的物種之最小共同祖先。這兩樣研究可以藉由演化樹，得
到許許多多的資訊。通常是假設演化樹是一個等距演化樹(ultrametric􀀡
tree)􀀡[3,􀀡4,􀀡5,􀀡6,􀀡7]，其中子葉為目前演化至今的物種，剩餘的內部節點
則是這些物種的祖先。而等距演化樹的特性，根節點至每一個子葉的
距離都是相同的，正代表著到目前為止物種有著相同的演化進度。如
下圖一即為等距演化樹。而在演化樹兩兩子葉的距離也就代表了兩個
不同物種的演化距離。􀀡
􀀡
圖一：等距演化樹
􀀡 一般做法為利用一個距離矩陣D[8]來建造演化樹。距離矩陣D代表
一個完全連通的無向圖G=(V,􀀡 E)，G有M個邊和N個點。在G上每一點
都代表一個物種。在G上每一個邊e都有一個實數代表兩兩物種i,􀀡j之間
的演化距離。使用D(i,􀀡 j)代表G中Vi和Vj的距離，即為這兩個物種的演
化差異程度。如表一代表了四個物種的演化距離D。􀀡
􀀡
表一：距離矩陣D􀀡
􀀡
􀀡
􀀡
􀀡
􀀡
􀀡
􀀡
􀀡 本研究問題，就是利用距離矩陣將演化樹給重新建立起來，使得
演化樹與距離矩陣是互相對應。我們稱作重新建構演化樹。如圖一，
就是以表一距離矩陣D所重新建構出來的演化樹T。􀀡
􀀡
􀀡 而重建出來的演化樹T，可能會有許多不同的類型，所以演化樹的
評估上也是相當重要的課題，我們使用TD(i,􀀡j)代表由i和j兩種物種再由
距離矩陣D所重建出來的演化樹T上的演化差異，根據這樣的差異還
D􀀡 s1􀀡 􀀡 s2􀀡 􀀡 s3􀀡 􀀡 s4􀀡
0􀀡 4􀀡 4􀀡 3􀀡
4􀀡 0􀀡 6􀀡 5􀀡
4􀀡 6􀀡 0􀀡 2􀀡
s1􀀡
s2􀀡
s3􀀡
s4􀀡 3􀀡 5􀀡 2􀀡 0􀀡
1
1
1
1
3
2
s3 s4 s1 s2
可以將演化樹分類為Minimax、Minisum和Minisize[12]。這三種分類
的定義分別如下：􀀡
• Minimax：當maximum{􀀡TD(i,􀀡j)􀀡-􀀡D(j,􀀡i)}為最小化(minimized)時，
就稱此演化樹為最小最大(Minimax)演化樹􀀡
• Minisum：當兩兩子葉距離的總和為最小化時，就稱此演化樹為
最小合(Minisum)演化樹􀀡
• Minisize：當所有路徑為最小化時，就稱此演化樹為最小化
(Minisize)演化樹􀀡
􀀡
這些分類也成了評估演化樹的關鍵，但事實上在演化樹中還有一
個更令人感興趣的特性，也是演化樹最重要的目的之一「親疏關係」。
在演化樹T中物種與物種所存在各種親屬關係之中，設TLCA(i,􀀡j)代表在
演化樹T上i,􀀡j兩個物種的最小共同祖先，如果演化樹T為((i,􀀡 j),􀀡k)代表
了TLCA(i,􀀡j)􀀡
􀀡
􀀡
􀀡
圖二：演化樹􀀡
􀀡
􀀡 另外為了符合物種之間的演化關係，所以距離矩陣D也符合以下的
條件。D(i,􀀡 j)等於D(j,􀀡 i)也就代表距離矩陣D是以對角線對稱的。D(i,􀀡
i)=0，自己跟自己是沒有差異。同時距離矩陣D也會符合三角不等式，
例如D(i,􀀡 j)+D(j,􀀡 k)=D(i,􀀡 k)[9]。距離矩陣D如果是等距演化樹若且非若
D(i,􀀡j)􀀡 ≦MAX{D(i,􀀡k),􀀡D(j,􀀡k)}[4]。如表一，就維持了這樣的特性。􀀡
􀀡
􀀡 事實上演化樹的建造已經被證明為NP-hard問題[9]，所以在本研究
計畫，我們試圖透過平行演算法，以及先前所提的演化樹親疏關係的
特性（如：最小共同祖先），來加快計算的時間，以及取得更完整的
親屬關係，此為本計畫之研究方向。􀀡
􀀡
􀀡 其中本研究計畫將利用緊湊關係(compact􀀡 set)[10,􀀡 11]找出親疏關
係。在完全連通的無向圖G上，設S為點的子集合。如果一個邊e的兩
端點都落在之中，稱e為內部邊(inside􀀡edge)。如果一個邊e的兩端點，
一端在S之中另外一端不是，稱e為突觸邊(broder􀀡 edge)。當S1和S2都為
點的子集合且S1與S2的交集為Φ，e的一端在S1另外一端在S2，稱e為交
叉邊(cross􀀡edge)。當S符合任意的內部邊小於任意的突觸邊，稱S符合
緊湊關係[11]。如圖三，為表一的緊湊關係。􀀡
􀀡
i j k
􀀡
􀀡
􀀡 􀀡
􀀡
􀀡
􀀡
􀀡
􀀡
圖三：緊湊關係􀀡
􀀡 􀀡
􀀡 緊湊關係的建立，也意味著在圖G之上，哪些點V有著較密切的親
屬關係。而這樣的親疏關係往往也是生物學家所關心的焦點之一，畢
竟有了正確的親疏關係的建立，更可以觀察出物種演化的過程，如何
的改變，而這樣的特性絕對不亞於先前所提到的最小最大、…等特
性，甚至有過之而無不及，所以如何利用緊湊關係來建立演化樹，也
是本研究計畫的重點之一。􀀡
􀀡
􀀡 除了緊湊關係的建立，本研究計畫的另外一個重點就是平行演算
法的設計與實作。在先前的研究論文中[9] ， 利用了分枝界定
(branch-and-bound)演算法設計出了單機建構演化樹的演算法，雖然分
枝界定演算法沒有辦法保證可以在多項是時間內把最差情況(worst􀀡
case)解決掉。但是分枝界定演算法可以把最佳解找到，這一點在
NP-hard問題上是非常有利的，同時分枝界定演算法也相當適合平行
化成為平行演算法，所以本研究計畫將嘗試設計出平行演算法來縮短
演化樹建造的時間。􀀡
􀀡
􀀡 本研究計畫嘗試藉建立起緊湊關係與最小共祖先特性的互相對
應，並配合上平行演算法來加速達成演化樹的建立，在硬體的平台上
我們將使用中華大學資工系的叢集電腦(cluster)，這個叢集電腦是由
24部配備相同之個人電腦所組成並且使用乙太網路線串連在一起，除
此之外本計畫亦希望能夠將平行演算法的實作推展至網格運算的架
構環境以求更有效率的建構演化樹。􀀡
􀀡
(2)研究方法及步驟􀀡
􀀡 本研究計畫將以圖論與平行運算的角度和方法，來思考演化樹建
立問題。將採取以下幾個階段。􀀡
􀀡
1. 收集並研讀演化樹建立相關論文。
2. 研究並提出有效的平行程式化演化樹建構演算法。
s1 4 s2
s3 2 s4
4 6 3 5
S1
S2
S3
3. 思考緊湊關係與最小共同祖先對於演化樹建立之效能提升關
係。
4. 設計利用緊湊關係解決演化樹建構之平行演算法。
5. 驗證我們所提出的演算法之正確性與效能。
6. 實際進行人類粒腺體之演化樹建構並討論與分析在生物資訊上
的效用。
7. 撰寫研究報告。
8. 將研究成果做進一步之推廣。
(3)預期結􀀡
1. 設計出利用緊湊關係解決演化樹建立之演算法。並將本研究結
果運用在生物資訊上。
2. 透過緊湊關係加上平行演算法在叢集架構上的實作，預期可以
大幅度的提高演算樹的建構運算速度。
3. 同時藉由參與計畫的過程，熟悉圖論技巧與演算法設計，以及
生物資訊上的實際應用。
4. 撰寫有學術貢獻的論文。
(4)參考文獻
1. D.􀀡Gusfied,􀀡Algorithms􀀡on􀀡Strings,􀀡Trees,􀀡and􀀡Sequences,􀀡Computer􀀡
Science􀀡and􀀡Computational􀀡Biology,􀀡Cambridge􀀡University􀀡Press,􀀡
1997.􀀡
2. W.H.􀀡Li􀀡and􀀡D.􀀡Graur,􀀡Fundamentals􀀡of􀀡Molecular􀀡Evolution,􀀡
Sinauer􀀡Associates,􀀡1991.􀀡
3. M.D.􀀡Hendy􀀡and􀀡D.􀀡Penny,􀀡“Branch􀀡and􀀡bound􀀡algorithms􀀡to􀀡
determine􀀡minimal􀀡evolutionary􀀡trees,”􀀡Mathematical􀀡Biosciences,􀀡
vol.􀀡59,􀀡pp.􀀡277-290,􀀡1982.􀀡
4. H.J.􀀡Bandelt,􀀡“Recognition􀀡of􀀡tree􀀡metrics,”􀀡SIAM􀀡Journal􀀡in􀀡
Discrete􀀡Mathematics,􀀡vol.􀀡3,􀀡no.􀀡1,􀀡pp.􀀡1-6,􀀡1990.􀀡
5. E.􀀡Dahlhaus,􀀡“Fast􀀡parallel􀀡recognition􀀡of􀀡ultrametrics􀀡and􀀡tree􀀡
metrics,”􀀡SIAM􀀡Journal􀀡on􀀡Discrete􀀡Mathematics,􀀡vol.􀀡6,􀀡no.􀀡4,􀀡pp.􀀡
523-532,􀀡1993.􀀡
6. M.􀀡Farach,􀀡S.􀀡Kannan,􀀡and􀀡T.􀀡Waenow,􀀡“A􀀡robust􀀡model􀀡for􀀡finding􀀡
optimal􀀡evolutionary􀀡trees,”􀀡Algorithmica,􀀡vol.􀀡13,􀀡pp.􀀡155-179,􀀡
1995.􀀡
7. M.􀀡Krivanek,􀀡“The􀀡complexity􀀡of􀀡ultrametric􀀡partitions􀀡on􀀡graphs,”􀀡
Information􀀡Processing􀀡Letter,􀀡vol.􀀡27,􀀡no.􀀡5,􀀡pp.􀀡265-270,􀀡1988.􀀡
8. W.H.􀀡Li.􀀡Molecular􀀡Evolution.􀀡Sinauer􀀡Associates,􀀡Inc.,􀀡1997.􀀡
9. Wu,􀀡B.􀀡Y.,􀀡Chao,􀀡K.􀀡–M.􀀡and􀀡Tang,􀀡C.􀀡Y.,􀀡“Exact􀀡and􀀡Approximation􀀡
Algorithms􀀡for􀀡Constructing􀀡Ultrametric􀀡Trees􀀡from􀀡Distance􀀡
Matrices,”􀀡Journal􀀡of􀀡Combinatorial􀀡Optimization,􀀡vol.􀀡3,􀀡pp.􀀡
199-211,􀀡1999.􀀡
10. 􀀡 E.􀀡Dekel,􀀡J.􀀡Hu,􀀡and􀀡W.􀀡Ouyang,􀀡“An􀀡optimal􀀡for􀀡finding􀀡compact􀀡
sets,”􀀡Information􀀡Processing􀀡Letters,􀀡vol.􀀡44,􀀡pp.􀀡285-289,􀀡1992.􀀡
11. 􀀡 Sung􀀡Kwon􀀡Kim,􀀡“A􀀡note􀀡on􀀡finding􀀡compact􀀡sets􀀡in􀀡graphs􀀡
represented􀀡by􀀡an􀀡adjacency􀀡list”􀀡Information􀀡Processing􀀡Letters,􀀡
vol.􀀡57,􀀡pp.􀀡335-238,􀀡1996􀀡
12. 􀀡 Chang,􀀡J.􀀡M,􀀡Tang,􀀡C.Y.,􀀡Chang,􀀡C.􀀡L.,􀀡“Compact􀀡Set􀀡Neighboring􀀡
Relation􀀡and􀀡Its􀀡Application􀀡in􀀡Evaluating􀀡Evolution􀀡Tree”,􀀡
Workshop􀀡on􀀡Algorithms􀀡and􀀡Computational􀀡Molecular􀀡Biology,􀀡
International􀀡Computer􀀡Symposium,􀀡2002(ICS􀀡02)􀀡 􀀡
􀀡
(5)需要指導教授指導內容􀀡
1. 在參考資料的收集上，如何往正確的方向收集，也需教授指導。
2. 在演算法的設計與驗證上，須和教授一同討論，演算法的正確
性也須由教授作更進一步的確認。
3. 在報告的撰寫上，須由教授指導撰寫的方式，以及如何將研究
成果有效撰寫出來。
4. 如何將研究成果的進步的推廣，也需要教授的指導。

https://nscnt12.nsc.gov.tw/applyform/WCR/94/A125779623/A125779623_C802.pdf