Parallel Optimization Design And Implementation Of Biological Sequence Alignment Algorithm

Biological sequence alignment is the foundation and core of bioinformatics. With the rapid development of biological science, the information of the sequence of protein and nucleic needed to study is dramatically increasing. The time complexity of common double sequence alignment algorithm is O(N2). The multiple sequence alignment time complexity is higher. With the increase of the length of the sequence and the enlargement of the comparison scale, the time cost is unbearable. So, if the potential parallelism of algorithm can be mined, and algorithm can be parallelized via data partitioning and pipelining processing, so as to make it executed in parallel on multiple processors, the time efficiency can be greatly increased.Firstly, this paper introduces the concepts of biological sequence alignment and parallel algorithm, and conducts parallel design of Needleman-Wunsch algorithm adopting the mode of pipeline processing. Based on it, several parallel sequence alignment algorithms are put forward. By finding multiple checkpoints, dividing a matrix into several parts, and making processors executing the Hirschberg algorithm in parallel, Hirschberg algorithm is parallelized. By building suffix tree and acquiring MUMs(Maximum Unique Matches) in parallel using the mechanism of active node and active node link, MUMmer algorithm is parallelized. FASTA algorithm is parallelized via acquiring and enlarging hot spots by means of diagonal parallel, and acquiring in parallel distances between the two hot spots on different diagonals by dividing the distance matrix into parts. The Clustal W algorithm is parallelized via acquiring the distances of all double sequence alignments through dividing distance into parts, as well as merging from the leaves of evolutionary tree to the root in parallel.Finally, the above four algorithms and their parallel algorithms are implemented respectively. The running time of serial algorithms and that of parallel algorithms under dual-core and quad-core are compared, and the results show that compared with serial algorithms, the proposed parallel algorithms is superior in terms of speed, and a sound speedup is thus obtained. So it is more suitable for multi-core architecture.