Repository: chrovis/cljam
Pull request #211 (2020-09-24 05:42:56)

Add support for nclist.
This pr adds support for Nested Containment List (NCList).

- Add a second argument to "make-sorted-map-intervals" to select the data structure.
- In the original, it is represented by two lists, but in order to represent it in Clojure, it is represented by one nested list.


Patch:
diff --git a/src/cljam/util/intervals.clj b/src/cljam/util/intervals.clj
index 740ac07..5e60563 100644
--- a/src/cljam/util/intervals.clj
+++ b/src/cljam/util/intervals.clj
@@ -17,12 +17,48 @@
        (into (sorted-map))
        (->SortedMapIntervals)))
 
+(defn- find-nclist-overlap-intervals [nclist start end]
+  (->> (subseq nclist >= start)
+       (map second)
+       (take-while #(<= (:start (first %)) end))
+       (mapcat #(cons (first %)
+                      (find-nclist-overlap-intervals (second %)
+                                                     start end)))))
+
+(deftype NclistIntervals [nclist]
+  IIntervals
+  (find-overlap-intervals* [this start end]
+    (find-nclist-overlap-intervals nclist start end)))
+
+(declare make-nclist*)
+
+(defn- make-nested-intervals [intervals]
+  (when-first [{:keys [start end] :as head} intervals]
+    (let [[nested-intervals rests]
+          (split-with #(<= start (:start %) (:end %) end)
+                      (next intervals))]
+      (cons [end [head (make-nclist* nested-intervals)]]
+            (lazy-seq (make-nested-intervals rests))))))
+
+(defn- make-nclist* [intervals]
+  (let [sorted-intervals (sort-by (juxt :start (comp - :end)) intervals)]
+    (into (sorted-map) (make-nested-intervals sorted-intervals))))
+
+(defn- make-nclist [intervals]
+  (->NclistIntervals (make-nclist* intervals)))
+
 (defn index-intervals
   "Make indexes for intervals to find overlaps."
-  [intervals]
-  (->> intervals
-       (group-by :chr)
-       (into {} (map (fn [[k vs]] [k (make-sorted-map-intervals vs)])))))
+  ([intervals]
+   (index-intervals intervals {}))
+  ([intervals {:keys [structure] :or {structure :sorted-map}}]
+   (->> intervals
+        (group-by :chr)
+        (into {} (map (fn [[k vs]]
+                        [k
+                         (case structure
+                           :sorted-map (make-sorted-map-intervals vs)
+                           :nclist (make-nclist vs))]))))))
 
 (defn find-overlap-intervals
   "Find intervals that are on the given `chr` and overlap the given interval


Test patch:
diff --git a/test/cljam/util/intervals_test.clj b/test/cljam/util/intervals_test.clj
index 728e839..bf0dc10 100644
--- a/test/cljam/util/intervals_test.clj
+++ b/test/cljam/util/intervals_test.clj
@@ -1,5 +1,6 @@
 (ns cljam.util.intervals-test
-  (:require [clojure.test :refer [deftest is]]
+  (:require [clojure.test :refer [deftest are testing]]
+            [clojure.template :refer [do-template]]
             [cljam.util.intervals :as intervals]))
 
 (def ^:private test-input1
@@ -10,24 +11,31 @@
    {:chr "chr2" :start 200 :end 400}])
 
 (deftest sorted-map-intervals-test
-  (let [smi (intervals/index-intervals test-input1)]
-    (is (= (intervals/find-overlap-intervals smi "chr1" 1 10)
-           [{:chr "chr1" :start 10 :end 100}]))
-    (is (= (intervals/find-overlap-intervals smi "chr1" 1 9) []))
-    (is (= (intervals/find-overlap-intervals smi "chr1" 100 101)
-           [{:chr "chr1" :start 10 :end 100}]))
-    (is (= (intervals/find-overlap-intervals smi "chr1" 101 102) []))
-    (is (= (intervals/find-overlap-intervals smi "chr1" 11 99)
-           [{:chr "chr1" :start 10 :end 100}]))
-    (is (= (intervals/find-overlap-intervals smi "chr2" 10 100)
-           [{:chr "chr2" :start 10 :end 100}]))
-    (is (= (intervals/find-overlap-intervals smi "chr2" 110 111) []))
-    (is (= (intervals/find-overlap-intervals smi "chr2" 90 160)
-           [{:chr "chr2" :start 10 :end 100} {:chr "chr2" :start 150 :end 200}
-            {:chr "chr2" :start 150 :end 250}]))
-    (is (= (intervals/find-overlap-intervals smi "chr2" 150 181)
-           [{:chr "chr2" :start 150 :end 200} {:chr "chr2" :start 150 :end 250}
-            {:chr "chr2" :start 180 :end 300} {:chr "chr2" :start 181 :end 200}]))
-    (is (= (intervals/find-overlap-intervals smi "chr2" 201 240)
-           [{:chr "chr2" :start 150 :end 250} {:chr "chr2" :start 180 :end 300}
-            {:chr "chr2" :start 182 :end 201} {:chr "chr2" :start 200 :end 400}]))))
+  (do-template [index-type]
+               (testing (str index-type)
+                 (let [index
+                       (intervals/index-intervals test-input1
+                                                  {:structure index-type})]
+                   (are [chr start end result]
+                        (= (set (intervals/find-overlap-intervals index chr
+                                                                  start end))
+                           result)
+                     "chr1" 1 10 #{{:chr "chr1" :start 10 :end 100}},
+                     "chr1" 1 9 #{},
+                     "chr1" 100 101 #{{:chr "chr1" :start 10 :end 100}},
+                     "chr1" 101 102 #{},
+                     "chr1" 11 99 #{{:chr "chr1" :start 10 :end 100}},
+                     "chr2" 10 100 #{{:chr "chr2" :start 10 :end 100}},
+                     "chr2" 110 111 #{}
+                     "chr2" 90 160 #{{:chr "chr2" :start 10 :end 100}
+                                     {:chr "chr2" :start 150 :end 200}
+                                     {:chr "chr2" :start 150 :end 250}},
+                     "chr2" 150 181 #{{:chr "chr2" :start 150 :end 200}
+                                      {:chr "chr2" :start 150 :end 250}
+                                      {:chr "chr2" :start 180 :end 300}
+                                      {:chr "chr2" :start 181 :end 200}},
+                     "chr2" 201 240 #{{:chr "chr2" :start 150 :end 250}
+                                      {:chr "chr2" :start 180 :end 300}
+                                      {:chr "chr2" :start 182 :end 201}
+                                      {:chr "chr2" :start 200 :end 400}})))
+               :sorted-map :nclist))