4

我正在寻找一种算法，最好是在 Python 中，它可以帮助我找到最接近目标字符串 N 个字符长的现有字符串的子字符串（N 个字符长）。

考虑目标字符串，即 4 个字符长，为：

targetString -> '1111'

假设这是我可以使用的字符串（我将生成它的子字符串以进行“最佳对齐”匹配）：

nonEmptySubStrings -> ['110101']

上述 4 个字符长的子字符串：

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

我想编写/使用一个“魔术函数”来选择最接近 targetString 的字符串：

someMagicFunction -> ['1101']

更多示例：

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

someMagicFunction -> ['1011']

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

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

这个“魔术函数”是一个众所周知的子字符串问题吗？

我真的很想找到分钟。nonEmptySubStrings 中的更改次数，以便它将 targetString 作为子字符串。

4

3 回答 3

3

我相信您需要Edit Distance。Peter Norvig 的拼写校正器是 python 中的一个实现示例。这是Levenshtein Distance 的实现。另请参阅此问题。

编辑：这在生物信息学中相当常见。参见例如FASTA和BLAST。生物信息学有很多这种算法的风格。有关方法的调查，请参阅序列比对。

于 2010-11-17T09:55:00.553 回答
2

作为前段时间关于基因匹配的讨论的一部分，我编写了这个 pyparsing 示例，实现了一个 pyparsing 类CloseMatch。通常 pyparsing 表达式返回一个包含匹配字符串和任何命名结果的结构，但CloseMatch返回一个包含匹配字符串和匹配字符串中不匹配位置列表的 2 元组。以下是如何CloseMatch使用：

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

这是部分匹配的示例输出：

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

请注意，此类不会找到重叠的匹配项。这仍然可以完成，但使用 scanString 的方法略有不同（我将在下一个 pyparsing 版本中包含它）。

于 2010-11-17T13:47:58.247 回答
1

根据 OP 对问题的评论，这是所需要的

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

这将返回任何子字符串到目标字符串的最小编辑距离。它不会指出是哪个字符串或它的索引是什么。不过可以很容易地修改它。

天真的方法，可能是最好的方法，是

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))

这不会返回子字符串出现的索引。当然，您没有在问题中指定您需要它；）

如果您想变得比这更好，这将取决于您如何测量距离，并且基本上可以归结为通过推断您必须更改至少 x 个字符以获得比您已经更好的匹配来避免检查某些子字符串有。那时，您还不如通过向前跳转 x 字符来更改 x 字符。

于 2010-11-17T09:57:14.943 回答