寻找多个序列之间的共享模式

Question

我需要写一个脚本，循环遍历一组序列，找出它们之间的共同特征（可能会有多个不同的特征），并打印出所有序列共享的这个特征。

在下面的例子中：

chains = ['GATTACA', 'TAGACCA', 'ATACA']

AT就是一个共享的特征。我会很感激任何能解决这个问题的方法，包括使用BioPython的函数。

最近我写了一个脚本，它会循环处理同一组序列，把较短的序列作为参考，然后尝试在其他序列的每个位置中找到这个参考序列。但我真的不知道如何在不定义参考的情况下找到共享的特征。

# reference
xz=" ".join(chains)
ref= min(xz.split(), key=len)


# LOOKING FOR THE MOTIFS
for chain in chains:
    for i in range(len(chain)):
        if chain==ref:
            pass
        elif ref not in chain:
            print "%s has not been found in the  %s"%(ref, chain)
            break
        elif chain[i:].startswith(ref):
            print "%s has been detected in %s in the %d position" %(ref, chain, i+1)

Answer 1

最简单的方法是先明白，最长的公共子串不可能比我们正在查看的最短字符串还要长。很明显，如果我们从可能的最长子串开始，先检查它，然后再检查更短的子串，直到找到一个公共子串，我们就可以停止了。

所以，我们首先按照长度对DNA字符串进行排序。我们把最短的那个字符串的长度称为 l。接下来，我们的步骤是测试这个字符串的子串，首先检查长度为 l 的子串，然后是长度为 l-1 的两个子串，依此类推，直到找到匹配的子串并返回它。

from Bio import SeqIO

def get_all_substrings(iterable):
    s = tuple(iterable)
    seen = set()
    for size in range(len(s)+1, 1, -1):
        for index in range(len(s)+1-size):
            substring = iterable[index:index+size]
            if substring not in seen:
                seen.add(substring)
                yield substring

def main(input_file, return_all=False):
    substrings = []
    records = list(SeqIO.parse(open(input_file),'fasta'))
    records = sorted(records, key=lambda record: len(str(record.seq)))
    first, rest = records[0], records[1:]
    rest_sequences = [str(record.seq) for record in rest]
    for substring in get_all_substrings(str(first.seq)):
        if all(substring in seq for seq in rest_sequences):
            if return_all:
                substrings.append(substring)
            else:
                return substring
    return substrings

Answer 2

这只是个简单的想法。你需要对它进行改进，因为它几乎会搜索所有的空间。我希望这能对你有所帮助。

def cut_into_parts(chain, n):
    return [chain[x:x+n] for x in range(0, len(chain)-n)]

def cut_chains(chains, n):
    rlist = []
    for k,v in enumerate(chains):
        rlist.extend(cut_into_parts(chains, n))
    return rlist

def is_str_common(str, chains):
    for k,v in enumerate(chains):
        if !chains[k].contains(str):
            return false
    return true

def find_best_common(chains):
    clist = []
    for i in inverse(range(0, len(chains)))://inverse - I dont remmeber exactly the name of func
        clist.extend(cut_chains(chains, i))
    for k, v in enumerate(clist):
        return is_str_common(clist[k], chains)