
Probabilistic Models
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 subalignment 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.