Application Search Of Parallel Genetic Algorithm In Biology Sequence Alignment

The multiple sequence alignment (MSA) is of great value to the research in bioinformatics since it supports the development of Genetic Sciences such as Expecting the functions & structures of Protein, the discovering the Evolutionary Relationships, and developing new medicine. However, MSA problem is known to be NP-hard, more still left undetermined. Obviously, MSA is among the most important and challenging task in computational biology.Algorithms are classified three species: dynamic programming method, progressive method and iterative method. In some sense, they all have some deficiencies. For example, dynamic programming method can align with only 8 sequences; the main disadvantage of progressive algorithm is the local minimum' problem and iterative algorithm is time consuming.Needleman-Wunsch (NW) algorithm is a classical algorithm among the optimum pairwise alignments. Genetic Algorithm (GA) is an approach of iterative algorithms, which appears capable of finding globally optimal multiple alignments. This paper combines NW algorithm with GA for multiple sequences alignment to enhance its speed and precision. This algorithm adopts a new code method to make it adaptable to different lengths and sizes of sequences. We produce random initial population to ensure search for solutions in the whole solution space, select better sections in the parent chromosomes in crossover operator to produce better chromosome, and introduce NW algorithm into mutation operator to speedup local search. To enhance the speed, this paper can dynamically crossover and mutation operate with multi-point according to sequence length. This paper adopts asynchronous communication to decrease the waiting time between processes, to conquer bottleneck problems by synchronous communication and to heighten further operation speed. In conclusion, a series of experimental data and the analysis of results demonstrate that this new approach can find solutions more efficiently than traditional iterative algorithms. Moreover, its solutions are as good as, even better than progressive algorithms in precision except in several special cases.