I have sequence which is a repetition of a few strings. I have identified the start and end markers of these strings in the sequence and now, I want to cluster similar strings together. The problem is there is a lot of noise. E.g say the strings in the sequence are ABC, BD, EF. and we have a sequence ABGC'BTD'BD'EF'EOF'ABQC'. Here I want to cluster ABGC and ABQC together. How can I do this when there is almost 30-50% noise. If there is some way to remove the noise first and then cluster them, that would work too. Also, the markers are being learnt in an unsupervised manner so you don't know the processes in it beforehand. You can assume the noise to be random.


2 Answers 2


First, you must define a distance that is good for your purpose : how close two substrings are :

  • How close "ABC" is to "ABGC" ?
  • How close "ABC" is to "BD" ?

Naturally it would be something like the Levenshtein distance or another edit distance. If the substrings vary a lot in length you may divide the raw edit distance by the length.

Then find a good clustering algorithm. K-means can't do it since it requires a vector space. There is a discussion about it here : Clustering a long list of strings (words) into similarity groups


There has been a lot of work on this before.

Get books on bioinformatics and sequential pattern mining.

E.g. the SPADE algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.