Indels.

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^Xand S^X are computed as

$$T^X = S^Y Pr \{ \mbox{deletion of} \; Z \}$$

and

$$S^X = \left ( M^{d_X} \right )^{'} T^X$$

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 $Pr \{ \mbox{deletion of}\;Z \}$and use T^X = S^Y.