论文部分内容阅读
并行体系结构的优越性应该用来处理超指数增长的生物学数据，这一事实揭示了本论文的两个方面。本文我们提出了一种计算密集型生物学数据分析的解决方案。文中所研究的生物学数据对象是生物序列、结构和网络。此外，我们利用的是不同的并行体系结构，英特尔多核、多核CPU以及集群。
本文第一个贡献是一种新的并行 k路原地归并算法—Lazy-Merge。该归并算法是本论文中整个工作的最后一步。由于本文中提出的生物学计算方法的加速算法是在将生物学数据集分成可并行的较小部分基础上进行处理的，所以该 Lazy-Merge是本文必不可少的一步。最后，一个结果中的每一部分与其他结果进行融合来形成最终结果。
本 Lazy-Merge算法包含三部分。第一部分描述了输入段的划分的过程和目的；这一部分将原来的k路归并任务重定义为大小确定的t个较小的k路归并任务，这里的t为划分数。第二部分描述不连续段的归并过程。最后一部分是以正确顺序使用不完全归并的段的算法。Lazy-Merge时间复杂度分析O(k×log(n/k)).
我们计划使用三种不同的数据。第一种规模上万；他的输入规模在到之间，我们称之为数据集1。第二种有几千万的规模；大约从到，我们称之为数据集2。增加数据集1和数据集2的方法是取其原有规模的两倍；换句话说，将”2”的指数加1。
实验结果显示，Lazy-Merge算法在移动次数和总用时上均胜过已有算法。使用128个线程来处理数据集1和数据集2，Lazy-Merge在与重复2路原地归并任务的比较树的比较中，平均减少了8.5倍的移动次数。移动的次数减少的程度随划分数的增多而上升。另外，对数据集1，Lazy-Merge相比于bitonic算法和Guan’s算法分别具有4.4倍和5.4倍的移动次数下降。对于数据集2，在规模最大的的情况下Lazy-Merge相比于bitonic算法具有3.2倍的移动次数下降。在数据集1的运行时间方面，Lazy-Merge比bitonic和Guan的算法分别快了2.5倍和292倍。在数据集2的运行时间方面，Lazy-Merge相比bitonic算法表现出5.7倍的加速比。
在第二个贡献中，我们通过解决两大不同的问题来处理生物序列。这两大问题是多序列联配(MSA)问题和系统发育树重建问题。
据我们所知，大多数现有的并行MSA问题的解决方法都是在工作站或者网络集群上实现的。这种体系结构的计算机价格比较高，而且对于非专业的用户来说使用比较困难。众所周知，使用配有共享存储器与多核处理器的计算机如今已经普遍存在。
我们提出了一个在多核以及众核体系结构中处理MSA的并行策略—CDAM。CDAM的动机是将大规模序列组分解成若干任何一个 MSA程序都可以处理的小规模子序列组。用集群的方法来分解序列组的原因是序列之间的距离越短，联配出现的错误就会越少。
我们在 CDAM中采用了五种聚类算法：CD-hit，UCLUST，SiLiX，CLUSS和BLASTClust；四种主流的基准：BAliBASE，PREFAB，IRMBASE和OXBench，以及28个大规模人工合成的数据集。实验结果清晰地表明，不同的聚类方法对CDAM的速度和精度的影响各不相同，CDAM(UCLUST)和CDAM(CD-hit)的综合性能最佳。尽管 CDAM(UCLUST)和CDAM(CD-hit)分别平均失去了2.19％和2.87%的联配精确度，但是它们可以将算法的执行时间分别提高151倍和111倍。
此处我们解决的另外一个序列分析问题是系统发育树的构建。一个系统发育（进化）树的构建是计算生物学中的一个重大挑战。系统发育树描述了从 DNA多序列联配或 AA序列（taxa）代表的生物体开始的生物体之间的进化关系。比较分析最近的调查可得出，使用ML方法的最精确、最快速的软件工具是PHYML和RAxML。
我们提出了一个 PhyML的改进方法—Fast-PhyML，Fast-PhyML可以缩小PhyML由于序列数量的增加造成的执行时间增加而带来的差距。对于此处提出的软件工具，我们进行了并行性能测试，结果显示了加速 PhyML的引导计算的潜力。该测试的测试平台是多核和众核体系结构、测试对象是 DNA序列和蛋白序列，获得了相当大的加速比；由于MICCPU协处理器，MIC的加速比比多核更高。
作为第三个贡献，我们处理了生物学结构。我们把蛋白质结构比对作为中心论题。
然而，由于新结构数目持续稳定增长，在个人计算机或服务器上的蛋白质结构比较成为一项棘手的任务。因此，为解决这个问题，急需提供一个大规模的并行工具。
这一工具无论在平均数据库构建还是搜索时间上都表现出线性的近乎完美的加速比。在一个单独的14核的工作站上使用这一工具，数据集3平均可以在1.9和5.6秒内完成搜索，而用3D-BLAST and PSISA则分别需要25和75秒。且这一工具对精确度没有任何影响。
我们的第四个贡献是处理了生物网络。降维和可视化是有效地分析和解释生物网络的高维数据的关键环节。矩阵的分解和可视化，允许用户显示感兴趣的生物网络的基本结构及其随时间演变过程。生物网络可视化面临的是一个巨大的数据集。
我们提供了生物网络快速的NMF。多核和非负矩阵分解的计算密集型任务的多核心版本（NMF）。该工具的目标是使生物网络图更简单和更快速的降维分析。此外，它可以作为众所周知的工具，如Cytoscape的一个插件。
我们利用字符串数据库作为源数据库。然后，针对三种不同的硬件配置，我们从众多的数据集中提取了3个。它们的大小分别是9533，21215和25713的数据集-1，数据集-2和数据集-3。这些数据集上分别用在不同的并行体系结构的多核，众核以及多核集群。实验结果表明，快速的NMF加速比是线性的。
作为最后一个也就是第五个贡献，我们把以上所有组合成一个通用的框架—Bio-Loads-to-Nodes。该框架根据输入的大小确定并行资源 m中的最佳数量，其中N是可用并行资源的数量，也就是内核和（或）计算节点的数目,且 m≤N。然后，框架平衡地管理通过这 m个资源分配生物数据集的过程。之后，框架管理运行数据分析程序的m个实例的执行过程,该过程处理分布式生物学数据集的分区部分。最后，框架将结果中m个不同的部分合并起来。
选定的方案分别是：3D-BLAST、BLAST和用于蛋白质结构比较的CpG岛搜索器，序列比对和CpG岛取景器。
对于独立的多核节点，该框架几乎实现了对3D-BLAST和BLAST分别可达7.5倍与7倍的线性加速比，而CpG Island finder的加速比只提高了5倍。这是因为加速比随着串行程序的运行时间增加而增加，CpG Island finder由于在该实验中花费的时间最短从而加速比的值比最低。
对于一个具有5个节点，总共35个内核的集群而言，3D-BLAST和BLAST分别有32和28倍的线性加速比，同时，由于同样原因的限制，CpG Island finder的加速比仅仅被限制在10倍及以内。
本文第一个贡献是一种新的并行 k路原地归并算法—Lazy-Merge。该归并算法是本论文中整个工作的最后一步。由于本文中提出的生物学计算方法的加速算法是在将生物学数据集分成可并行的较小部分基础上进行处理的，所以该 Lazy-Merge是本文必不可少的一步。最后，一个结果中的每一部分与其他结果进行融合来形成最终结果。
本 Lazy-Merge算法包含三部分。第一部分描述了输入段的划分的过程和目的；这一部分将原来的k路归并任务重定义为大小确定的t个较小的k路归并任务，这里的t为划分数。第二部分描述不连续段的归并过程。最后一部分是以正确顺序使用不完全归并的段的算法。Lazy-Merge时间复杂度分析O(k×log(n/k)).
我们计划使用三种不同的数据。第一种规模上万；他的输入规模在到之间，我们称之为数据集1。第二种有几千万的规模；大约从到，我们称之为数据集2。增加数据集1和数据集2的方法是取其原有规模的两倍；换句话说，将”2”的指数加1。
实验结果显示，Lazy-Merge算法在移动次数和总用时上均胜过已有算法。使用128个线程来处理数据集1和数据集2，Lazy-Merge在与重复2路原地归并任务的比较树的比较中，平均减少了8.5倍的移动次数。移动的次数减少的程度随划分数的增多而上升。另外，对数据集1，Lazy-Merge相比于bitonic算法和Guan’s算法分别具有4.4倍和5.4倍的移动次数下降。对于数据集2，在规模最大的的情况下Lazy-Merge相比于bitonic算法具有3.2倍的移动次数下降。在数据集1的运行时间方面，Lazy-Merge比bitonic和Guan的算法分别快了2.5倍和292倍。在数据集2的运行时间方面，Lazy-Merge相比bitonic算法表现出5.7倍的加速比。
在第二个贡献中，我们通过解决两大不同的问题来处理生物序列。这两大问题是多序列联配(MSA)问题和系统发育树重建问题。
据我们所知，大多数现有的并行MSA问题的解决方法都是在工作站或者网络集群上实现的。这种体系结构的计算机价格比较高，而且对于非专业的用户来说使用比较困难。众所周知，使用配有共享存储器与多核处理器的计算机如今已经普遍存在。
我们提出了一个在多核以及众核体系结构中处理MSA的并行策略—CDAM。CDAM的动机是将大规模序列组分解成若干任何一个 MSA程序都可以处理的小规模子序列组。用集群的方法来分解序列组的原因是序列之间的距离越短，联配出现的错误就会越少。
我们在 CDAM中采用了五种聚类算法：CD-hit，UCLUST，SiLiX，CLUSS和BLASTClust；四种主流的基准：BAliBASE，PREFAB，IRMBASE和OXBench，以及28个大规模人工合成的数据集。实验结果清晰地表明，不同的聚类方法对CDAM的速度和精度的影响各不相同，CDAM(UCLUST)和CDAM(CD-hit)的综合性能最佳。尽管 CDAM(UCLUST)和CDAM(CD-hit)分别平均失去了2.19％和2.87%的联配精确度，但是它们可以将算法的执行时间分别提高151倍和111倍。
此处我们解决的另外一个序列分析问题是系统发育树的构建。一个系统发育（进化）树的构建是计算生物学中的一个重大挑战。系统发育树描述了从 DNA多序列联配或 AA序列（taxa）代表的生物体开始的生物体之间的进化关系。比较分析最近的调查可得出，使用ML方法的最精确、最快速的软件工具是PHYML和RAxML。
我们提出了一个 PhyML的改进方法—Fast-PhyML，Fast-PhyML可以缩小PhyML由于序列数量的增加造成的执行时间增加而带来的差距。对于此处提出的软件工具，我们进行了并行性能测试，结果显示了加速 PhyML的引导计算的潜力。该测试的测试平台是多核和众核体系结构、测试对象是 DNA序列和蛋白序列，获得了相当大的加速比；由于MICCPU协处理器，MIC的加速比比多核更高。
作为第三个贡献，我们处理了生物学结构。我们把蛋白质结构比对作为中心论题。
然而，由于新结构数目持续稳定增长，在个人计算机或服务器上的蛋白质结构比较成为一项棘手的任务。因此，为解决这个问题，急需提供一个大规模的并行工具。
这一工具无论在平均数据库构建还是搜索时间上都表现出线性的近乎完美的加速比。在一个单独的14核的工作站上使用这一工具，数据集3平均可以在1.9和5.6秒内完成搜索，而用3D-BLAST and PSISA则分别需要25和75秒。且这一工具对精确度没有任何影响。
我们的第四个贡献是处理了生物网络。降维和可视化是有效地分析和解释生物网络的高维数据的关键环节。矩阵的分解和可视化，允许用户显示感兴趣的生物网络的基本结构及其随时间演变过程。生物网络可视化面临的是一个巨大的数据集。
我们提供了生物网络快速的NMF。多核和非负矩阵分解的计算密集型任务的多核心版本（NMF）。该工具的目标是使生物网络图更简单和更快速的降维分析。此外，它可以作为众所周知的工具，如Cytoscape的一个插件。
我们利用字符串数据库作为源数据库。然后，针对三种不同的硬件配置，我们从众多的数据集中提取了3个。它们的大小分别是9533，21215和25713的数据集-1，数据集-2和数据集-3。这些数据集上分别用在不同的并行体系结构的多核，众核以及多核集群。实验结果表明，快速的NMF加速比是线性的。
作为最后一个也就是第五个贡献，我们把以上所有组合成一个通用的框架—Bio-Loads-to-Nodes。该框架根据输入的大小确定并行资源 m中的最佳数量，其中N是可用并行资源的数量，也就是内核和（或）计算节点的数目,且 m≤N。然后，框架平衡地管理通过这 m个资源分配生物数据集的过程。之后，框架管理运行数据分析程序的m个实例的执行过程,该过程处理分布式生物学数据集的分区部分。最后，框架将结果中m个不同的部分合并起来。
选定的方案分别是：3D-BLAST、BLAST和用于蛋白质结构比较的CpG岛搜索器，序列比对和CpG岛取景器。
对于独立的多核节点，该框架几乎实现了对3D-BLAST和BLAST分别可达7.5倍与7倍的线性加速比，而CpG Island finder的加速比只提高了5倍。这是因为加速比随着串行程序的运行时间增加而增加，CpG Island finder由于在该实验中花费的时间最短从而加速比的值比最低。
对于一个具有5个节点，总共35个内核的集群而言，3D-BLAST和BLAST分别有32和28倍的线性加速比，同时，由于同样原因的限制，CpG Island finder的加速比仅仅被限制在10倍及以内。