Question

Let S and T be two sequences of length n and m, respectively. When calculating the dynamic programming table to find the optimal global alignments between the two sequences S and T, we can keep pointers to find the optimal alignments by following these pointers from cell (n, m) to cell (0, 0). Each of the paths represents a different optimal alignment for the two sequences.

a) Give an algorithm in O(nm) which calculates the number of different alignments between the two sequences. (Hint : Use dynamic programming).

b) Build the dynamic programming table of your algorithm for the sequences X = AABAACAAA and Y = ABACAA.

Answer 1

Answer:

Alphabet:

An alphabet, denoted by Σ, is a finite, unordered set of symbols; e.g., DNA: ΣD = {A, C, G, T} RNA: ΣR = {A, C, G, U} Amino acids: ΣAA = {A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y }

Sequences or Strings:

A sequence or string, s, is a finite succession of the symbols in Σ. We say that s ∈ Σ ∗ , where Σ∗ is the set of all sequences over alphabet Σ, including the empty sequence, ∅. For example, Σ∗ R = {∅, A, C, G, U, AA, AC, AG, AU, CA, CC, CG, CU, . . .}. Given a sequence s of length m, we use s[1]s[2] · · · s[m] to denote the symbols in s. Sometimes, we will use s1s2 · · · sm for convenience. Subsequences: A subsequence of s is any sequence obtained by removing zero or more symbols from s. The sequences CATA and CTG are subsequences of CATTAG. AATTCG is not. A proper subsequence is a subsequence obtained by removing one or more symbols from s. Substrings: A substring of s is a subsequence of s consisting of consecutive symbols in s. Given a sequence, s, of length m, the substring that begins with s[i] and ends with s[j] is denoted s[i . . . j], 1 ≤ i ≤ j ≤ m. The sequence CAT is a substring of CATTAG. CATA is not. A prefix of s is denoted s[1 . . . j], j ≤ m. A suffix of s is denoted s[i . . . m], 1 ≤ i.

#Could you please leave a THUMBS UP for my work..