Sequence Alignment by Regression Coding

In aligning two sequences, dynamic time warping (DTW) is the well-known dynamic programming algorithm. However, DTW can be sensitive to noise samples that may affect alignment of other relevant samples. In this article, we propose a novel approach to sequence alignment by treating it as a regression coding optimization problem, a task to predict one sequence from another. With some mild relaxation DTW can be seen as a special case of our approach while we provide more flexible and informative interpretation. Experimental results on both synthetic and real-world datasets show that our method can yield more accurate alignment than existing approaches.