Optimal matching is a sequence analysis method used in social science, to assess the dissimilarity of ordered arrays of tokens that usually represent a time-ordered sequence of socio-economic states two individuals have experienced. Once such distances have been calculated for a set of observations (e.g. individuals in a cohort) classical tools (such as cluster analysis) can be used. The method was tailored to social sciences from a technique originally introduced to study molecular biology (protein or genetic) sequences (see sequence alignment). Optimal matching uses the Needleman-Wunsch algorithm.

Algorithm

belonging to a finite set the sequence space, i.e. the set of all possible sequences of states.

Optimal matching algorithms work by defining simple operator algebras. In the most simple approach, a set composed of only three basic operations to transform sequences is used:

• and

• .

Imagine now that a cost, the idea is to measure the cost; a reasonable choice is to select the cheapest of such sequences. We thus call distance , that is there is no cost. The distance function is symmetric; the term indel cost usually refers to the common cost of insertion and deletion.

Considering a set composed of only the three basic operations described above, this proximity measure satisfies the triangular inequality. Transitivity however, depends on the definition of the set of elementary operations.

Criticism

Although optimal matching techniques are widely used in sociology and demography, such techniques also have their flaws. As was pointed out by several authors (for example L. L. Wu.

Software

• TDA is a powerful program, offering access to some of the latest developments in transition data analysis.

• STATA has implemented a package to run optimal matching analysis.

• TraMineR is an open source R-package for analyzing and visualizing states and events sequences, including optimal matching analysis.

References and notes