(a) Give an example of three strings x, y, z such that in any optimal alignment of x, y, z, at least one of the pairs (x, y) or (y, z) or (x, z) is not optimally aligned. Prove your example has this property. (An example where some optimal alignment of x, y, z does not contain an optimal alignment of x, y but may contain optimal alignments of x, z and/or y, zwill earn you partial credit.)

(b) (7 pts) Prove that the gap between the cost of the pairwise optimal alignments and the pairwise alignments induced by an optimal 3-way alignment can be arbitrarily large. More symbolically, let dxy denote the cost of an optimal alignment of x and y, and for an alignment of x, y, z, let dxy() denote the cost of the pairwise alignment of x and y which is induced by . Your goal here is: for all c > 0, construct three strings x, y, z such that max{dxy() dxy, dxz() dxz, dyz() dyz} > c for all three-way alignments . (Suppose all three strings have length n; how big can you make the gap c as a function of n, asymptotically?)

2. The most efficient version of the preceding approach we know of for three strings takes ngs have somewhere an amount of time which becomes impractical as soon as the stri between 10 and 10 characters (which are still actually fairly small sizes if one is considering aligning, e. .g, genomes). Because of this, people seek faster heuristic algo- rithms, and this is even more true for aligning more than three strings. One natural approach to faster multi-string alignment is to first consider optimal pairwise align ments and somehow use this information to help find the multi-way alignment. Here we show that naive versions of such a strategy are doomed to fail. Given an alignment of three strings, we may consider the 2-string alignments it induces just consider two of the rows of the alignment at a time. If both of those rows have a gap in some column, we treat the pairwise alignment as though that column doesn't exist. For example, the alignment of r and y induced by the figure at the top of Q1 would be Note that the column between rs and ys got deleted because it consisted of two gaps 2. The most efficient version of the preceding approach we know of for three strings takes ngs have somewhere an amount of time which becomes impractical as soon as the stri between 10 and 10 characters (which are still actually fairly small sizes if one is considering aligning, e. .g, genomes). Because of this, people seek faster heuristic algo- rithms, and this is even more true for aligning more than three strings. One natural approach to faster multi-string alignment is to first consider optimal pairwise align ments and somehow use this information to help find the multi-way alignment. Here we show that naive versions of such a strategy are doomed to fail. Given an alignment of three strings, we may consider the 2-string alignments it induces just consider two of the rows of the alignment at a time. If both of those rows have a gap in some column, we treat the pairwise alignment as though that column doesn't exist. For example, the alignment of r and y induced by the figure at the top of Q1 would be Note that the column between rs and ys got deleted because it consisted of two gaps