如何在没有100%相似性的字符串列表中搜索模式？

Question

所以我有一个字符串列表：

input_list=["ACTGATCTTATCGAGTCAGCTAGTCGATCGATCGACGCGCGATCGTGATG","TGCATCGATCGATGCTAGTCGATATACGCGATATGTACG","CATCGGATCGATCGATCAGCTCATAGTCAGTC","CATCGATCATATATCGAGCGACAGTCAGTCGATCAGTCATCAGGTAGC","CATCATATCGAGCAGTCATCGTAGTCATGATCGATCGAT","ACATGAATCGATCGATAATCGATCGCGATTCGATG"]

以及包含要在字符串中查找的模式的元组列表

list_patterns=[("AGTG","TCGC"),("TATC","ATGT"),("GCAT","TCAG")]

我有一个函数，对于每个字符串，从“list_patterns”中查找（任意）一对模式。“list_patterns”中每个元组的第一个元素从字符串的末尾搜索，每个元组的第二个元素从每个字符串的末尾搜索。 随后，函数修剪字符串，将修剪后的字符串追加到空列表中（如果没有找到任何模式对，则只追加原始的未修剪字符串）

trimmed_list = []
for el in input_list:
    for pat in list_patterns:
        beg = el.find(pat[0])
        end = el.rfind(pat[1])
        if(beg != -1 and end != -1):
            output_list.append(el[beg+len(pat[0]):end])
            break
    else:
        output_list.append(el)

问题是，我想修剪并找到模式，但不一定只匹配那些具有100%相似性的模式。我还希望找到一些相似的模式（通过用户定义的阈值），并相应地修剪字符串

我发现这个函数可以检索两个字符串之间的相似性比率，但我无法将其实现到我的原始函数中：

from difflib import SequenceMatcher
def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

例如，假设我有一个字符串：

"ATGCATCGTACGTACGTACG"

以及一组可能与原始模式略有不同的模式：

("AYTG","TARYCG")

即使字符串不完全包含这些模式（但包含类似的模式），我仍然希望对其进行修剪（ATG | catcgtacg | TACG），并有一个输出：

"CATCGTACGTACG"

有没有一种简单的方法可以将“SequenceMatcher”函数添加到我的用户定义函数中？ 提前非常感谢您的回答

Answer 1

您可以创建自定义的find函数并调用它，而不是string.find或string.rfind方法。此函数只查看与模式长度相同的字符串部分。如果不同的长度可以匹配，它必须延长，但很难预测会延长多少

def find_similar(needle, haystack, backwards = False, min_diff_ratio = 0.75):
    n_len = len(needle)
    # create a range depending on direction
    if backwards:
        r = range(len(haystack)-n_len, -1, -1)
    else:
        r = range(len(haystack) - n_len)
    for i in r:
        # create a substring with same length as search string
        # at index
        substr = haystack[i:i + n_len]
        # Here we check for similarity using your function
        if similar(needle, substr) >= min_diff_ratio:
            return i
    return -1

将您的循环更新到此位置

trimmed_list = []
for el in input_list:
    for pat in list_patterns:
        beg = find_similar(pat[0], el)
        end = find_similar(pat[1], el, True)
        if(beg != -1 and end != -1):
            output_list.append(el[beg+len(pat[0]):end])
            break
    else:
        output_list.append(el)