Given two strings X and Y , respectively, of length m and n defined over a set Σ = {a1, a2, · · · , ak} of finitely many symbols, we are interested in computing an optimal (i.e., minimum cost)...

Given two strings X and Y , respectively, of length m and n defined over a set Σ = {a1, a2, · · · , ak}
of finitely many symbols, we are interested in computing an optimal (i.e., minimum cost) alignment of two strings, where two possible alignments are defined as (i) a mismatch with cost
cm and (ii) a gap with cost dg.
Consider the following two sequences defined over Σ = {A, G, C, T}, where
X = { A A C A G T T A C C}
Y = { T A A G G T C A}
Consider the following two alignments in which the first one is with total cost 2cm + 4cg and
the second one is with total cost 3cm + 2cg.
X = { − A A C A G T T A C C}
Y = { T A A − − G G T − C A}
X = { A A C A G T T A C C}
Y = { T A − A G G T − C A}
Depending on the values of cm and cg, an alignment with the minimum total cost must be
determined. Apply your algorithm in (a) to compute an optimal alignment of X and Y . If
multiple solutions exist, show all of them.
(a) Give a dynamic programming algorithm to find an alignment with minimum total cost.
(b) Apply your algorithm in (a) to compute an optimal alignment of X = acd and Y = caabd,
where cm = 3 and cg = 2. Show all your work.