title: Find (L,t)-clump
body: <p>I'm trying to find clumps in Clojure. Basically, I need to find all k-length substrings that occur in a window of size L in a genome that occurs t times. I've implemented what I think the solution is, however I believe there might be bugs in it since the system (beta.stepic.org) I'm using to confirm tells me so. Can you guys spot where I'm messing up? My solution goes as follows, find all top ranking k-mers (k-length substrings) and find their starting indices. Afterwards, I partition in groups of t, which means this is the amount of times they occur and basically do a difference of the last and first item in a partitioned group with an offset of k (since all k-mers should fit in the L-window and this would account for the last k-mer by extending it). The indices are in ascending order. Where's the bug?</p>
  
  <h1>Clump Finding Problem: Find patterns forming clumps in a string.</h1>
  
  <pre><code> Input: A string Genome, and integers k, L, and t.
   Output: All distinct k-mers forming (L, t)-clumps in Genome.
  </code></pre>
  
  <p><strong>Sample Input</strong>:</p>
  
  <blockquote>
    <p>genome: CGGACTCGACAGATGTGAAGAACGACAATGTGAAGACTCGACACGACAGAGTGAAGAGAAGAGGAAACATTGTAA</p>
  </blockquote>
  
  <pre><code> k: 5 
   L: 50 
   t: 4
  </code></pre>
  
  <p><strong>Sample Output</strong>:</p>
  
  <blockquote>
    <p>CGACA GAAGA </p>
  </blockquote>
  
  <pre><code>(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 #(&lt;= (+ k (- (last %) (first %))) L)
          (partition t 1 indices))) k-mer))))
  </code></pre>