Logo Search packages:      
Sourcecode: python-biopython version File versions

def Bio::HMM::DynamicProgramming::AbstractDPAlgorithms::forward_algorithm (   self  )  [inherited]

Calculate sequence probability using the forward algorithm.

This implements the foward algorithm, as described on p57-58 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 p57-58 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):


Generated by  Doxygen 1.6.0   Back to index