1. Consider the pair of sequences, CGTC and TGTC. Use the Needleman
& Wunsch dynamic programming algorithm to ﬁnd an optimal alignment of the sequences (assume a linear gap penalty of -1, a match score
of +1 and a mismatch penalty of -1). How many optimal alignments
are there? Your answer should show your work and include a fully
populated array of sub-alignment scores.
2. If G, a symmetric square matrix, is the generator matrix of a continuous-
time Markov Chain over a ﬁnite state space with equilibrium frequency
vector π, prove that πj = 1/M ∀ j , where M is the number of states.