Abstract: Based on taking into account communication loads and divisible load principle，an optimal pair-wise sequence global alignment distribution strategy is presented on the heterogeneous cluster computing systems that processors have different computing speeds and communication capabilities and memory sizes.This distribution strategy obtains the values of iterations of parallel algorithm and sub-sequence length assigned to every processor on the heterogeneous cluster system.The experimental results on the cluster of heterogeneous personal computers show that the present parallel algorithm for pair-wise sequence global alignment is superior to one with the even distribution strategy，and it obtains good speedup and scalability.

Key words: pair-wise sequence alignment, parallel algorithm, heterogeneous cluster systems, divisible loads

摘要： 对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统，考虑通信启动开销，基于可分负载理论，提出一种双序列全局比对问题并行处理的最优分配策略，利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明，提出的双序列全局比对并行算法优于基于平均分配策略的并行比对算法，获得良好的加速和可扩展性。

关键词: 双序列比对, 并行算法, 异构机群系统, 可分负载