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

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

Calculate sequence probability using the backward algorithm.

This implements the backward algorithm, as described on p58-59 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 p58-59 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):


Generated by  Doxygen 1.6.0   Back to index