4
$\begingroup$

In my thesis I am working on a problem connected with sequence alignment, in particular, I deal with the Dynamic Time Warping (DTW) algorithm (see this for more), which is used to evaluate the distance between two time series. It is very similar to the Needleman–Wunsch algorithm for aligning protein sequences, the difference is: NW finds a maximum score alignment, whereas DTW finds a minimum distance alignment; and DTW does not penalise gaps.

The question I am having is the following one. Given two sequences S and T, what is the maximum DTW distance between them if points along S can be skipped. I tried adjusting the standard DTW dynamic programming algorithm, but this problem may not be as trivial as it seems. For example, finding the minimum DTW distance between S and T if points along S can be skipped is easy, we just need to extend the recurrence relation from the original alignment algorithm; but this trick does not seem to be working with the problem I have.

I would be very grateful for any ideas on how to tackle this problem or any links to relevant literature.

More formally, DTW distance is defined via the following recurrence relation: $$d_{DTW}(\langle\rangle,\langle\rangle)=0,$$ $$d_{DTW}(S,\langle\rangle)=\infty,$$ $$d_{DTW}(\langle\rangle,T)=\infty,$$ $$d_{DTW}(S,T)=\delta(S_n,T_m)+\min\{d_{DTW}(S_{1:n-1},T_{1:m-1}),d_{DTW}(S_{1:n-1},T_{1:m}),d_{DTW}(S_{1:n},T_{1:m-1})\},$$ where $\delta$ is the local distance function (usually $L_1$ or $L_2$ metric) and $|S|=n$ and $|T|=m$. What I am looking for is a subsequence $S'$ of $S$, such that is $$\arg\max_{S'}d_{DTW}(S',T).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.