分子系統(tǒng)發(fā)育推斷中最大似然法的并行化研究.pdf

1、生物學(xué)界目前流行在分子水平上重建系統(tǒng)發(fā)育樹，以此來描述生命的演化進(jìn)程。常見的系統(tǒng)發(fā)育重建算法有基于距離原則的不加權(quán)算術(shù)平均對群法、鄰接法和基于最優(yōu)原則的最大簡約法、最大似然法、貝葉斯法等。相比于其它算法，最大似然法在統(tǒng)計(jì)的一致性、原始數(shù)據(jù)信息利用的充分性以及同一框架下的似然樹的可比性等方面有明顯優(yōu)勢，但這些優(yōu)勢的代價(jià)是最大似然法全局搜索的計(jì)算時(shí)間復(fù)雜度是指數(shù)級的，為盡量減低計(jì)算時(shí)間復(fù)雜度，實(shí)際應(yīng)用多采用尋求局部最優(yōu)的啟發(fā)式減枝算法策略，

2、以致其在系統(tǒng)發(fā)育重建領(lǐng)域的應(yīng)用受到限制。本文立足于系統(tǒng)發(fā)育重建中最大似然法的全局搜索方法，運(yùn)用計(jì)算機(jī)科學(xué)領(lǐng)域成熟的并行計(jì)算技術(shù)，針對似然樹重建過程中的計(jì)算特點(diǎn)，展開并行化研究。
　　首先，從似然計(jì)算的分析入手，構(gòu)建了最大似然法重建系統(tǒng)發(fā)育樹全局搜索的串行算法Serial-MLE。運(yùn)用“四步并行算法設(shè)計(jì)法”，分析了最大似然法的計(jì)算過程中在樹的拓?fù)淇臻g和序列的位點(diǎn)空間上的可并行性，采用輕量級的Fork/Join并行框架設(shè)計(jì)和實(shí)現(xiàn)了樹空

3、間的并行算法FJ-Topo和位點(diǎn)空間的并行算法FJ-Locus。進(jìn)一步的實(shí)驗(yàn)表明FJ-Topo在樹空間上平均加速了3.69倍，F(xiàn)J-Locus在位點(diǎn)空間上平均加速了1.55倍，這充分說明了系統(tǒng)發(fā)育重建的似然計(jì)算在樹的拓?fù)淇臻g和序列的位點(diǎn)空間上的可并行性。
　　其次，針對樹空間隨著分類群數(shù)量的增加而呈現(xiàn)階乘式增長的趨勢，在基于消息傳遞機(jī)制的MPJ并行計(jì)算框架下，設(shè)計(jì)了樹空間上多進(jìn)程加速并行算法MPJ-Topo，同時(shí)融合了 Fork/

4、Join框架加速位點(diǎn)空間上并行計(jì)算的混合式算法MPJ-FJ。實(shí)驗(yàn)表明MPJ-Topo算法在樹空間上平均加速比達(dá)到7到8倍左右；混合式算法 MPJ-FJ在較短的序列情況下，加速表現(xiàn)不如 MPJ-Topo，但隨著序列長度位點(diǎn)空間的增大，混合式算法MPJ-FJ在MPJ-Topo的基礎(chǔ)上最高可以提升10％左右的加速。
　　第三，基于MapReduce并行框架的大數(shù)據(jù)處理能力，在爆炸式增長的樹空間上實(shí)現(xiàn)MapReduce并行化算法MR-To

5、po，同時(shí)延續(xù)混合式并行算法的思路，實(shí)現(xiàn)融合 Fork/Join加速并行計(jì)算位點(diǎn)空間的混合式算法 MR-FJ。實(shí)驗(yàn)表明MR-Topo在樹空間上最高可達(dá)到了52.82的加速比，混合式算法MR-FJ的加速比隨著分類群規(guī)模和序列長度的增加而增長，最高可達(dá)到57.72。
　　本文在最大似然法重建系統(tǒng)發(fā)育樹領(lǐng)域進(jìn)行了一些的并行化算法的探索，依據(jù)取得的結(jié)果認(rèn)為，在生物大數(shù)據(jù)的趨勢下，并行技術(shù)特別是 MapReduce并行框架可以為全局尋優(yōu)的最