5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does this mean that we always have to specify BOTH indel and substitution costs in order to arrive at Optimal Matching distances? $\endgroup$
    – histelheim
    Nov 17, 2012 at 0:14
  • 2
    $\begingroup$ For optimal matching (method="OM"), the seqdist function uses 1 as default indel cost, but you have to provide either a substitution cost matrix or a method for computing one ("TRATE" or "CONSTANT"). Alternatively you can use method="LCS" which corresponds to OM with a unit indel cost and a constant substitution cost of 2. $\endgroup$
    – Gilbert
    Dec 4, 2012 at 16:41
  • $\begingroup$ This "common practice" is documented by Abbott/Tsay (2000: 12f.). Nonetheless, its usefulness may depend on the variance of your substitution costs. For example, if your min. and max. value for a substitution are almost equal, then this rule of thumb indel costs yield almost the same results as LCS which accidently also conforms to this rule. Beware, LCS uses only indels! Lesnard (2010: 396f.) and Robette/Bry (2012: 15f.) give a more detailed account on the issue of indel costs and the relation between OM (Levenshtein I), LCS (Levenshtein II) and Hamming distances. $\endgroup$
    – non-numeric_argument
    Jun 19, 2013 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.