基于距离的进化树系统的并行算法研究的开题报告.docx

基于距离的进化树系统的并行算法研究的开题报告
开题报告
题目：基于距离的进化树系统的并行算法研究
导师姓名：XXX
申请人姓名：XXX
一、课题研究的背景与意义
Phylogenetic（系统发育）研究是生物学、进化生物学、生物信息学等领域的重要组成部分。系统发育研究的目标是通过对物种特征的分析，推断物种间的进化关系，进一步了解现有物种的起源和演化历程。其中，进化树系统是一种重要的分析工具，用于描绘物种间的进化关系，并可应用于估计特定物种在树上的进化位置。
随着高通量测序技术的发展，能够生成大量的分子序列数据，使得大规模的进化树系统分析成为可能。大规模数据集的分析需要使用高效的进化树系统计算算法和技术。目前常用的进化树系统计算方法包括最大似然估计法（ML）和贝叶斯方法（Bayesian）等。这些方法基本上都是串行的计算方法，无法满足对大规模数据的高效处理需求。因此，研究高效的并行算法对进化树系统的计算是必要的。
二、研究内容
本课题的主要研究内容是基于距离的进化树系统的并行算法。距离法是一种常用的计算进化树系统的方法，其基本原理是计算不同物种之间的距离，并根据距离计算进化树系统。在本课题中，我们将研究如何使用并行计算算法加速距离法计算。具体研究内容如下：
1.分析距离法的计算过程，探究并行计算的可行性。
2.设计并实现基于MPI（MessagePassingInterface）高性能并行计算框架，并完成一些基本的并行操作，如数据划分、任务分配等。
3.探索并实现一些并行化精度控制策略，如Bootstrapping，Jackknife等。
4.设计并实现支持复杂、大规模数据并行计算的算法。
5.测试和评估所提出的算法的精确性和性能性能，并与目前主流方式进行对比分析。
三、研究的预期结果
本课题期望能够研究出一种高效的基于距离的进化树系统并行算法，能够大大缩短大规模数据集下的计算时间，从而为高质量进化树系统的计算提供基础支持。同时，本研究也期待具有较高的应用价值，能够得到在生物信息学、生物学、进化生物学等领域的应用。
四、研究的进度安排
本课题的进度大致分为以下几个阶段：
1.研究距离法计算过程及其并行化方法。
2.设计MPI的高性能并行计算框架。
3.实现精度控制策略和支持大规模数据的并行算法。
4.进行实验测试，并在结果发布和推广前进行优化。
五、参考文献
1.LiuK.,RaghavanS.,andNelesenS.Alignmentofdistancematricesandphylogeneticinference.SIAMJournalonDiscreteMathematics(2006).
2.Székely,L.A.,andGolovin,K.Scalabledistancebasedphylogenetictreereconstructionusingmapreduce.JournalofParallelandDistributedComputing(2014).
3.vanOrmondtD.,andvanderMaeleO.ParallelizationofdistancematrixcomputationusingOpenMP.ProceedingsoftheInternationalConferenceonParallelandDistributedComputing,ApplicationsandTechnologies(PDCAT)(2016).