algorithm - 求(L，t)-团

我想在Clojure找到一团。基本上，我需要找到所有的K长度的子串，它们出现在一个基因组中L大小的窗口中，出现T次。我已经实现了我认为的解决方案，但是我相信其中可能有漏洞，因为我正在使用的系统（beta.stepic.org）告诉我你们能找出我搞砸的地方吗？我的解决方案如下，找到所有排名靠前的k-mers（k-length子串）并找到它们的起始索引。然后，我将它们分成t组，这意味着这是它们发生的次数，基本上是用k偏移量来区分被分区组中的最后一个和第一个项目（因为所有k-mer都应该适合L窗口，这将通过扩展它来解释最后的k-mer）索引按升序排列。虫子在哪里？
束查找问题：查找在字符串中形成束的模式。

 Input: A string Genome, and integers k, L, and t.
 Output: All distinct k-mers forming (L, t)-clumps in Genome.

样本输入：
基因组：cgactcgagagagagagagagagatgagagagagatgagagagagagatgagagagactgagagagagagagagactaa

 k: 5
 L: 50
 t: 4

样本输出：
CGACA砷化镓

(defn get-indices [source target]
  "Returns the indices for the substring target
   found in source in ascending order. This includes overlaps."
  (let
    [search   (java.util.regex.Pattern/compile (str "(?=(" target "))"))
     matcher  (re-matcher search source)
     not-nil? (complement nil?)]

    (defn inner [matcher]
      (if (not-nil? (re-find matcher))
        (cons (.start matcher) (inner matcher))))
          (inner matcher)))

(defn get-frequent-kmer [source k]
  "Gets the most frequenct k-mers of size k from source"
  (let [max-val (val (apply max-key val (frequencies (partition k 1 source))))]
    (map first (filter #(= (val %) max-val)
      (frequencies (map (partial apply str) (partition k 1 source)))))))


(defn find-clumps [genome k L t]
  (for [k-mer (get-frequent-kmer genome k)]
    (let [indices (get-indices genome k-mer)]
      (if (some true? (map #(<= (+ k (- (last %) (first %))) L)
        (partition t 1 indices))) k-mer))))

最佳答案

除了代码样式有一些可以改进的地方外，我看到的主要问题是您在max-key val上过滤k-mers，而在初始过滤上根本不考虑t。
当你发现最常见的l-mers的大小k时，你只需要保留较长的l-mers：

  (apply max-key val (frequencies (partition k 1 source)))

因为你按最大值过滤

  (filter #(= (val %) max-val)

你只是在分析：

  (for [k-mer (get-frequent-kmer genome k)]

问题是，如果t是4，但你有超过4次重复的5-mers，你就把重复4次的留在方程之外。

关于algorithm - 求(L，t)-团，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20087842/