** 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 *T*^{X}and *S*^{X} are computed as

and

as usual.
This corresponds to computing the EC when all the *Z* subtree is missing.
Since multiplying *T*^{X} and *S*^{X} by a constant has no effect
(as discussed above), we can simply ignore
and use *T*^{X} = *S*^{Y}.

*Gaston Gonnet*

*1998-07-14*