You are given two sequences of characters (DNA strands) Xn = (x1, x2, ..., xn) and...

Transcribed Image Text:

You are given two sequences of characters (DNA strands) Xn = (x1, x2, ..., xn) and Ym (y1, y2, ..., ym) and we want to measure their similarity in the following way: we put the two sequences one below the other and try to match the characters one by one. We can add spaces to the two sequences to increase the number of matching characters but for each space a cost of 1 unit is added. If two characters do not match, then we are charged a cost of 3 units. Our goal is to find the layout of the sequences with the least cost. For example: consider the two sequences X7-(C, T, A, C, C, G, G) and Y6 =(T, A, C, A, T, G). One provision is the following: X, C T A C C Y = GG TACAT G 4 pairs of characters have matched this layout, we have added 3 spaces (with cost 1), and a pair has not matched (cost 3). The total cost of this layout equals 6. a) Write the recurrence equation to find minimum comparison cost C (i, j) of sequences Xi and Yj b) Write pseudocode to find minimum comparison cost C (n, m) using a table. Note that this method should not be recursive. c) What is the running time and the space of the above algorithm? You are given two sequences of characters (DNA strands) Xn = (x1, x2, ..., xn) and Ym (y1, y2, ..., ym) and we want to measure their similarity in the following way: we put the two sequences one below the other and try to match the characters one by one. We can add spaces to the two sequences to increase the number of matching characters but for each space a cost of 1 unit is added. If two characters do not match, then we are charged a cost of 3 units. Our goal is to find the layout of the sequences with the least cost. For example: consider the two sequences X7-(C, T, A, C, C, G, G) and Y6 =(T, A, C, A, T, G). One provision is the following: X, C T A C C Y = GG TACAT G 4 pairs of characters have matched this layout, we have added 3 spaces (with cost 1), and a pair has not matched (cost 3). The total cost of this layout equals 6. a) Write the recurrence equation to find minimum comparison cost C (i, j) of sequences Xi and Yj b) Write pseudocode to find minimum comparison cost C (n, m) using a table. Note that this method should not be recursive. c) What is the running time and the space of the above algorithm?