Back to index

python-biopython  1.60
Public Member Functions | Private Member Functions | Private Attributes
Bio.HMM.DynamicProgramming.AbstractDPAlgorithms Class Reference
Inheritance diagram for Bio.HMM.DynamicProgramming.AbstractDPAlgorithms:
Inheritance graph
[legend]

List of all members.

Public Member Functions

def __init__
def forward_algorithm
def backward_algorithm

Private Member Functions

def _foward_recursion
def _backward_recursion

Private Attributes

 _mm
 _seq

Detailed Description

An abstract class to calculate forward and backward probabiliies.

This class should not be instantiated directly, but should be used
through a derived class which implements proper scaling of variables.

This class is just meant to encapsulate the basic foward and backward
algorithms, and allow derived classes to deal with the problems of
multiplying probabilities.

Derived class of this must implement:

o _forward_recursion -- Calculate the forward values in the recursion
using some kind of technique for preventing underflow errors.

o _backward_recursion -- Calculate the backward values in the recursion
step using some technique to prevent underflow errors.

Definition at line 7 of file DynamicProgramming.py.


Constructor & Destructor Documentation

def Bio.HMM.DynamicProgramming.AbstractDPAlgorithms.__init__ (   self,
  markov_model,
  sequence 
)
Initialize to calculate foward and backward probabilities.

Arguments:

o markov_model -- The current Markov model we are working with.

o sequence -- A training sequence containing a set of emissions.

Reimplemented in Bio.HMM.DynamicProgramming.LogDPAlgorithms, and Bio.HMM.DynamicProgramming.ScaledDPAlgorithms.

Definition at line 25 of file DynamicProgramming.py.

00025 
00026     def __init__(self, markov_model, sequence):
00027         """Initialize to calculate foward and backward probabilities.
00028 
00029         Arguments:
00030 
00031         o markov_model -- The current Markov model we are working with.
00032 
00033         o sequence -- A training sequence containing a set of emissions.
00034         """
00035         self._mm = markov_model
00036         self._seq = sequence

Here is the caller graph for this function:


Member Function Documentation

def Bio.HMM.DynamicProgramming.AbstractDPAlgorithms._backward_recursion (   self,
  cur_state,
  sequence_pos,
  forward_vars 
) [private]
Calculate the backward recursion value.

Reimplemented in Bio.HMM.DynamicProgramming.ScaledDPAlgorithms.

Definition at line 102 of file DynamicProgramming.py.

00102 
00103     def _backward_recursion(self, cur_state, sequence_pos, forward_vars):
00104         """Calculate the backward recursion value.
00105         """
00106         raise NotImplementedError("Subclasses must implement")

Here is the caller graph for this function:

def Bio.HMM.DynamicProgramming.AbstractDPAlgorithms._foward_recursion (   self,
  cur_state,
  sequence_pos,
  forward_vars 
) [private]
Calculate the forward recursion value.

Definition at line 37 of file DynamicProgramming.py.

00037 
00038     def _foward_recursion(self, cur_state, sequence_pos, forward_vars):
00039         """Calculate the forward recursion value.
00040         """
00041         raise NotImplementedError("Subclasses must implement")

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 
00108     def backward_algorithm(self):
00109         """Calculate sequence probability using the backward algorithm.
00110 
00111         This implements the backward algorithm, as described on p58-59 of
00112         Durbin et al.
00113 
00114         Returns:
00115 
00116         o A dictionary containing the backwards variables. This has keys
00117         of the form (state letter, position in the training sequence),
00118         and values containing the calculated backward variable.
00119         """
00120         # all of the different letters that the state path can be in
00121         state_letters = self._seq.states.alphabet.letters
00122         
00123         # -- initialize the algorithm
00124         #
00125         # NOTE: My index numbers are one less than what is given in Durbin
00126         # et al, since we are indexing the sequence going from 0 to
00127         # (Length - 1) not 1 to Length, like in Durbin et al.
00128         #
00129         backward_var = {}
00130         
00131         first_letter = state_letters[0]
00132         # b_{k}(L) = a_{k0} for all k
00133         for state in state_letters:
00134             backward_var[(state, len(self._seq.emissions) - 1)] = \
00135               self._mm.transition_prob[(state, state_letters[0])]
00136 
00137         # -- recursion
00138         # first loop over the training sequence backwards
00139         # Recursion step: (i = L - 1 ... 1)
00140         all_indexes = range(len(self._seq.emissions) - 1)
00141         all_indexes.reverse()
00142         for i in all_indexes:
00143             # now loop over the letters in the state path
00144             for main_state in state_letters:
00145                 # calculate the backward value using the appropriate
00146                 # method to prevent underflow errors
00147                 backward_value = self._backward_recursion(main_state, i,
00148                                                           backward_var)
00149 
00150                 if backward_value is not None:
00151                     backward_var[(main_state, i)] = backward_value
00152 
00153         # skip the termination step to avoid recalculations -- you should
00154         # get sequence probabilities using the forward algorithm
00155 
00156         return backward_var
        

Here is the call graph for this function:

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 
00043     def forward_algorithm(self):
00044         """Calculate sequence probability using the forward algorithm.
00045 
00046         This implements the foward algorithm, as described on p57-58 of
00047         Durbin et al.
00048 
00049         Returns:
00050 
00051         o A dictionary containing the foward variables. This has keys of the
00052         form (state letter, position in the training sequence), and values
00053         containing the calculated forward variable.
00054 
00055         o The calculated probability of the sequence.
00056         """
00057         # all of the different letters that the state path can be in
00058         state_letters = self._seq.states.alphabet.letters
00059         
00060         # -- initialize the algorithm
00061         #
00062         # NOTE: My index numbers are one less than what is given in Durbin
00063         # et al, since we are indexing the sequence going from 0 to
00064         # (Length - 1) not 1 to Length, like in Durbin et al.
00065         #
00066         forward_var = {}
00067         # f_{0}(0) = 1 
00068         forward_var[(state_letters[0], -1)] = 1
00069         # f_{k}(0) = 0, for k > 0
00070         for k in range(1, len(state_letters)):
00071             forward_var[(state_letters[k], -1)] = 0
00072 
00073         # -- now do the recursion step
00074         # loop over the training sequence
00075         # Recursion step: (i = 1 .. L)
00076         for i in range(len(self._seq.emissions)):
00077             # now loop over the letters in the state path
00078             for main_state in state_letters:
00079                 # calculate the forward value using the appropriate
00080                 # method to prevent underflow errors
00081                 forward_value = self._forward_recursion(main_state, i,
00082                                                         forward_var)
00083 
00084                 if forward_value is not None:
00085                     forward_var[(main_state, i)] = forward_value
00086                 
00087         # -- termination step - calculate the probability of the sequence
00088         first_state = state_letters[0]
00089         seq_prob = 0
00090 
00091         for state_item in state_letters:
00092             # f_{k}(L)
00093             forward_value = forward_var[(state_item,
00094                                          len(self._seq.emissions) - 1)]
00095             # a_{k0}
00096             transition_value = self._mm.transition_prob[(state_item,
00097                                                          first_state)]
00098 
00099             seq_prob += forward_value * transition_value
00100 
00101         return forward_var, seq_prob

Here is the call graph for this function:


Member Data Documentation

Definition at line 34 of file DynamicProgramming.py.

Definition at line 35 of file DynamicProgramming.py.


The documentation for this class was generated from the following file: