1. What is the time complexity of the bottom-up string alignment algorithm ? Bottom-up

Name Ben Maina Wanjohi

Reg P58/76011/2012

Assignment 3

Course code ics801

Date 4^h July 2012

Assignment III

1.What is the time complexity of the bottom-up string alignment algorithm ?
Bottom-up

Bottom up approach is to try solving the sub problems first and use their solutions to build-on and arrive at solutions to bigger sub problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub problems by using the solutions to small sub problems.

Example

n e m a t o d e

m 6 6 6 5 5 4 4 4

p 5 5 5 5 5 4 4 4

t 5 5 5 5 5 4 4 4

y 4 4 4 4 4 4 4 4

There are 2 complexity involved a)- Time complexity

b)-space complexity

a) -Time Complexity:

Time complexity of optimal alignment is product O(nm),this is bacause when computing value of the cell (i, j), only cells (i − 1, j − 1), (i, j − 1), (i − 1, j) are examined) constant time. There are (n + 1)(m+ 1) cells ) O(nm) time complexity.

When computing the value for a specific cell (i; j) only cells (i -1; j- 1), (i; j -1) and (i - 1; ) are examined, along with two characters Si and Tj. Hence, to fill in one cell takes a constant number of cell examinations and comparisons. There are n*m cells in the table. So the time complexity is also O(nm).

b)-Space complexity:

Space complexity is O(n), if only M(x, y) is required, and O(nm) for the reconstruction of the alignment. Row-wise computation of the matrix, for computing row k, only row k−1 must be stored) O(n) space. For reconstructing the alignment, all trace back pointers must be stored) O(nm) space

A matrix is built as follows:

Where:

• 
  = Strings over the Alphabet
  
• 
  
  
• 
  
  
• 
  - is the maximum Similarity-Score between a suffix of a[1...i] and a suffix of b[1...j]
  
• 
  , '-' is the gap-scoring scheme
  

Example

Time complexity is when top-down parser tries to parse an ambiguous input, it may need exponential number of steps (with respect to the length of the input) to try all alternatives in order to produce all possible output, which eventually would require exponential memory space. The problem of exponential time complexity in top-down constructed as sets of mutually recursive functions.

2 Stephen F. Altschul; and Bruce W. Erickson (1986). "Optimal sequence alignment using affine gap costs". Bulletin of Mathematical Biology 48: 603–616. DOI:10.1007/BF02462326.

3 Miller, Webb and Myers, Eugene (1988). "Optimal alignments in linear space". Computer Applications in Biosciences (CABIOS) 4: 11–17.

4 Smith, Temple F.; and Waterman, Michael S. (1981). "Identification of Common Molecular Subsequences". Journal of Molecular Biology 147: 195–197. DOI:10.1016/0022-2836(81)90087-5. PMID 7265238.