1-For a pair of strings v = v1 . . . vn and w = w1 . . .wm, define M(v,w) to be the matrix whose (i, j)th entry is the score of the optimal global alignment which aligns the character vi with the character wj . Give an O(nm) algorithm which computes M(v,w).

Define an overlap alignment between two sequences v = v1 . . . vn and w = w1 . . .wm to bean alignment between a suffix of v and a prefix of w. For example, if v = TATATA and w = AAATTT, then a (not necessarily optimal) overlap alignment between v and w is ATA AAA Optimal overlap alignment is an alignment that maximizes the global alignment score between vi, . . . , vn and w1, . . .wj , where the maximum is taken over all suffixes vi, . . . , vn of v and all prefixes w1, . . .wj of w.

2-Design a greedy algorithm for the Multiple Breakpoint Distance problem and evaluate its approximation ratio.

3-Design a divide-and-conquer algorithm for the Motif Finding problem and estimate its running time. Have you improved the running time of the exhaustive search algorithm?