Locate "N Gram" substrings that are smallest distance away from a target string N character long

Question

I am looking for an algorithm, preferably in Python that would help me locate substrings, N characters long, of exisiting strings that are closest to a target string N character long.

Consider the target string, that is, say, 4 characters long, to be:

targetString -> '1111'

Assume this is the string I have available with me ( I will generate substrings of this for "best alignment" matching ):

nonEmptySubStrings -> ['110101']

Substrings of the above that are 4 characters long:

nGramsSubStrings -> ['0101', '1010', '1101']

I want to write/use a "Magic Function" that would select the string closest to targetString :

someMagicFunction -> ['1101']

Some more examples:

nonEmptySubStrings -> ['101011']
nGramsSubStrings -> ['0101', '1010', '1011']

someMagicFunction -> ['1011']

nonEmptySubStrings -> ['10101']
nGramsSubStrings -> ['0101', '1010']

someMagicFunction -> ['0101', '1010']

Is this "Magic Function" a well known substring problem?

I really want to find the min. number of changes in nonEmptySubStrings so that it would have targetString as a substring.

I am interested in knowing an answer to the last ( bolded ) line of my question above. My requirement seems to be something that should be fairly frequent in bioinformatics? Oh it might be as trivial as being based on the Hamming distance ( in which case I would modify my question to remove the ngram generation step ). I basically want to find the min. number of changes in nonEmptySubStrings so that it would have targetString as a substring. — PoorLuzer, Nov 17 '10 at 09:55

score 3 · Answer 1 · edited May 23 '17 at 11:47

3

I believe you need Edit Distance. Peter Norvig's spelling corrector is an implementation example in python. Here's an implementation of Levenshtein Distance. See also this question.

EDIT: This is fairly frequent in bioinformatics. See e.g. FASTA and BLAST. Bioinformatics has many flavors of this algorithm. See Sequence Alignment for a survey of methods.

edited May 23 '17 at 11:47

Community

1
1

answered Nov 17 '10 at 09:55

Yuval F

20,565
5
44
69

score 2 · Answer 2 · answered Nov 17 '10 at 13:47

As part of a discussion a while ago on gene matching, I wrote this pyparsing example, implementing a pyparsing class CloseMatch. Normally pyparsing expressions return a structure containing matched strings and any named results, but CloseMatch returns a 2-tuple containing the matching string and a list of mismatch locations within the matched string. Here is how CloseMatch would be used:

searchseq = CloseMatch("TTAAATCTAGAAGAT", 3)
for g in genedata: 
    print "%s (%d)" % (g.id, g.genelen) 
    print "-"*24 
    for t,startLoc,endLoc in searchseq.scanString(g.gene): 
        matched, mismatches = t[0] 
        print "MATCH:", searchseq.sequence 
        print "FOUND:", matched 
        if mismatches: 
            print "      ", ''.join(' ' if i not in mismatches else '*'  
                            for i,c in enumerate(searchseq.sequence)) 
        else: 
            print "<exact match>" 
        print "at location", startLoc

Here is a sample output of a partial match:

organism=Toxoplasma_gondii_RH (258)
------------------------
MATCH: TTAAATCTAGAAGAT
FOUND: TTAAATTTAGGAGCT
             *   *  * 
at location 195

Note that this class does not find overlapping matches. That can still be accomplished, but with a slightly different approach with scanString (which I will include in the next pyparsing release).

aaronasterling · Accepted Answer · 2010-11-17T10:35:22.990

Base on OP's comment to question, this is what is desired

import functools

def edit_distance(str1, str2): 
    #implement it here

f = functools.operator(edit_distance, target_string)
return min(f(s) for s in slices(string_))   # use slices from below

This will return the minimum edit distance of any substring to the target string. It will not indicate which string that is or what its index is. It could be easily modified to do so though.

The naive way, which can be the best way, is

import functools

def diff(str1, str2):
    # However you test the distance gets defined here. e.g. Hamming distance, 
    # Levenshtein distance, etc.


def slices(string_, L):
    for i in xrange(len(string_) - L + 1)):
        yield string_[i:i+L]

best_match = min(slices(string_), key=functools.partial(diff, target_string))

This wont return the index at which the substring occurs though. Of course you didn't specify that you need it in your question ;)

If you want to get better than this, it will depend on how you're measuring the distance and will basically boil down to avoiding checking some substrings by infering that you would have to change at least x chars to get a better match than you already have. At that point, you might as well just change x chars by jumping ahead x chars.

your 'slices' needs to have 'for i in xrange(len(string_) - L + 1):' instead of 'for i in xrange(len(string_) - L))' Would hamming distance be a good metric for 'def diff(str1, str2)'? — PoorLuzer, Nov 17 '10 at 10:10
@PoorLuzer, It seems like Hamming distance would be ideal given that it measures the number of different characters. Is this all you want? Do you want the actual substring or it's index? If not, you could probably do it all without a function. Let me know and I'll update. — aaronasterling, Nov 17 '10 at 10:36
I don't want to know anything about the substrings except to find the min. number of changes in string_ so that it would have target_string as a substring. The function to compute the 'min. number of changes' needs to be as fast as possible as it will be processing thousands of strings. The strings are numeric and binary ( i.e. it has only two different digits ) in case this helps. — PoorLuzer, Nov 17 '10 at 18:45

Locate "N Gram" substrings that are smallest distance away from a target string N character long

3 Answers3