Sorry if this question was already asked. I'm new to sequence analysis, I'm using TraMineR to analyze some sequences with the Optimal Matching. But I need to know the maximum possible cost that can result from using the OM.

I'm using an alphabet like: A,B,C,D,E,F and I have defined a substitution matrix.

Is there any way to know the maximum possible distance or cost of a sequence without creating all possible sequences of the alphabet?

Thanks in advance for your help.


1 Answer 1


The answer is given in

Gabadinho, A., Ritschard, G., Müller, N.S. & Studer, M. (2011), Analyzing and visualizing state sequences in R with TraMineR, Journal of Statistical Software. Vol. 40(4), pp. 1-37.

which is distributed as a vignette with the TraMineR package. Page 29, it is stated that the maximum OM distance between two sequences $x$ and $y$ is

$D_{max}=\min(\ell_{x},\ell_{y}) \cdot \min\big(2{c_I}, \max(S)\big) + c_{I} |\ell_{x}-\ell_{y}|$

where $\ell_x$ and $\ell_y$ are the sequence lengths, $c_I$ the indel cost and $S$ the substitution cost matrix.


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.