# Discovering string “motifs” in python

I have millions of strings from different sources that tend to exhibit some common patterns. Is there a way to extract these common motifs?

For example, in a list (of millions) that includes strings

['rs12346','rs1212122',...,'sxs-rs333',...,'kgp222']


..is there a way to extract the following patterns?

• 'rs' plus one or more digits
• 'sxs-rs' plus one or more digits
• 'kgp' plus one or more digits

Some other parameters:

• cleaning up beforehand isn't an option
• some manual tweaking would be possible (e.g. manually changing a pattern because of outside knowledge)
• exceptions (i.e. classifying less than 100% of the strings) can be tolerated
• an ideal solution would be using a built-in python library.

Assuming that letters are indicative of "motifs" and numbers are considered as digits and not exact numbers, this is what I would do:

First - transform numbers into a digit placeholder (#)

import re
s = re.sub("\d",s,"#")


Then I would transform a string into a bag-of-bigrams vector in the char level

from sklearn.feature_extraction.text import CountVectorizer
vecs = CountVectorizer(s, analyzer="char_wb", ngram_range=(1,3))


After these 2 steps, we got a sparse vector from any string:

'ab123' --> {" a":1,"ab":1,"b#","##":2,"# ":1}


Next we want to convert those vectors to a pairwise distance matrix and cluster by that distance.

from sklearn.metrics.pairwise import pairwise_distances
from scipy.cluster import  hierarchy
X = X.todense()
C = hierarchy.fcluster(Z,threshold, criterion="distance")
return C


C = link_cluster(vecs)