自适应动态规划序列比对并行算法研究

"基于动态规划的序列比对的并行算法研究 (2011年) - 李大卫 - 同济大学软件学院" 本文主要探讨的是序列比对算法的优化，特别是通过动态规划方法实现的并行化策略。序列比对是生物信息学中的关键任务，用于比较和分析DNA、RNA或蛋白质序列的相似性，对于基因识别、进化关系分析等应用至关重要。传统的序列比对算法如Smith-Waterman和Needleman-Wunsch是基于动态规划的，它们虽然能提供精确的比对结果，但计算量大，不适合处理大规模数据。 作者深入研究了不同类型的序列比对算法，包括两序列比对、多序列比对、局部比对和全局比对，以及渐进和迭代的方法。局部比对关注序列中特定区域的匹配，而全局比对则考虑整个序列的匹配。渐进方法通常适用于多序列比对，通过逐步合并较小的比对结果来构建全局比对。迭代方法则通过反复调整和优化比对结果来提高准确性。 针对动态规划算法的并行性，作者提出了一种自适应策略。在算法的初始和结束阶段，通过设置较小的高度和宽度参数，最大化处理器的利用率，确保大多数处理器参与计算。在计算的中期，通过增大高度和宽度来减少处理器间的通信成本，这有助于优化并行性能。这种自适应策略旨在平衡计算负载，将输入的比对序列均匀分配到各个计算节点，以实现更高效的并行处理。 实验在集群系统上使用MPI（Message Passing Interface）环境进行，结果显示，该并行算法在固定进程数量下，随着序列长度增加，执行时间显著增加；而在固定序列长度下，随着并行进程数量的增加，执行时间显著减少。这表明该算法能够有效地利用序列比对问题的内在并行性，降低时间复杂度，对于处理大规模序列比对问题具有优势。 这篇2011年的研究论文提出了一个创新的自适应动态规划序列比对的并行算法，它在保持比对精度的同时，通过优化并行处理策略，显著提升了计算效率，对于生物信息学领域的序列分析有着重要的实践意义。