next up previous
Next: Conclusions Up: Probabilistic Dynamic Programming and Previous: Normalization.


Insertions/deletions are handled in the same way they would be handled by the standard DP algorithms [15,10]. The cost of a deletion is known to depend on the PAM distance of the aligned sequences [3] and there exist approximations to compute them based on the distance alone. In case DP chooses an indel, one of the subtrees is viewed as having had a deletion and this deletion has to be propagated to the entire aligned subtree. If X is a node with descendants Y and Z, and DP chooses Y to be an insertion, i.e. Y is not aligned to anything, then TXand SX are computed as

\begin{displaymath}T^X = S^Y Pr \{ \mbox{deletion of} \; Z \} \end{displaymath}


\begin{displaymath}S^X = \left ( M^{d_X} \right )^{'} T^X \end{displaymath}

as usual. This corresponds to computing the EC when all the Z subtree is missing. Since multiplying TX and SX by a constant has no effect (as discussed above), we can simply ignore $Pr \{ \mbox{deletion of}\;Z \}$and use TX = SY.

Gaston Gonnet