POSTER NO: 72

An Improved Alignment Algorithm

¹Min Zhang, ²Junhua Zhang
¹Department of Computer Science and Engineering, Dalian University of Technology, China, No. 2, Linggong Road, Dalian, China, ²Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, No. AI, Zhong Guan Cun Nan Si Jie, Beijing, China

The algorithm of Smith & Waterman for identification of maximally similar subsequences is extended to allow identification the global similarity of two sequences. The score matrix is calculated by substitution scores BLOSUM62 and a cost of a+b*k for gaps of length k. The maximally similar subsequences are given by the algorithm of Smith-Waterman, and then the algorithm is invoked recursively to the remnant subsequences until the left and right ends just like the middle order of tree. The score matrix of left subsequence need not be computed, but the right one needs to be.