Give an example of three strings x,y,z such that the optimal alignment of x with y does not appear in any optimal alignment of x,y,z, and the same is true for optimal alignments of x,y and of y,z. Prove your example has this property. (An example where any optimal alignment of x,y,z does not contain an optimal alignment of x,ybut may contain optimal alignments of x,z and/or y,zwill earn you partial credit.)

The most efficient version of the preceding approach we know of for three strings takes an amount of time which becomes impractical as soon as the strings have somewhere between 104 and 105 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'it exist. For example, the alignment of x and y induced by the figure at the top of Q1 would be T1 T2 Note that the column between 23 and y3 got deleted because it consisted of two gaps The most efficient version of the preceding approach we know of for three strings takes an amount of time which becomes impractical as soon as the strings have somewhere between 104 and 105 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'it exist. For example, the alignment of x and y induced by the figure at the top of Q1 would be T1 T2 Note that the column between 23 and y3 got deleted because it consisted of two gaps