Study On Parallel Processing For Sequence Alignment On Heterogeneous Cluster Computing Systems

Sequence alignment is one of the important research contents of bioinformatics, and is also a basic method of the sequence analysis tasks. It mainly studies the optimization correspondence among the sequence, by using a distance function or a similar fraction to measure the similarity of sequences. Sequence alignment has vast significance on the analysis of molecular structure and functions, so many researchers have been investigating its efficient computing approaches. In many applications, the length of the sequences is very long, it is time-consuming to solve the sequence alignment problem even though the fastest sequential algorithm is executed. So it is necessary to design highly efficient parallel algorithm for sequence alignment. Due to high performance and low cost of the cluster computing systems, parallel processing for sequence alignment on the cluster computing systems is very meaningful in practice.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 slave processor on the heterogeneous cluster system. The experimental results on the cluster of heterogeneous personal computers show that the time for the present parallel algorithm for pair-wise sequence global alignment decreases 10%～60%, compared to the even distribution strategy, and it obtains good speedup and scalability.Multiple sequences local alignment is another important sequence alignment problem. By taking into account communication loads and the assigned processor distribution order and divisible load principle, an optimal parallel processing distribution strategy for multi-sequence local alignment is presented on the heterogeneous cluster computing systems that processors have different computing speeds and communication capabilities and memory sizes, and a mathematics programming model for solving the given problem is proposed, by considering the optimal assigned processor distribution order. The experimental results on the cluster of heterogeneous personal computers show that the time for the present parallel algorithm for multi-sequence local alignment decreases 13%～35%, compared to the even distribution strategy, and it obtains good speedup and scalability.