Algorithms for Molecular Biology Fall Semester, 2001

s of lengths j 1 , j 2 , . . . , j r of the sequences x 1 , x 2 , . . . , x r , respectively. We define D(0, 0, . . . , 0) = 0 And we calculate D(j 1 , j 2 , . . . , j r ) = min ##{0,1} , ##=0 {D(j # 1 , j 2 # 2 , . . . , j r # r ) + #(# 1 x j 1 , . . . , # r x jr )} where # is the cost function, and # = (# 1 , # 2 , ..., # n ) # {0, 1} is a vector that indicates the directions of alignment progress in the hyper-cube. The size of the hyper-cube is O( j=1 n j ), where n j is the length of x j , where computation of each of each entry consider 2 -1 others. If n 1 = n 2 = . . . = n r = n, the space complexity is of O(n ) and the time complexity is O(2 ) O(computation of the # function). Hence the exact solution, using dynamic programming, is practical for only a small number of strings. Moreover, the exact multiple alignment problem, using sum-of-pairs or evolutionary-tree scoring metrics, has be proven to be NP-complete [9]. 4.1.2 Scoring Metric