序列比对是生物信息学的核心研究内容之一,也是各种序列分析任务的基本方法。它研究序列之间的优化对应,即用一个距离函数或者相似分数来度量序列之间的相似性和非相似性。序列比对对研究分子结构与功能预测具有重要意义,因此其计算方法得到人们高度重视。在实际应用中,序列比对的规模很大,即使利用最快的串行比对算法也很耗时,因此需要设计高效的并行算法以快速求解这类问题。由于机群计算系统具有高性能和低成本的特点,所以在异构机群系统上研究序列比对算法的并行处理具有重要的现实意义。本文基于可分负载理论的最优原则,对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,与平均分配策略相比,本文提出的最优分配策略进行双序列全局比对并行处理所需的时间明显缩短,并获得良好的加速和可扩展性。多序列局部比对是另一个重要的序列比对问题。本文针对处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,给定处理机分配顺序,基于可分负载理论提出一种多序列局部比对问题并行处理的最优分配策略,给定了处理机最优分配顺序,给出并行求解多序列局部比对问题所需时间的数学规划模型。异构PC机群系统上的实验结果表明,本文提出的最优分配策略进行多序列局部比对并行处理所需的时间比按平均分配策略的算法所需时间短,并获得良好的加速和可扩展性。