PAML

PAML是一款利用最大似然法對DNA或蛋白質序列進行系統發育分析的軟體包，該軟體包由著名華裔科學家、英國皇家科學學院士、倫敦大學統計遺傳學教授楊子恆開發並免費提供給學術研究使用。

基本介紹

• 中文名：Phylogenetic Analysis by Maximum Likelihood
• 外文名：PAML
• 開發者：楊子恆
• 利用方法：最大似然法

PAML簡介

PAML（Phylogenetic Analysis by Maximum Likelihood）

PAML在UNIX/Linux/Mac OSX系統下使用ANSI C源碼，在Window系統下（Windows 9x/NT/2000/XP/Vista）使用DOS命令操作。

從套用範圍來說，PAML並不是最好的系統樹構建軟體，但在系統樹的基礎上可以非常有效的進行：進化參數估計、進化假說檢驗、分歧時間估計、正選擇估計等。因此，可以用PAUP*、PHYLIP等首先進行系統樹構建，之後用PAML進行分子進化方面的研究。

PAML串列算法分析

在PAML 中，最大似然法的計算具體過程包括以下兩個步驟：

計算單個位點的似然值。PAML用現存物種在該位點所有可能的組合及其機率來表示這個值，與替代模型密切相關；

計算進化樹的似然值。PAML中用所有位點似然值f（x_h;θ）的對數之和來表示, 其中，x_h 是輸入的核苷酸序列；θ是 數學模型中使用的一組參數，如分支長度；n表示位點總數。如果用PMat=e^Qt代表轉移機率矩 陣，t代表時間，Q代表瞬時轉移機率矩陣，conP代表條件機率矩陣（用數組形式表示），那 么 串 行PAML算法的描述如算法1所示。

PAML並行算法設計

瓶頸函式確定

所謂瓶頸函式，就是指程式運行過程中比較耗時的函式。如果想最佳化程式、提高程式的性能，應優先處理瓶頸函式。

並行算法策略

並行化操作，採用了兩個層次的並行策略：

位點間並行

由於每個基因序列中的多個位點間的運算相互獨立，因此將位點劃分給多個處理器核心，使用多執行緒技術 實現同位點計算任務的並行。

位點內並行

一個位點內要進行大量矩陣、向量運算，這些運算很適合進行數據級並行，因此使用SSE/AVX來實現位點內的SIMD 並行計算。

並行算法實現

首先進行數據擴展，使用memalign函式可以在動態分配記憶體的時候指定邊界對齊。這樣在使用SSE/AVX時就可以高效地訪問數據、提高計算吞吐率。兩級並行算法如算法2所示。

算法2

for all nodes i do//stage 1    For all gene sequence i do        using bpm_avx compute transition p probability matrix PMai=U*expt*V        For each threads i do // using - openmp,0<=i<t            For all sites k/t do                For all rodons m do                    using avx compute transition p probability states array comP                end for            end for        end for    end forend forcompute likehood function f,|θfor the whole tree // stage 2

總結

利用多核的PAML並行算法對DNA序列以及蛋白序列的數據集分析有很明顯的加速效果，在將來基於PAML並行算法的系統分析將得到廣泛套用。