math - 最长可能字符串的长度不包含重复的 3-mer

Question

我试图找到不包含重复 3-mer 的最长可能连续数字字符串的长度。

这是一个生物信息学问题，我正在为蛋白质序列排序。

基本上，类似的东西0102340109不起作用，因为010重复。

但是类似的东西是0002223589765有效的，因为你找不到任何重复的 3 位数字。

我需要找到最长的序列，我有点卡住了，一无所知。

Answer 1

以下代码是用 ES6 编写的。您可以创建一个sliding接受字符串输入的过程 a 返回子字符串“windows”的 Iterable

Array.from(sliding (3,1) ('012345'))
// [ '012', '123', '234', '345' ]

Array.from(sliding (2,2) ('012345'))
// [ '01', '23', '45' ]

Array.from(sliding (4,2) ('012345'))
// [ '0123', '1234', '2345' ]

然后，使用它，您可以定义一个seqIsRepeated遍历滑动窗口的过程。我们不会预先计算整个窗口列表，而是逐个查看它们，将每个结果添加到一个集合中。如果Set中已经存在该窗口，true将立即返回并停止迭代。如果该过程使其通过所有窗口而没有找到重复项，false则将返回。

const sliding = (m,n) => function* (xs) {
  for (let i = 0; i + m <= xs.length; i += n)
    yield xs.substr(i, m);
};

const seqIsRepeated = n => xs => {
  let set = new Set();
  for (let seq of sliding (n,1) (xs))
    if (set.has(seq))
      return true;
    else
      set.add(seq);
  return false;
};

console.log (seqIsRepeated (3) ('0102340109'));    // true
console.log (seqIsRepeated (3) ('0002223589765')); // false

这不会为您找到最长的序列，但希望它确实给您一个开始。从这里开始，您将查看输入序列的子字符串并使用seqIsRepeated(3)来消除子字符串的可能性