Biological Sequence Alignment Problem

Bioinformatics is a new crossing discipline which utilizes modern computational technology to handle and research the data of biology. In bioinformatics, sequence alignment is the most foundation problem. How to obtain better alignment of sequences efficiently is the important theme in it. The research of sequence alignment algorithm plays an important role in bioinformatics.After giving an introduction of all kind algorithms in this field and discussing the earliest global pairwise sequence alignment algorithm — Needleman-Wunsch Dynamic Programming algorithm, the paper analyzes the disvantages of all pairwise sequence alignment algorithms and its heuristic alignment algorithms. Also the paper deduces a new heuristic algorithm based on High-Segment Pairs. It can improve the alignment as well as it can reduce the runtime of the algorithm.The problem of multiple sequence alignment is a NP-Complete problem. The fact that the multiple sequence alignment problem of high complexity has led to the development of different algorithms. The paper introduces the advantages and disvantages of all the algorithms. Lastly, the paper presents a new multiple sequence algorithm(GA-DP) based on HSP where daynamic programming is introduced into the genetic algorithm. GA-DP algorithm has a lower complexity and can obtain a proximate satisfying optima for the multiple sequence alignment problem in reasonable computational time.