对齐匹配序列

Question

我正在尝试根据前5个字符和最后5个字符对齐匹配序列。例如：

AAATGCEGAIRPVOGJKKK
KKKTGKAFKEJWKLJFFFF
FFFKEJFWKFJWEKFJIGK

将对齐和连接以创建：

^{pr2}$

请注意，映射区域不应该重复。实际上我有超过3行，而且它们没有被排序，所以我尝试创建一个循环来将所有这些行对齐。我不确定处理这个问题的最佳方法。在

Answer 1

我想你可以通过编一本前缀词典来解决这个问题。一旦你有了它，从任意序列开始，找到它的后缀在前缀列表中。然后转到有那个前缀的序列，构建一个链。在

下面是一些代码：

def make_circular_overlapping_sequence(sequences, min_overlap=1, max_overlap=5):
    # start by mapping prefixes to full sequences
    prefixes = {}
    for seq in sequences:
        for length in range(min_overlap, max_overlap+1):
            prefixes[seq[:length]] = seq

    # pick arbitrary a start sequence
    start = current = sequences[0]

    # build a chain of sequences with overlapping suffixes and prefixes
    chain = [start]
    while True:
        # try longest suffixes first
        for length in range(max_overlap, min_overlap-1, -1):
            suffix = current[-1-length:]
            if suffix in prefixes:
                current = prefixes[suffix]
                if current == start: # looped around, so we're done
                    return "".join(chain)
                chain.append(current[length+1:]) # don't duplicate the prefix
                break
        else: # for loop ended without breaking
            raise ValueError("No match found for sequence {!r}"
                             .format(current))

测试输出：

^{pr2}$

注意事项：

1. 此代码适用于明确的循环序列，如果存在不明确的匹配（例如"...ABC"，后面可能跟"ABC..."或{}），则可能无法按预期工作。目前它总是选择最长的重叠。在
2. 如果链结束时没有循环，代码将引发异常，但是如果有一个不包含start元素的短循环（例如["A...B", "B..C", "C..B"]），则它可能永远运行。在
3. 该算法不能保证所有的输入序列都包含在输出中。它只会找到一个循环并停止。在
4. 第一个值和最后一个值的匹配部分不会被修剪掉。如果您不想这样做，我建议从返回值中切去最后一个后缀：return "".join(chain)[:-length]