The DTW alignment algorithm was developed originally for speech recognition⁽¹⁾ and it aims at aligning two sequences of feature vectors by warping the time axis iteratively until an optimal match (according to a suitable metrics) between the two sequences is found.

Let us consider two sequences of feature vectors A and B. The two sequences can be arranged on the sides of a grid, with one on the top and the other on the left hand side, see the figure below. Both sequences start on the bottom left of the grid. Inside each cell a distance measure can be placed, comparing the corresponding elements of the two sequences. To find the best match or alignment between these two sequences one needs to find a path through the grid, which minimizes the total distance between A and B. Thus the procedure for finding the best alignment between A and B involves finding all possible routes through the grid and for each one compute the overall distance, which is defined as the sum of the distances between the individual elements on the warping path. Consequently, the final DTW distance between A and B is the minimum overall distance over all possible warping paths.

DTW warping path

It is apparent that for any pair of considerably long sequences the number of possible paths through the grid will be very large. However, the power of the DTW algorithm resides in the fact that instead of finding all possible routes through the grid, the DTW algorithm makes use of dynamic programming and works by keeping track of the cost of the best path at each point in the grid. A detail explanation of DTW algorithm can be found in the article of Hermans and Tsiporkova⁽²⁾ or downloaded from GenTχWarper tool website.

(1) Sakoe,H. and Chiba,S. (1978) Dynamic programming algorithm optimization for spoken word recognition, IEEE Trans. on Acoust., Speech, and Signal Process, ASSP-26, 43-49.

(2) Hermans,F. and Tsiporkova,E. (2007) Merging microarray cell synchronization experiments through curve alignment, Bioinformatics, 23, e64-e70.