pattern recognition for sequence data There are a lot of data sequences, I am trying to find pairs of sequences that are similar with other.
Trivially, we can define some distance measure, and compare each pair of sequence in terms of this measure. Or even we can solve this problem in a clustering framework. I have two questions, what are the general features to capture the sequence type of data? If I want to solve the problem in the context of either classification or clustering, I have to find the way to characterize the sequence.
A side problem is that, two sequences may be different, but the subsequence of one may be similar to a sub sequence of another one. How to solve this problem in a systematic way? Are there some algorithms/models to handle this kind of problem?  Using sliding window approach can make computation exponentially large.
 A: The following article provide a critical comparison of many distance measures available for sequences of categorical data. 
Studer, M. and Ritschard, G. (2016), What matters in differences between life trajectories: a comparative review of sequence dissimilarity measures. Journal of the Royal Statistical Society: Series A (Statistics in Society), 179: 481–511. doi: 10.1111/rssa.12125
It is available here in open access: http://onlinelibrary.wiley.com/doi/10.1111/rssa.12125/abstract
A: One trick I learned from the speech recognition literature is dynamic time warp.
https://en.wikipedia.org/wiki/Dynamic_time_warping
There is an implementation in R,
https://cran.r-project.org/web/packages/dtw/dtw.pdf
A: There is a huge literature on time series classification and clustering in the data mining community. Many algorithms have been proposed, many similarity metrics  invented. But, as pointed out by [1], a large number of these algo are not  effective in real world applications. The ref section should get you started on this topic.
[1] Keogh, E., & Kasetty, S. (2003). On the need for time series data mining benchmarks: a survey and empirical demonstration. Data Mining and knowledge discovery, 7(4), 349-371.
