python - 最短超串搜索的更有效算法

Question

我下面的问题是 NP 完全问题，但是，我试图找到至少稍微快一点的字符串搜索函数或模块，与现在相比，它可能有助于减少一些计算时间。如有任何建议，我们将不胜感激。

连接的(最长可能的)超字符串是:

AGGAGTCCGCGTGAGGGAGGTGTAGTGTAGTGG

下面的代码产生了 16 米的最短超串:

CCGTAGGTGGAGT

import itertools as it

def main():
    seqs = ['AGG', 'AGT', 'CCG', 'CGT', 'GAG', 'GGA', 'GGT', 'GTA', 'GTG', 'TAG', 'TGG']
    seq_perms = [''.join(perm) for perm in it.permutations(seqs)]
    for i in range(0, len(''.join(seqs))):
        seq_perms = [''.join(perm)[:i] for perm in it.permutations(seqs)]   
        for perm in seq_perms:   
            if all(perm.find(seq) != -1 for seq in seqs) == True:
                print 'Shortest superstring containing all strings:\n{}'.format(perm)
                return


if __name__ == '__main__':
    main()

任何在我的系统上以更短时间完成的重构都将被标记为已解决。

Answer 1

我应用了 Dijkstra 算法(宽度搜索)，并在不到一秒的时间内找到了解决此任务的方法。我在内存使用方面对其进行了一些优化，但我认为就算法而言，这是一种比其他答案中的方法更好的方法。除非我们用完内存，否则这应该是一个更好的解决方案。

from collections import defaultdict

def dijkSuperstring(originalSeqs):
  paths = defaultdict(set)
  paths[0] =  { '' }
  while paths:
    minLength = min(paths.keys())
    while paths[minLength]:
      candidate = paths[minLength].pop()
      seqAdded = False
      for seq in originalSeqs:
        if seq in candidate:
          continue
        seqAdded = True
        for i in reversed(range(len(seq)+1)):
          if candidate.endswith(seq[:i]):
            newCandidate = candidate + seq[i:]
            paths[len(newCandidate)].add(newCandidate)
      if not seqAdded:  # nothing added, so all present?
        return candidate
    del paths[minLength]

print dijkSuperstring(
  [ 'AGG', 'AGT', 'CCG', 'CGT', 'GAG', 'GGA', 'GGT', 'GTA', 'GTG', 'TAG', 'TGG' ])

我还尝试使用随机序列作为输入:

seqs = [ ''.join(random.choice('GATC')
  for i in range(3))
    for j in range(11) ]
print dijkSuperstring(deqs)

我很快发现求解时间在很大程度上取决于结果的大小 (!) 而不是输入的大小(因此它不可预测)。这并不奇怪，但它使得比较不同的算法有点困难，因为其他算法不一定也具有此属性。特别是，OP 中的序列集似乎构成了一个相对轻量级的问题。其他由 3 个字符组成的 11 个序列的集合更难解决。

所以我做了一些统计测量；我解决了 1000 组 8 个序列。这是我为 3 个和 4 个字符的序列所做的。然后我将持续时间分为 100 组(从 0 到最高持续时间等间隔)并计算每组有多少人。为了平滑图形，我总是使用三个相邻组的总和。

下图分别显示了两个这样的实验，使用我的算法的早期(未优化)版本执行(但曲线的形状与现在相同)；我做了两次，至少知道图中的一条奇怪的沟渠是有原因的还是纯属偶然。

我有兴趣看到其他算法的同类输入的类似图表。这可能很有趣，因为我的算法显然存在内存问题。由于内存耗尽，解决 11 个 3 个字符的序列使我的机器停顿了好几次，因此即使速度较慢，使用另一种算法也是有意义的。

8 个 3 个字符的序列

4 个字符的 8 个序列