Problem $1(25$ points$)$ Multiple Sequence Alignment

$($a$)(12$ points$)$ Consensus multiple alignment versus sum$-$of$-$pairs multiple alignment. Definitions: $($adapted

from Gusfield, p$.352)$

$(1)$ Given a multiple alignment $M$ of a set of strings $S,$ the consensus character of column $i$ of $M$ is the

character that maximizes the summed score between the character and all the characters in column $i.($In

case of ties, say by convention that we prefer A over C over G over T over 'gap'$).$ The score of $($gap$,$

gap$)$ is $0.$ Let $d(i)$ denote that maximum summed score in column $i.$

$(2)$ The consensus string $S_M$ derived from alignment $M$ is the concatenation of the consensus characters

for each column of $M.$

$(3)$ The alignment score of $S_M$ equals to the sum of column scores $d(S_M)=d(1)+$dots$+d(m),$ where

$m$ has $m$ columns.

$(4)$ The optimal consensus multiple alignment is a multiple alignment $M$ for input string set $S$ whose

consensus string $S_M$ has the largest alignment score over all possible multiple alignments of $S.$

Example:

$S=\{AGCC,$ACC,$TCC\},$ and match, mismatch, gap $=+2,-2,-3.$ Consider the following alignments:

$M_1$:$\{AGCC,A-CC,T-CC\}$;$S_{M_1}=$ A$-$CC$,$ and $d(S_{M_1})=(+2)+(-3)+(+6)+(+6)=11.$

$M_2$:$\{AGCC,A-CC,-TCC\}$;$S_{M_2}=$ AGCC, and $d(S_{M_2})=(+1)+(-3)+(+6)+(+6)=10.$

Show an example with three or more sequences where all optimal multiple alignments according to the

above model are different from all optimal alignments according to the Sum$-$Of$-$Pairs model. In other

words, since there may be several equally$-$scoring optimal alignments, the set of optimal alignments for

the consensus model must be disjoint from the set of optimal alignments for the Sum$-$Of$-$Pairs model.

Assume either a match, mismatch, and gap penalty of $(+2,-2,-3)$ or $(+2,-1,-1)($you may find the

second set of scoring parameters easier to prove$).$ Let the alphabet be $\{A,C,G,T\}.$

$($b$)(13$ points$)$ Phylogenetic$-$treebased alignment.