User Defined Substitution Cost Matrix

Question

I have a 30x30 symmetric matrix that I would like to use as a substitution cost matrix in TraMineR to analyze sequences of length 10 with an alphabet of 30. When I try to perform OM with this matrix, however, I get an error about the triangle inequality (see below).

Other matrices that I have made by hand seem to work fine (see example below). I thought the subcost matrix could be set any way I want as long as it was symmetric and the dimensions reflected the size of the alphabet. Are there limitations on how I can set the subcosts? Or perhaps something else is causing the problem?

Thanks

> diss1vs <- seqdist(bhpsfup.seqw, method = "OM", indel = .1*maxsub, sm = upsubcosts)
 [>] 536 sequences with 30 distinct events/states
Error in checktriangleineq(sm, warn = FALSE, indices = TRUE, tol = tol) : 
  REAL() can only be applied to a 'numeric', not a 'integer'

Example matrix that works

zeroblock <- diag(6)
zeroblock[zeroblock == 1] <- 0
zeroblock

twoblock <- diag(6)
twoblock[twoblock == 0] <- 2
twoblock[twoblock == 1] <- 2
twoblock

submat.up1 <- cbind(zeroblock,twoblock,twoblock,twoblock,twoblock)
submat.up2 <- cbind(twoblock,zeroblock,twoblock,twoblock,twoblock)
submat.up3 <- cbind(twoblock,twoblock,zeroblock,twoblock,twoblock)
submat.up4 <- cbind(twoblock,twoblock,twoblock,zeroblock,twoblock)
submat.up5 <- cbind(twoblock,twoblock,twoblock,twoblock,zeroblock)
submat.up <- rbind(submat.up1, submat.up2, submat.up3, submat.up4, submat.up5)
submat.up

Answer 1

The substitution costs should respect the triangle inequality, otherwise the resulting distance won't respect it (and won't be a distance but a dissimilarity).

The optimal matching algorithm can be interpreted (if it respects triangle inequality) as the minimum cost required to transform sequence A in sequence B. However, the algorithm (Needlman-Wunsch) does not try to make successive substitutions, but only one. Hence, if you have the following costs (with indel=5):

  A  B  C
A 0  1  3
B 1  0  1
C 3  1  0

Now consider computing the distance between sequences "A" and "C". The optimal matching distance will be 3 (substitution between A and C). But it would have cost less to first substitute A by B (cost 1) and then B by C (cost 1) for a total of 2.

This example illustrates why we should use substitution costs that respect triangle inequality. It ensures that the resulting distance is coherent. The distance between two points should always be equal or less than going through another one.

Answer 2

The triangle inequality requires that the distance between any three points $A$, $B$, and $C$ meets the criteria that the distance between $A$ and $C$ is not larger than the distance between $A$ and $B$ plus the distance between $B$ and $C$. That is, $D(A,C) \le D(A,B) + D(C,B)$.

To guarantee that the substitution cost matrix does not lead to a violation of this rule, the costs should be set so that zeros appear only on the diagonal and any combination of smaller costs is larger than the largest cost.