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

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