Calculate sequence probability using the backward algorithm. This implements the backward algorithm, as described on p5859 of Durbin et al. Returns: o A dictionary containing the backwards variables. This has keys of the form (state letter, position in the training sequence), and values containing the calculated backward variable. Definition at line 107 of file DynamicProgramming.py. 00107 : """Calculate sequence probability using the backward algorithm. This implements the backward algorithm, as described on p5859 of Durbin et al. Returns: o A dictionary containing the backwards variables. This has keys of the form (state letter, position in the training sequence), and values containing the calculated backward variable. """ # all of the different letters that the state path can be in state_letters = self._seq.states.alphabet.letters #  initialize the algorithm # # NOTE: My index numbers are one less than what is given in Durbin # et al, since we are indexing the sequence going from 0 to # (Length  1) not 1 to Length, like in Durbin et al. # backward_var = {} first_letter = state_letters[0] # b_{k}(L) = a_{k0} for all k for state in state_letters: backward_var[(state, len(self._seq.emissions)  1)] = \ self._mm.transition_prob[(state, state_letters[0])] #  recursion # first loop over the training sequence backwards # Recursion step: (i = L  1 ... 1) all_indexes = range(len(self._seq.emissions)  1) all_indexes.reverse() for i in all_indexes: # now loop over the letters in the state path for main_state in state_letters: # calculate the backward value using the appropriate # method to prevent underflow errors backward_value = self._backward_recursion(main_state, i, backward_var) if backward_value is not None: backward_var[(main_state, i)] = backward_value # skip the termination step to avoid recalculations  you should # get sequence probabilities using the forward algorithm return backward_var class ScaledDPAlgorithms(AbstractDPAlgorithms):
