[問題] 不知有人曾有經驗Parse "Newick" tree嗎？

看板C_and_CPP (C/C++)作者lulala888 (嚕啦啦)時間16年前 (2009/09/05 12:14)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串1/1

先聲明一下，這個不是作業題，而是我實際的一個問題，我本身不是科班出身，但是有許多寫經驗的程式，但最近碰上這個問題，卻讓我不知如何去實作它？這個問題，是關於基因演化的。我有一個檔案tree.txt，裡面的格式為 ((t1:0.3,t2:0.5):0.1,(t3:0.2,t4:0.6):0.2); 這是一個基因樹，如果把它畫圖，就會成位下面這種樹狀圖 0.3 0.1|-----------(t1) |-----(A)| 0.5 | |----------------------(t2) (F)| | 0.2 | 0.2 |---------(t3) |-----------(B)| 0.6 0.6 |---------------------------------(t4) 以括號中的 t1:0.3 為例，代表t1這個node有個長度附加於這node上，長度為0.3 若有逗號，則表示這兩個nodes是處於平行位置上，只是附帶的長度資訊是不同的，所以我們可以看見，(t1:0.3,t2:0.5)同處於 node A下，並各自帶不同的長度，我這個檔案是不會有A,B及F這些資訊的，這只是為了讓大家了解方便，我自行加設的。這個基因樹還有個特點，每一個node下最多兩個children，但是也有可能只有一個，除非再末端，否則nodes >= 1，以我這個tree來說， ((t1:0.3,t2:0.5):0.1,(t3:0.2):0.2); <--這是可能的(把t4刪除) 以下為我的問題， (1)我要把這個基因樹的資訊，Parse到Array或Matrix中，因為之後我要把長度資訊加以計算，請問我要怎樣儲存這些資訊較好呢？ (2)我要的計算是遞迴的，比如說我的function為 myfunction()，這function會傳出double的值以節點F來說（最後結果），F的結果應等於 myfunction(A,0.1)+myfunction(B,0.2)，而節點A的的值應為myfunction(t1,0.3)+myfunction(t2,0.5)，而節點B的值myfunction(t3,0.2)+myfunction(t4,0.6)。不知大家可以看出我想要的計算嗎？我要重最末端開始算起，且我的基因樹，遠遠複雜於這個，這邊只有兩層，我的基因樹高達50層以上，而且我的程式有二個限制，我希望用threads去平行計算，且我的myfunction不能用遞迴的方式（因為記憶體的限制）。想請問再這樣的限制下，如何Parse我的tree？又如何在不用遞迴的前提下，去計算F值？先在此謝謝大家，希望能幫我想想，如能有codes告訴我大概的方法更佳。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 24.160.178.133