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.
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).
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:
= Strings over the Alphabet
- is the maximum Similarity-Score between a suffix of a[1...i] and a suffix of b[1...j]
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 (Θ(n4) for left-recursive grammars and Θ(n3) 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'.
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 Biology48: 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 Biology147: 195–197. DOI:10.1016/0022-2836(81)90087-5. PMID7265238.
5 Stephen F. Altschul; and Bruce W. Erickson (1986). "Optimal sequence alignment using affine gap costs". Bulletin of Mathematical Biology48: 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.