Parallel Local Alignment Algorithm for Multiple Sequences on Heterogeneous Cluster Systems

By taking into account communication startup overhead and the assigned processor distribution order and by applying hashing technique, a novel sequence distribution strategy is presented and the parallel local alignment algorithm for multiple sequences is designed on the heterogeneous cluster system that the computing nodes have different computing speeds and communication capabilities based on divisible load principle. The experimental results on the cluster system with heterogeneous personal computers show that, compared with the parallel algorithm with the average sequence distribution approach, the parallel local alignment algorithm for multiple sequences with the presented sequence distribution strategy can decrease the execution time of 13%~35%, and it can obtain good speedup and scalability.