The Research And Implementation Of Biological Sequence Alignment

Bioinformatics is a new crossing discipline which utilizes modern computational technology to handle and research the data of biology. In this field, sequence alignment, which is the most fundamental problem, has great significance to find the function, structure and evolutional information of nucleic acid and protein sequences. How to obtain better alignment of sequences efficiently is the important theme in bioinformatics.The paper researches global sequence alignment algorithm such as dynamic programming algorithm, local sequence alignment algorithm such as Smith-Waterman, BLAST, FASTA. Based on the research of these algorithms` design and the analysis of their performance, a pair-wise sequence alignment algorithm based on suffix tree is implemented. There are three major steps: establish suffix tree, search for common strings and link common strings. The algorithm is based on suffix-tree with suffix link, make full use of the character of suffix link, rapidly position the next suffix internal node, to accomplish the suffix tree in linear time; otherwise, it is easy to find common string utilizing suffix tree, and the second step is accomplished in linear time too; In the third step, using pruning strategy to reduce the running time of the algorithm; the expansion of the depth and breadth combination to advance the accuracy of the algorithm. Experimental results show that the algorithm`s running time is better than Smith-Waterman algorithm; in the accuracy, better than the BLAST algorithm.The paper researches multiple sequence alignment algorithm such as progressive sequence alignment and iterative sequence alignment, analyzes their advantage ,disadvantage and applicable scope. It researches and implement progressive sequence alignment ClustalW.Based on the research of all these algorithms, it implemented a biological sequence alignment system, which utilizes SPLSA to implement pair-wise sequence alignment, ClustalW to implement multiple sequence alignment. The system also provides appendant functions such as document search, result display and result conservation.