Calculate sequence probability using the forward algorithm. This implements the foward algorithm, as described on p5758 of Durbin et al. Returns: o A dictionary containing the foward variables. This has keys of the form (state letter, position in the training sequence), and values containing the calculated forward variable. o The calculated probability of the sequence. Definition at line 42 of file DynamicProgramming.py. 00042 : """Calculate sequence probability using the forward algorithm. This implements the foward algorithm, as described on p5758 of Durbin et al. Returns: o A dictionary containing the foward variables. This has keys of the form (state letter, position in the training sequence), and values containing the calculated forward variable. o The calculated probability of the sequence. """ # 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. # forward_var = {} # f_{0}(0) = 1 forward_var[(state_letters[0], 1)] = 1 # f_{k}(0) = 0, for k > 0 for k in range(1, len(state_letters)): forward_var[(state_letters[k], 1)] = 0 #  now do the recursion step # loop over the training sequence # Recursion step: (i = 1 .. L) for i in range(len(self._seq.emissions)): # now loop over the letters in the state path for main_state in state_letters: # calculate the forward value using the appropriate # method to prevent underflow errors forward_value = self._forward_recursion(main_state, i, forward_var) if forward_value is not None: forward_var[(main_state, i)] = forward_value #  termination step  calculate the probability of the sequence first_state = state_letters[0] seq_prob = 0 for state_item in state_letters: # f_{k}(L) forward_value = forward_var[(state_item, len(self._seq.emissions)  1)] # a_{k0} transition_value = self._mm.transition_prob[(state_item, first_state)] seq_prob += forward_value * transition_value return forward_var, seq_prob def _backward_recursion(self, cur_state, sequence_pos, forward_vars):
