Classification of sequences of symbols Let's say i have sequences of symbols which can have five values : A, B, C, X, Y. The average length of sequences is around 7.
It is important that the symbols A, B, C have a bigger importance than X and Y which may be consider as 'whatever different from A, B or C'
I need to classify those data among two classes : positives and negatives. The positive class is composed of sequences generally well aligned like 
X X A B Y C
A B C X X
A Y A X B C X X

Note that positive examples have generally symbols A,B and C in that order.
Negatives examples look like more 'messy' like
B X A X X X X C
C A Y Y X X B

My first thought was that entropy was the key of that problem. I checked various papers but nothing was really satisfying. So my question is:
Which features would you use for a classification purpose?
 A: I would not use any feature detectors but recurrent neural networks. They are very good for symbolic sequences: for example, they are able to recognize context sensitive languages.
Check out Biologically Phoneme Classification with LSTM neural nets (Graves, Schmidhuber) for an explanation of how to use RNNs for classification. See Generating Text with Recurrent Neural Networks (Martens, Sutskever, Hinton) for an impressive symbolic application of RNNs.
A: It sounds like this question is asking for a way to quantify the sense of "generally well aligned" strings.  Of course there are many ways to do this, but the examples and the description suggest that any solution meet two criteria:
1.  The X's and Y's should play no role in the result.

2.  The strings in which the A, B, and C's appear in order are the most "well aligned."

This suggests basing the classification on an edit distance among the {A,B,C} substrings or on a partial ordering of multiset permutations.  To provide more focused advice, we would need more information about the purpose of the intended importance ordering and about how these strings are generated.
A: Kernel methods (such as the support vector machine) are likely to be quite good for this kind of problem as you can use kernel functions that operate directly on strings of symbols of variable length.  Examples include the spectrum kernel (which projects the strings into an implicit feature space where each dimension records the number of ocurrences of all possible substrings of a given length - or less) and the mismatch kernel, which is similar, but the counting of sub-strings allows a certain amount of mis-matches.  There is also the sequence  alignment kernel,  which might be of interest.
A: Can we do it programitically ?? Meaning that writing a peace of code that does that you saying ..ex giving "A x X B Y c" more importance than "B X X X A C".
agree that this code should be bit complex though.? 
