Design and analysis of algorithm
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
e 7 7 6 5 5 5 5 5
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
**2.Create a top-down algorithm for the string alignment problem**
A matrix is built as follows:
then then
Where:
## Example
Sequence 1 = ACACACTA Sequence 2 = AGCACACA
**3.What is the time complexity of the algorithm**
## 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.
The key idea is to store results of applying a parser p at position j in a memotable and to reuse results whenever the same situation arises, we also use memoization for refraining redundant computations to accommodate any form of CFG in polynomial time (Θ(n^{4}) for left-recursive grammars and Θ(n^{3}) for non left-recursive grammars). Their top-down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'.
**Reference **
**1 **ICS 161 -- Dept. Information & Computer Science -- UC Irvine 21 Aug 2011, 08:47:13 PDT.
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.
5 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.
6 Miller, Webb and Myers, Eugene (1988). "Optimal alignments in linear space". *Computer Applications in Biosciences (CABIOS)* **4**: 11–17.
**Share with your friends:** |