创建高效

随机序列与最小编辑距离的时间的高NR我需要创建一个程序/脚本用于创建高数量的随机序列中的（20信基于4个不同的字母长的序列）与之间的最小编辑距离所有序列。 “高”在这里将是至少100k的序列，但如果可能的话高达100万。创建高效

我开始与刚产生随机20个字母序列的简单方法，并且对于每个序列，计算所述序列和已创建并存储所有其它序列之间的编辑距离。如果新序列超过了我的阈值，则存储它，否则丢弃。如你所知，这对于较高数量的序列非常不利。高达10K是相当好的，但试图获得100K，这开始变得麻烦。

我真的只需要一次创建序列和存储输出，所以今天我真的没有那么挑剔的速度，但使百万在这个速度仅仅是没有可能的。

一直在努力思考的替代品，以加快这一进程，如建立序列是最小的ED的“块”，然后合并，但没有拿出任何解决方案。

想知道，难道任何人有任何聪明的想法/方法可以实施创造如此高的数量以最小的ED更多的时间有效的序列？

干杯， JB

来源

2017-09-15 Joseph Bergenstråhle

你有什么（简短）的背景知道你打算如何使用这些序列/为什么他们需要随机，但在编辑距离接近？从不同角度处理问题总是有可能比优化当前的解决方案更有效。 – Bilkokuya

当然，让我澄清，编辑距离应该高于给定的阈值（在这种情况下> 4）。背景是在模拟中使用的DNA测序“条形码”，序列需要不相似，但也需要ED>〜4，以便在一个或两个字母中进行替换（在模拟期间引入错误介绍）不会使其等于我的序列集合中的另一个序列。 –

看来，维基百科，即编辑距离是三个操作插入，缺失，置换的一个;在起始字符串上执行。为什么不系统地生成所有字符串，从起始字符串开始N个编辑，然后在达到极限时停止？

将不会有任何需要检查的实际编辑距离，因为他们将是一代正确的。随机性可以产生一个数字然后洗牌。

来源

2017-09-15 14:18:23 Paddy3118

谢谢，但我认为我对这个问题的最初表述还不清楚，我应该使用“最小”而不是“最小”，对此抱歉。我编辑了第一句话。我认为你解释了这个问题，因此我希望输出是一组具有编辑距离的序列与起始字符串的关系。事实并非如此，我希望输出集中的每个序列与所有其他序列的编辑距离大于4，这样如果我从集合中随机选取一个序列，则我不会发现其他序列比4 ED更接近集合 –

回答

相关问题