论文部分内容阅读
生物学界目前流行在分子水平上重建系统发育树,以此来描述生命的演化进程。常见的系统发育重建算法有基于距离原则的不加权算术平均对群法、邻接法和基于最优原则的最大简约法、最大似然法、贝叶斯法等。相比于其它算法,最大似然法在统计的一致性、原始数据信息利用的充分性以及同一框架下的似然树的可比性等方面有明显优势,但这些优势的代价是最大似然法全局搜索的计算时间复杂度是指数级的,为尽量减低计算时间复杂度,实际应用多采用寻求局部最优的启发式减枝算法策略,以致其在系统发育重建领域的应用受到限制。本文立足于系统发育重建中最大似然法的全局搜索方法,运用计算机科学领域成熟的并行计算技术,针对似然树重建过程中的计算特点,展开并行化研究。首先,从似然计算的分析入手,构建了最大似然法重建系统发育树全局搜索的串行算法Serial-MLE 。运用“四步并行算法设计法”,分析了最大似然法的计算过程中在树的拓扑空间和序列的位点空间上的可并行性,采用轻量级的Fork/Join并行框架设计和实现了树空间的并行算法FJ-Topo和位点空间的并行算法FJ-LocuS。进一步的实验表明FJ-Topo在树空间上平均加速了3.69倍,FJ-Locus在位点空间上平均加速了1.55倍,这充分说明了系统发育重建的似然计算在树的拓扑空间和序列的位点空间上的可并行性。其次,针对树空间随着分类群数量的增加而呈现阶乘式增长的趋势,在基于消息传递机制的MPJ并行计算框架下,设计了树空间上多进程加速并行算法MPJ-Topo,同时融合了Fork/Join框架加速位点空间上并行计算的混合式算法MPJ-FJ。实验表明MPJ-Topo算法在树空间上平均加速比达到7到8倍左右；混合式算法MPJ-FJ在较短的序列情况下,加速表现不如MPJ-Topo,但随着序列长度位点空间的增大,混合式算法MPJ-FJ在MPJ-Topo的基础上最高可以提升10%左右的加速。第三,基于MapReduce并行框架的大数据处理能力,在爆炸式增长的树空间上实现MapReduce并行化算法MR-Topo,同时延续混合式并行算法的思路,实现融合Fork/Join加速并行计算位点空间的混合式算法MR-FJ 。实验表明MR-Topo在树空间上最高可达到了52.82的加速比,混合式算法MR-FJ的加速比随着分类群规模和序列长度的增加而增长,最高可达到57.72。本文在最大似然法重建系统发育树领域进行了一些的并行化算法的探索,依据取得的结果认为,在生物大数据的趋势下,并行技术特别是MapReduce并行框架可以为全局寻优的最大似然法提供有效的并行计算手段。