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.
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
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.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
