What is the relationship between substitution cost matrix and indel costs?

Question

In TraMineR I might compute dissimilarities as such:

properties <- matrix(c(# left, married, child ,divorced
  0, 0, 0, 0,  # parent
  1, 0, 0, 0,  # left
  0, 1, .5, 0, # marr
  1, 1, 0, 0,  # left+marr
  0, 0, 1, 0,  # child
  1, 0, 1, 0,  # left+child
  1, 1, 1, 0,  # left+marr+child
  .5, 1, .5, 1 # divorced
), 8, 4, byrow=TRUE)

sm <- as.matrix(dist(properties))
indel <- .5*max(sm)
dOM <- seqdist(biofam.seq, method="OM", indel=indel, sm=sm)

Why do I provide both indel costs (indel) and substitution cost matrix (sm)? I thought they were one and the same? Please help me to understand the relationship between the substitution cost matrix and the indel costs.

Answer 1

There is no analytic relationship between the substitution costs and the indel cost.

The substitution cost between two states, say left and married is the cost of replacing either left with married or married with left.

The indel cost, is the cost of inserting an element in the sequence. It is also the cost of deleting an element.

With the indel you control the allowed time warp in sequence comparison. The higher the indel cost, the more you penalize time warp. Setting the indel as an arbitrary high value will prevent any time shift in sequence comparison (the result will be equivalent to the Hamming distance). Lowering the indel on the contrary tends to prevent direct substitutions. Without indel, it would not be possible to measure the dissimilarity between sequences of unequal lengths for example.

A common practice is to set the indel at half the maximum substitution cost meaning that it will never cost less to make an insert and a delete in place of a substitution. This does not mean that insert/delete will not be used. In the following example, for instance,

ABABABAB
BABABABA

we can align the sequences by inserting a A at the beginning of the second sequence and deleting the ending A. Without insert/delete, 8 substitutions would be necessary, which would most probably be more costly.

Hope this helps.

Gilbert