python - 将相似的模式合并为单一的共识模式

Question

在上一篇文章中，我没有正确地澄清问题，因此，我想在这里开始一个新的话题。

我有以下物品：

59,000 个蛋白质模式的排序列表（范围从 3 个字符“FFK”到 152 个字符长）；
一些长蛋白质序列，也就是我的参考。

我将根据我的参考匹配这些模式并找到匹配的位置。（我的朋友帮助编写了一个脚本。）

import sys
import re
from itertools import chain, izip

# Read input
with open(sys.argv[1], 'r') as f:
    sequences = f.read().splitlines()
with open(sys.argv[2], 'r') as g:
    patterns = g.read().splitlines()

# Write output
with open(sys.argv[3], 'w') as outputFile:
    data_iter = iter(sequences)
    order = ['antibody name', 'epitope sequence', 'start', 'end', 'length']
    header = '\t'.join([k for k in order])
    outputFile.write(header + '\n')
    for seq_name, seq in izip(data_iter, data_iter):
        locations = [[{'antibody name': seq_name, 'epitope sequence': pattern, 'start': match.start()+1, 'end': match.end(), 'length': len(pattern)} for match in re.finditer(pattern, seq)] for pattern in patterns]
        for loc in chain.from_iterable(locations):
            output = '\t'.join([str(loc[k]) for k in order])
            outputFile.write(output + '\n')

f.close()
g.close()
outputFile.close()

问题是，在这 59,000 个模式中，经过排序后，我发现一个模式的某些部分与其他模式的一部分匹配，我想将它们合并为一个大的“共识”模式并保持共识（参见下面的示例):

TLYLQMNSLRAED
TLYLQMNSLRAEDT
  YLQMNSLRAED
  YLQMNSLRAEDT
  YLQMNSLRAEDTA
  YLQMNSLRAEDTAV

将产生

TLYLQMNSLRAEDTAV

另一个例子：

    APRLLIYGASS
    APRLLIYGASSR
    APRLLIYGASSRA
    APRLLIYGASSRAT
    APRLLIYGASSRATG
    APRLLIYGASSRATGIP
    APRLLIYGASSRATGIPD
  GQAPRLLIY
KPGQAPRLLIYGASSR
KPGQAPRLLIYGASSRAT
KPGQAPRLLIYGASSRATG
KPGQAPRLLIYGASSRATGIPD
       LLIYGASSRATG
       LLIYGASSRATGIPD
   QAPRLLIYGASSR

将产生

KPGQAPRLLIYGASSRATGIPD

PS：我在这里对齐它们，以便更容易可视化。最初的 59,000 个模式没有排序，因此很难在实际文件中看到共识。

在我的特定问题中，我没有选择最长的模式，相反，我需要考虑每个模式以找到共识。我希望我已经对我的具体问题进行了足够清楚的解释。

谢谢！

score 1 · Accepted Answer

这是我使用随机输入顺序的解决方案，以提高测试的信心。

import re
import random

data_values = """TLYLQMNSLRAED
TLYLQMNSLRAEDT
  YLQMNSLRAED
  YLQMNSLRAEDT
  YLQMNSLRAEDTA
  YLQMNSLRAEDTAV
    APRLLIYGASS
    APRLLIYGASSR
    APRLLIYGASSRA
    APRLLIYGASSRAT
    APRLLIYGASSRATG
    APRLLIYGASSRATGIP
    APRLLIYGASSRATGIPD
  GQAPRLLIY
KPGQAPRLLIYGASSR
KPGQAPRLLIYGASSRAT
KPGQAPRLLIYGASSRATG
KPGQAPRLLIYGASSRATGIPD
       LLIYGASSRATG
       LLIYGASSRATGIPD
   QAPRLLIYGASSR"""

test_li1 = data_values.split()
#print(test_li1)

test_li2 = ["abcdefghi", "defghijklmn", "hijklmnopq", "mnopqrst", "pqrstuvwxyz"]

def aggregate_str(data_li):
    copy_data_li = data_li[:]
    while len(copy_data_li) > 0:
        remove_li = []
        len_remove_li = len(remove_li)
        longest_str = max(copy_data_li, key=len)
        copy_data_li.remove(longest_str)
        remove_li.append(longest_str)
        while len_remove_li != len(remove_li):
            len_remove_li = len(remove_li)
            for value in copy_data_li:
                value_pattern = "".join([x+"?" for x in value])
                longest_match = max(re.findall(value_pattern, longest_str), key=len)
                if longest_match in value:
                    longest_str_index = longest_str.index(longest_match)
                    value_index = value.index(longest_match)
                    if value_index > longest_str_index and longest_str_index > 0:
                        longest_str = value[:value_index] + longest_str
                        copy_data_li.remove(value)
                        remove_li.append(value)
                    elif value_index < longest_str_index and longest_str_index + len(longest_match) == len(longest_str):
                        longest_str += value[len(longest_str)-longest_str_index:]
                        copy_data_li.remove(value)
                        remove_li.append(value)
                    elif value in longest_str:
                        copy_data_li.remove(value)
                        remove_li.append(value)
        print(longest_str)
        print(remove_li)

random.shuffle(test_li1)
random.shuffle(test_li2)
aggregate_str(test_li1)
#aggregate_str(test_li2)

print() 的输出。

KPGQAPRLLIYGASSRATGIPD
['KPGQAPRLLIYGASSRATGIPD', 'APRLLIYGASS', 'KPGQAPRLLIYGASSR', 'APRLLIYGASSRAT', 'APRLLIYGASSR', 'APRLLIYGASSRA', 'GQAPRLLIY', 'APRLLIYGASSRATGIPD', 'APRLLIYGASSRATG', 'QAPRLLIYGASSR', 'LLIYGASSRATG', 'KPGQAPRLLIYGASSRATG', 'KPGQAPRLLIYGASSRAT', 'LLIYGASSRATGIPD', 'APRLLIYGASSRATGIP']
TLYLQMNSLRAEDTAV
['YLQMNSLRAEDTAV', 'TLYLQMNSLRAED', 'TLYLQMNSLRAEDT', 'YLQMNSLRAED', 'YLQMNSLRAEDTA', 'YLQMNSLRAEDT']

Edit1 - 代码的简要说明。

1.) 在列表中查找最长的字符串

2.) 遍历所有剩余的字符串并找到最长的匹配。

3.) 确保匹配不是误报。根据我编写此代码的方式，它应该避免在终端配对单个重叠。

4.) 如有必要，将匹配附加到最长的字符串。

5.）当没有其他东西可以添加到最长的字符串时，重复过程（1-4）以获得下一个最长的字符串。

Edit2 - 更正了处理 ["abcdefghijklmn", "ghijklmZopqrstuv"] 等数据时的不良行为

score 0 · Accepted Answer

def main():
#patterns = ["TLYLQMNSLRAED","TLYLQMNSLRAEDT","YLQMNSLRAED","YLQMNSLRAEDT","YLQMNSLRAEDTA","YLQMNSLRAEDTAV"]
patterns = ["APRLLIYGASS","APRLLIYGASSR","APRLLIYGASSRA","APRLLIYGASSRAT","APRLLIYGASSRATG","APRLLIYGASSRATGIP","APRLLIYGASSRATGIPD","GQAPRLLIY","KPGQAPRLLIYGASSR","KPGQAPRLLIYGASSRAT","KPGQAPRLLIYGASSRATG","KPGQAPRLLIYGASSRATGIPD","LLIYGASSRATG","LLIYGASSRATGIPD","QAPRLLIYGASSR"]

test = find_core(patterns)
test = find_pre_and_post(test, patterns)
#final = "YLQMNSLRAED"
final = "KPGQAPRLLIYGASSRATGIPD"

if test == final:
    print("worked:" + test)
else:
    print("fail:"+ test)

def find_pre_and_post(core, patterns):
    pre = ""
    post = ""
    for pattern in patterns:
        start_index = pattern.find(core)
        if len(pattern[0:start_index]) > len(pre):
            pre = pattern[0:start_index]
        if len(pattern[start_index+len(core):len(pattern)]) > len(post):
            post = pattern[start_index+len(core):len(pattern)]

    return pre+core+post

def find_core(patterns):
    test = ""
    for i in range(len(patterns)):
        for j in range(2,len(patterns[i])):
            patterncount = 0
            for pattern in patterns:
                if patterns[i][0:j] in pattern:
                    patterncount += 1
            if patterncount == len(patterns):
                test = patterns[i][0:j]
    return test

main()

所以我首先要做的是find_core从长度为 2 的字符串开始找到函数中的主要核心，因为对于第一个字符串，一个字符的信息不足。然后我比较那个子字符串，看看它是否在所有字符串中作为“核心”的定义
然后我在每个字符串中找到子字符串的索引，然后找到添加到核心的前后子字符串。我会跟踪这些长度并在一个长度大于另一个时更新它们。我没有时间探索边缘情况，所以这是我的第一枪

python - 将相似的模式合并为单一的共识模式

2 回答 2

Related

Reference