Repository: chrovis/cljam
Pull request #128 (2017-12-21 11:05:20)

Add many util functions for SAM/BAM files & split cljam.io.sam.util.
#### Summary
This PR adds utility functions for SAM/BAM files.
- parsers for optional fields
    - According to [SAM spec](https://github.com/samtools/hts-specs/blob/master/SAMv1.pdf), [optional fields spec](https://github.com/samtools/hts-specs/blob/master/SAMtags.pdf) and [BWA](http://bio-bwa.sourceforge.net/bwa.shtml#tbl).
- reverse-complement sequence
- predicates for flags

Because many functions are placed in `cljam.io.sam.util`,
I split the namespace into some sub-namespaces to keep them organized.

#### Tests

- `lein test :all` 🆗 


Patch:
diff --git a/src/cljam/algo/convert.clj b/src/cljam/algo/convert.clj
index 679529c..cd58da8 100644
--- a/src/cljam/algo/convert.clj
+++ b/src/cljam/algo/convert.clj
@@ -4,7 +4,7 @@
             [cljam.common :refer [*n-threads* get-exec-n-threads]]
             [cljam.io.sam :as sam]
             [cljam.io.bam.encoder :as encoder]
-            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.refs :as refs]
             [cljam.io.sequence :as cseq]
             [cljam.io.util :as io-util]
             [com.climate.claypoole :as cp])
@@ -22,7 +22,7 @@
     (sam/write-alignments wtr alns hdr)))
 
 (defn- bam-write-alignments [rdr wtr hdr num-block]
-  (let [refs (sam-util/make-refs hdr)
+  (let [refs (refs/make-refs hdr)
         n-threads (get-exec-n-threads)]
     (doseq [blocks (cp/pmap (if (= n-threads 1) :serial (dec n-threads))
                             (fn [chunk]
diff --git a/src/cljam/algo/dedupe.clj b/src/cljam/algo/dedupe.clj
index c10c054..8dc3040 100644
--- a/src/cljam/algo/dedupe.clj
+++ b/src/cljam/algo/dedupe.clj
@@ -3,7 +3,7 @@
   (:refer-clojure :exclude [dedupe])
   (:require [com.climate.claypoole :as cp]
             [cljam.io.sam :as sam]
-            [cljam.io.sam.util :as sam-util]))
+            [cljam.io.sam.util.flag :as flag]))
 
 (defn- refs->regions [refs]
   (for [{:keys [name len]} refs]
@@ -14,12 +14,6 @@
     (when-not (and (= (.length q) 1) (= \* (.charAt q 0)))
       (reduce (fn [r x] (+ r (- (int x) 33))) 0 q))))
 
-(defn- paired? [{:keys [flag]}]
-  (pos? (bit-and flag (sam-util/flags :multiple))))
-
-(defn- mapped? [{:keys [flag]}]
-  (zero? (bit-and flag (bit-or (sam-util/flags :unmapped) (sam-util/flags :next-unmapped)))))
-
 (defn dedupe-xform
   "Returns a transducer which removes PCR duplications."
   [& {:keys [remove-dups] :or {remove-dups true}}]
@@ -29,10 +23,12 @@
      (partition-by (juxt :rname :pos))
      (mapcat
       (fn [alns]
-        (loop [[{:keys [pos tlen qname] :as x} :as xs] alns heads {} tails [] dups []]
+        (loop [[{:keys [pos tlen qname flag] :as x} :as xs] alns heads {} tails [] dups []]
           (if x
             (cond
-              (not (and (paired? x) (mapped? x) (= (:rnext x) "="))) (recur (next xs) heads (conj tails x) dups)
+              (not (and (flag/multiple? flag)
+                        (not (flag/both-unmapped? flag))
+                        (= (:rnext x) "="))) (recur (next xs) heads (conj tails x) dups)
               (pos? tlen) (let [k [pos tlen]]
                             (if-let [v (get heads k)]
                               (let [[good bad] (if (pos? (compare (cp v) (cp x))) [v x] [x v])]
diff --git a/src/cljam/algo/depth.clj b/src/cljam/algo/depth.clj
index 3db5159..d3e678a 100644
--- a/src/cljam/algo/depth.clj
+++ b/src/cljam/algo/depth.clj
@@ -5,7 +5,8 @@
             [cljam.common :as common]
             [cljam.util.region :as region]
             [cljam.io.sam :as sam]
-            [cljam.io.sam.util :as sam-util])
+            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.refs :as refs])
   (:import [cljam.io.protocols SAMRegionBlock]))
 
 (def ^:const default-step 1000000)
@@ -51,7 +52,7 @@
   [bam-reader {:keys [chr start end] :or {start 1 end Long/MAX_VALUE}}
    & [{:keys [step n-threads] :or {step default-step n-threads 1}}]]
   {:pre [chr start end (pos? start) (pos? end) (<= start end)]}
-  (when-let [{:keys [len]} (sam-util/ref-by-name (sam/read-refs bam-reader) chr)]
+  (when-let [{:keys [len]} (refs/ref-by-name (sam/read-refs bam-reader) chr)]
     (binding [common/*n-threads* n-threads]
       (lazy-depth* bam-reader chr (min len start) (min len end) step))))
 
@@ -122,7 +123,7 @@
   [bam-reader {:keys [chr start end] :or {start 1 end Long/MAX_VALUE}}
    & [{:keys [step unchecked? n-threads] :or {step default-step unchecked? false n-threads 1}}]]
   {:pre [chr start end (pos? start) (pos? end) (<= start end)]}
-  (when-let [{:keys [len]} (sam-util/ref-by-name (sam/read-refs bam-reader) chr)]
+  (when-let [{:keys [len]} (refs/ref-by-name (sam/read-refs bam-reader) chr)]
     (seq
      (depth*
       bam-reader
diff --git a/src/cljam/algo/pileup/mpileup.clj b/src/cljam/algo/pileup/mpileup.clj
index c52920c..91f8712 100644
--- a/src/cljam/algo/pileup/mpileup.clj
+++ b/src/cljam/algo/pileup/mpileup.clj
@@ -3,9 +3,10 @@
             [clojure.string :as cstr]
             [clojure.tools.logging :as logging]
             [cljam.io.sam :as sam]
-            [cljam.io.sam.util :as sam-util]
-            [cljam.io.sequence :as cseq]
-            [cljam.io.util.cigar :as cig]))
+            [cljam.io.sam.util.cigar :as cigar]
+            [cljam.io.sam.util.flag :as flag]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sequence :as cseq]))
 
 (defn to-mpileup
   "Stringify mpileup sequence."
@@ -67,7 +68,7 @@
        (map
         (fn [alns]
           (->> alns
-               (map (fn [a] (assoc a :cig-index (cig/to-index (:cigar a)))))
+               (map (fn [a] (assoc a :cig-index (cigar/to-index (:cigar a)))))
                (pileup-seq start end))))
        (apply map
               (fn [index refs & plps]
@@ -77,14 +78,10 @@
 
 (defn basic-mpileup-pred
   "Basic predicate function for filtering alignments for mpileup."
-  [a]
-  (and (:flag a)
-       (sam-util/primary? (:flag a)) ;; primary
-       (zero? (bit-and 0x4 (:flag a))) ;; mapped
-       (zero? (bit-and 0x200 (:flag a))) ;; QC pass
-       (zero? (bit-and 0x400 (:flag a))) ;; Not duplicated
-       (or (zero? (bit-and 0x1 (:flag a))) ;; single-end
-           (pos? (bit-and 0x2 (:flag a)))))) ;; properly-paired
+  [{:keys [flag]}]
+  (and flag
+       (zero? (bit-and (flag/encoded #{:unmapped :filtered-out :duplicated :supplementary :secondary}) flag))
+       (or (not (flag/multiple? flag)) (flag/properly-aligned? flag))))
 
 (defn- correct-qual
   "Correct quality of two overlapped mate reads by setting zero quality for one of the base."
@@ -130,7 +127,7 @@
    (pileup nil bam-reader region))
   ([ref-reader bam-reader {:keys [chr start end] :or {start -1 end -1}}]
    (try
-     (if-let [r (sam-util/ref-by-name (sam/read-refs bam-reader) chr)]
+     (if-let [r (refs/ref-by-name (sam/read-refs bam-reader) chr)]
        (let [s (if (neg? start) 1 start)
              e (if (neg? end) (:len r) end)
              refseq (if ref-reader
diff --git a/src/cljam/algo/sorter.clj b/src/cljam/algo/sorter.clj
index 56edc0e..2a90801 100644
--- a/src/cljam/algo/sorter.clj
+++ b/src/cljam/algo/sorter.clj
@@ -1,5 +1,6 @@
 (ns cljam.algo.sorter
   "Sorter of the SAM/BAM format alignments."
+  (:refer-clojure :exclude [sorted?])
   (:require [clojure.java.io :as cio]
             [clojure.tools.logging :as logging]
             [com.climate.claypoole :as cp]
@@ -7,19 +8,11 @@
             [cljam.io.sam :as sam]
             [cljam.io.util :as io-util]
             [cljam.util :as util]
-            [cljam.io.sam.common :refer [sam-version]])
+            [cljam.io.sam.util.header :as header])
   (:import [java.io Closeable File]
            [java.util PriorityQueue]))
 
 (def ^:const default-chunk-size 1500000)
-(def ^:const order-unknown :unknown)
-(def ^:const order-coordinate :coordinate)
-(def ^:const order-queryname :queryname)
-
-(defn- replace-header
-  "Replaces version number and sorting info of the header."
-  [hdr vn so]
-  (assoc hdr :HD {:VN vn, :SO so}))
 
 (defn- refmap
   [refs]
@@ -60,8 +53,8 @@
   "Splits SAM/BAM file into multiple files each containing alignments up to chunk-size.
   name-fn must be a function taking a int value i and returning a path string for i-th output.
   read-fn must produce a sequence of alignments and write-fn must consume the splitted sequence."
-  [rdr chunk-size name-fn read-fn write-fn]
-  (let [hdr (replace-header (sam/read-header rdr) sam-version (name order-coordinate))]
+  [rdr mode chunk-size name-fn read-fn write-fn]
+  (let [hdr (header/sorted-by mode (header/update-version (sam/read-header rdr)))]
     (logging/info "Splitting...")
     (cp/with-shutdown! [p (cp/threadpool (cp/ncpus))]
       (->> (read-fn rdr)
@@ -90,7 +83,7 @@
         write-fn (if block?
                    (fn [w xs _] (sam/write-blocks w (sort-fn xs)))
                    (fn [w xs hdr] (sam/write-alignments w (sort-fn xs) hdr)))]
-    (split** rdr chunk-size name-fn read-fn write-fn)))
+    (split** rdr mode chunk-size name-fn read-fn write-fn)))
 
 (defn- head-pq
   "Take a smallest element from sequences in priority queue."
@@ -161,11 +154,10 @@
                      protocols/reader-path
                      util/basename
                      (partial gen-cache-filename (name cache-fmt)))
-        key-fn (case mode
-                 :coordinate (partial coordinate-key (refmap (sam/read-refs rdr)))
-                 :queryname queryname-key)
+        key-fn ({header/order-coordinate (partial coordinate-key (refmap (sam/read-refs rdr)))
+                 header/order-queryname queryname-key} mode)
         splitted-files (split* rdr chunk-size name-fn mode #(sort-by-index key-fn %))
-        hdr (replace-header (sam/read-header rdr) sam-version (name mode))]
+        hdr (header/sorted-by mode (header/update-version (sam/read-header rdr)))]
     (logging/info (str "Merging from " (count splitted-files) " files..."))
     (merge* wtr hdr splitted-files mode key-fn)
     (logging/info "Deleting cache files...")
@@ -174,25 +166,21 @@
 (defn sort-by-pos
   "Sorts alignments by chromosomal position."
   [rdr wtr & [option]]
-  (sort! rdr wtr (into (or option {}) {:mode :coordinate})))
+  (sort! rdr wtr (into (or option {}) {:mode header/order-coordinate})))
 
 (defn sort-by-qname
   "Sort alignments by query name."
   [rdr wtr & [option]]
-  (sort! rdr wtr (into (or option {}) {:mode :queryname})))
+  (sort! rdr wtr (into (or option {}) {:mode header/order-queryname})))
 
-(defn sorted-by?
+(defn sorted?
   "Returns true if the sam is sorted, false if not. It is detected by
   `@HD SO:***` tag in the header."
   [rdr]
-  (let [so (:SO (:HD (sam/read-header rdr)))]
-    (or (= so (name order-queryname))
-        (= so (name order-coordinate)))))
+  (header/sorted? (sam/read-header rdr)))
 
 (defn sort-order
   "Returns sorting order of the sam as Keyword. Returning order is one of the
   following: :queryname, :coordinate, :unsorted, :unknown."
   [rdr]
-  (if-let [so (:SO (:HD (sam/read-header rdr)))]
-    (keyword so)
-    order-unknown))
+  (header/sort-order (sam/read-header rdr)))
diff --git a/src/cljam/io/bam/decoder.clj b/src/cljam/io/bam/decoder.clj
index 602d7d3..1934d06 100644
--- a/src/cljam/io/bam/decoder.clj
+++ b/src/cljam/io/bam/decoder.clj
@@ -3,10 +3,12 @@
   (:require [clojure.string :as cstr]
             [proton.core :as proton]
             [cljam.util :as util]
-            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.quality :as qual]
+            [cljam.io.sam.util.sequence :as sam-seq]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sam.util.cigar :as cigar]
             [cljam.io.bam.common :as common]
-            [cljam.io.util.lsb :as lsb]
-            [cljam.io.util.cigar :as cigar])
+            [cljam.io.util.lsb :as lsb])
   (:import [java.util Arrays]
            [java.nio ByteBuffer ByteOrder CharBuffer]
            [cljam.io.protocols SAMAlignment SAMRegionBlock SAMCoordinateBlock SAMQuerynameBlock]))
@@ -84,17 +86,17 @@
 (defn decode-qual [^bytes b]
   (if (Arrays/equals b (byte-array (alength b) (util/ubyte 0xff)))
     "*"
-    (sam-util/phred-bytes->fastq b)))
+    (qual/phred-bytes->fastq b)))
 
 (defn decode-seq [seq-bytes length]
-  (sam-util/compressed-bases->str length seq-bytes 0))
+  (sam-seq/compressed-bases->str length seq-bytes 0))
 
 (defn decode-next-ref-id [refs ^long ref-id ^long next-ref-id]
   (if (= next-ref-id -1)
     "*"
     (if (= ref-id next-ref-id)
       "="
-      (sam-util/ref-name refs next-ref-id))))
+      (refs/ref-name refs next-ref-id))))
 
 (defrecord BAMRawBlock [data ^long pointer-beg ^long pointer-end])
 
@@ -105,7 +107,7 @@
   ([refs block]
    (let [buffer      (ByteBuffer/wrap (:data block))
          ref-id      ^int (lsb/read-int buffer)
-         rname       (or (sam-util/ref-name refs ref-id) "*")
+         rname       (or (refs/ref-name refs ref-id) "*")
          pos         (inc ^int (lsb/read-int buffer))
          l-read-name (int ^long (lsb/read-ubyte buffer))
          mapq        ^long (lsb/read-ubyte buffer)
@@ -152,7 +154,7 @@
            (let [seq     (decode-seq (lsb/read-bytes buffer (quot (inc l-seq) 2)) l-seq)
                  qual    (decode-qual (lsb/read-bytes buffer l-seq))
                  rest    (lsb/read-bytes buffer (options-size (alength ^bytes (:data block)) l-read-name n-cigar-op l-seq))
-                 rname   (or (sam-util/ref-name refs ref-id) "*")
+                 rname   (or (refs/ref-name refs ref-id) "*")
                  options (decode-options rest)]
              (SAMAlignment. qname (int flag) rname (int pos) ref-end (int mapq)
                             cigar rnext (int pnext) (int tlen) seq qual options))))))))
diff --git a/src/cljam/io/bam/encoder.clj b/src/cljam/io/bam/encoder.clj
index dcc58ab..b61684b 100644
--- a/src/cljam/io/bam/encoder.clj
+++ b/src/cljam/io/bam/encoder.clj
@@ -3,7 +3,10 @@
   (:require [clojure.string :as cstr]
             [cljam.util :as util]
             [cljam.io.sam.util :as sam-util]
-            [cljam.io.util.cigar :as cgr]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sam.util.quality :as qual]
+            [cljam.io.sam.util.cigar :as cigar]
+            [cljam.io.sam.util.sequence :as seq]
             [cljam.io.util.lsb :as lsb]
             [cljam.io.bam.common :as common]))
 
@@ -13,8 +16,8 @@
 (defn- get-next-ref-id [sa refs]
   (condp = (:rnext sa)
     "*" -1
-    "=" (if-let [id (sam-util/ref-id refs (:rname sa))] id -1)
-    (if-let [id (sam-util/ref-id refs (:rnext sa))] id -1)))
+    "=" (if-let [id (refs/ref-id refs (:rname sa))] id -1)
+    (if-let [id (refs/ref-id refs (:rnext sa))] id -1)))
 
 (defn- get-options-size [sam-alignment]
   (->> (map
@@ -44,7 +47,7 @@
 (defn- encode-qual [sam-alignment]
   (if (= (:qual sam-alignment) "*")
     (byte-array (.length ^String (:seq sam-alignment)) (util/ubyte 0xff))
-    (sam-util/fastq->phred (:qual sam-alignment))))
+    (qual/fastq->phred (:qual sam-alignment))))
 
 (defn- encode-tag-value [writer val-type value]
   (case val-type
@@ -70,7 +73,7 @@
 
 (defn get-block-size [aln]
   (let [read-length (.length ^String (:seq aln))
-        cigar-length ^long (cgr/count-op (:cigar aln))]
+        cigar-length ^long (cigar/count-op (:cigar aln))]
     (+ ^long common/fixed-block-size
        (.length ^String (:qname aln))
        1 ;; null
@@ -81,7 +84,7 @@
 
 (defn encode-alignment [wrtr aln refs]
   ;; refID
-  (lsb/write-int wrtr (or (sam-util/ref-id refs (:rname aln)) -1))
+  (lsb/write-int wrtr (or (refs/ref-id refs (:rname aln)) -1))
   ;; pos
   (lsb/write-int wrtr (dec (:pos aln)))
   ;; bin_mq_nl
@@ -89,7 +92,7 @@
   (lsb/write-ubyte wrtr (short (:mapq aln)))
   (lsb/write-ushort wrtr (sam-util/compute-bin aln))
   ;; flag_nc
-  (lsb/write-ushort wrtr (cgr/count-op (:cigar aln)))
+  (lsb/write-ushort wrtr (cigar/count-op (:cigar aln)))
   (lsb/write-ushort wrtr (:flag aln))
   ;; l_seq
   (lsb/write-int wrtr (.length ^String (:seq aln)))
@@ -103,10 +106,10 @@
   (lsb/write-string wrtr (:qname aln))
   (lsb/write-bytes wrtr (byte-array 1 (byte 0)))
   ;; cigar
-  (doseq [cigar (cgr/encode-cigar (:cigar aln))]
+  (doseq [cigar (cigar/encode-cigar (:cigar aln))]
     (lsb/write-int wrtr cigar))
   ;; seq
-  (lsb/write-bytes wrtr (sam-util/str->compressed-bases (:seq aln)))
+  (lsb/write-bytes wrtr (seq/str->compressed-bases (:seq aln)))
   ;; qual
   (lsb/write-bytes wrtr (encode-qual aln))
   ;; options
diff --git a/src/cljam/io/bam/reader.clj b/src/cljam/io/bam/reader.clj
index c2d3758..7cf19ec 100644
--- a/src/cljam/io/bam/reader.clj
+++ b/src/cljam/io/bam/reader.clj
@@ -1,7 +1,8 @@
 (ns cljam.io.bam.reader
   "Reader of BAM file format."
   (:require [cljam.io.protocols :as protocols]
-            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sam.util.header :as header]
             [cljam.io.bam-index.core :as bai]
             [cljam.io.bam.decoder :as decoder]
             [cljam.io.util.lsb :as lsb])
@@ -121,7 +122,7 @@
       (do (.seek ^BGZFInputStream (.reader rdr) (ffirst (bai/get-unplaced-spans bai)))
           (read-blocks-sequentially* rdr decoder))
       (let [refs (.refs rdr)]
-        (->> (bai/get-spans bai (sam-util/ref-id refs chr) start end)
+        (->> (bai/get-spans bai (refs/ref-id refs chr) start end)
              (eduction
               (comp
                (mapcat
@@ -132,7 +133,7 @@
 (defn load-headers
   "Reads header section of BAM file and returns it as a map."
   [rdr]
-  (let [header (sam-util/parse-header (lsb/read-string rdr (lsb/read-int rdr)))
+  (let [header (header/parse-header (lsb/read-string rdr (lsb/read-int rdr)))
         n-ref (lsb/read-int rdr)
         refs (loop [i n-ref, ret []]
                (if (zero? i)
diff --git a/src/cljam/io/bam/writer.clj b/src/cljam/io/bam/writer.clj
index a9c28ab..ec85c26 100644
--- a/src/cljam/io/bam/writer.clj
+++ b/src/cljam/io/bam/writer.clj
@@ -1,7 +1,8 @@
 (ns cljam.io.bam.writer
   "Writer of BAM file format."
   (:require [cljam.io.protocols :as protocols]
-            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sam.util.header :as header]
             [cljam.io.util.lsb :as lsb]
             [cljam.io.bam.common :as common]
             [cljam.io.bam.encoder :as encoder])
@@ -36,14 +37,14 @@
 
 (defn write-header* [^BAMWriter wtr header]
   (let [w (.writer wtr)
-        header-string (str (sam-util/stringify-header header) \newline)]
+        header-string (str (header/stringify-header header) \newline)]
     (lsb/write-bytes w (.getBytes ^String common/bam-magic)) ; magic
     (lsb/write-int w (count header-string))
     (lsb/write-string w header-string)))
 
 (defn write-refs* [^BAMWriter wtr header]
   (let [w (.writer wtr)
-        refs (sam-util/make-refs header)]
+        refs (refs/make-refs header)]
     (lsb/write-int w (count refs))
     (doseq [ref refs]
       (lsb/write-int w (inc (count (:name ref))))
@@ -53,7 +54,7 @@
 
 (defn write-alignments* [^BAMWriter wtr alns header]
   (let [w (.writer wtr)
-        refs (sam-util/make-refs header)]
+        refs (refs/make-refs header)]
     (doseq [a alns]
       (lsb/write-int w (encoder/get-block-size a))
       (encoder/encode-alignment w a refs))))
diff --git a/src/cljam/io/sam/reader.clj b/src/cljam/io/sam/reader.clj
index 66e3b33..93a5db6 100644
--- a/src/cljam/io/sam/reader.clj
+++ b/src/cljam/io/sam/reader.clj
@@ -2,6 +2,8 @@
   (:require [clojure.java.io :as cio]
             [clojure.tools.logging :as logging]
             [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.refs :as refs]
+            [cljam.io.sam.util.header :as header]
             [cljam.io.protocols :as protocols])
   (:import [java.io BufferedReader Closeable]
            [cljam.io.protocols SAMCoordinateBlock SAMQuerynameBlock]))
@@ -31,7 +33,7 @@
   (read-header [this]
     (.header this))
   (read-refs [this]
-    (vec (sam-util/make-refs (.header this))))
+    (vec (refs/make-refs (.header this))))
   (read-alignments [this]
     (protocols/read-alignments this {}))
   (read-alignments [this {:keys [chr start end] :as region}]
@@ -104,8 +106,8 @@
        (transduce
         (comp
          (take-while (fn [line] (= (first line) \@)))
-         (map sam-util/parse-header-line))
-        sam-util/into-header)))
+         (map header/parse-header-line))
+        header/into-header)))
 
 (defn reader [f]
   (let [header (with-open [r (cio/reader f)]
diff --git a/src/cljam/io/sam/util.clj b/src/cljam/io/sam/util.clj
index 60b411d..da2fcb9 100644
--- a/src/cljam/io/sam/util.clj
+++ b/src/cljam/io/sam/util.clj
@@ -1,108 +1,15 @@
 (ns cljam.io.sam.util
   "Utilities related to SAM/BAM format."
   (:require [clojure.string :as cstr]
-            [proton.core :refer [as-long as-double hex->bytes]]
             cljam.io.protocols
-            [cljam.io.util.cigar :as cigar])
+            [cljam.io.sam.util.cigar :as cigar]
+            [cljam.io.sam.util.option :as opt])
   (:import [java.nio CharBuffer ByteBuffer]
            [java.nio.charset StandardCharsets]
            [cljam.io.protocols SAMAlignment]))
 
 ;;; parse
 
-(defn- parse-header-keyvalues
-  "e.g. \"LN:45 SN:ref\" -> {:LN 45, :SN \"ref\"}"
-  [keyvalues]
-  (into
-   {}
-   (map (fn [kv]
-          (let [[k v] (cstr/split kv #":" 2)]
-            [(keyword k)
-             (case k
-               "LN" (Integer/parseInt v)
-               "PI" (Integer/parseInt v)
-               v)])))
-   keyvalues))
-
-(defn parse-header-line
-  "e.g. \"@SQ	SN:ref	LN:45\" => [:SQ {:SN \"ref\" :LN 45}]"
-  [line]
-  (let [[typ & kvs] (cstr/split line #"\t")]
-    [(keyword (subs typ 1)) (parse-header-keyvalues kvs)]))
-
-(defn- finalize-rf
-  "Wrap a reducing function with finalizing function."
-  [rf f]
-  (fn finalize-rf-inner
-    ([] (rf))
-    ([x] (f (rf x)))
-    ([x y] (rf x y))))
-
-(defn- into-rf
-  "Returns a reducing function which returns a new coll with elements conjoined."
-  [to]
-  (if (instance? clojure.lang.IEditableCollection to)
-      (fn into-rf-editable
-        ([] (transient to))
-        ([x] (with-meta (persistent! x) (meta to)))
-        ([r x] (conj! r x)))
-      (fn into-rf-non-editable
-        ([] to)
-        ([x] x)
-        ([r x] (conj r x)))))
-
-(defn- group-by-rf
-  "Returns a reducing function acts like `group-by`.
-  Second argument `rf` is a reducing function appliede to each group. Default is (into-rf [])."
-  ([keyfn] (group-by-rf keyfn (into-rf [])))
-  ([keyfn rf]
-   (fn group-by-rf-inner
-     ([] (transient {}))
-     ([x] (into {} (map (fn group-by-rf-finalize [[k v]] [k (rf v)])) (persistent! x)))
-     ([x y] (let [k (keyfn y)]
-              (if-let [old (get x k)]
-                (assoc! x k (rf old y))
-                (assoc! x k (rf (rf) y))))))))
-
-(def into-header
-  (-> (group-by-rf first ((map second) (into-rf [])))
-      (finalize-rf (fn [m] (if (some? (:HD m)) (update m :HD first) m)))))
-
-(defn parse-header
-  "Parse a header string, returning a map of the header."
-  [s]
-  (->> (cstr/split-lines s)
-       (transduce
-        (map parse-header-line)
-        into-header)))
-
-(defn- parse-tag-single [val-type val]
-  (case val-type
-    \Z val
-    \A (first val)
-    \I (as-long val)
-    \i (as-long val)
-    \s (as-long val)
-    \S (as-long val)
-    \c (as-long val)
-    \C (as-long val)
-    \f (as-double val)
-    \H (hex->bytes val)
-    (throw (Exception. "Unrecognized tag type"))))
-
-(defn- parse-optional-fields [options]
-  (map (fn [op]
-         (let [[tag val-type-str val] (cstr/split op #":")
-               val-type (first val-type-str)]
-           {(keyword tag) {:type val-type-str
-                           :value (if (= val-type \B)
-                                    val
-                                    (parse-tag-single val-type val))}}))
-       options))
-
-(defn- parse-seq-text [s]
-  (cstr/upper-case s))
-
 (defn parse-alignment
   "Parse an alignment line, returning a map of the alignment."
   [line]
@@ -111,50 +18,17 @@
         ref-length (cigar/count-ref cigar)
         end (if (zero? ref-length) 0 (int (dec (+ pos ref-length))))]
     (SAMAlignment. qname (Integer/parseInt flag) rname pos end (Integer/parseInt mapq)
-                   cigar rnext (Integer/parseInt pnext) (Integer/parseInt tlen) (parse-seq-text seq)
-                   qual (vec (parse-optional-fields options)))))
+                   cigar rnext (Integer/parseInt pnext) (Integer/parseInt tlen) (cstr/upper-case seq)
+                   qual (map opt/parse-optional-field options))))
 
 ;;; stringify
 
-(defn- stringify-header-keyvalues [kv-map]
-  (cstr/join \tab
-             (map (fn [kv]
-                    (let [[k v] (seq kv)]
-                      (str (name k) \: v)))
-                  kv-map)))
-
-(defn- stringify-optional-fields [options]
-  (cstr/join \tab
-             (map (fn [op]
-                    (let [[tag entity] (first (seq op))]
-                      (str (name tag) \: (:type entity) \: (:value entity))))
-                  options)))
-
-(defn stringify-header [hdr]
-  (cstr/join \newline
-             (map (fn [h]
-                    (let [[typ kvs] h]
-                      (if (= typ :HD)
-                        (str "@HD" \tab (stringify-header-keyvalues kvs))
-                        (cstr/join \newline
-                                   (map #(str \@ (name typ) \tab (stringify-header-keyvalues %)) kvs)))))
-                  (seq hdr))))
-
-(defn stringify-alignment [sa]
-  (cstr/trim
-   (cstr/join \tab
-              [(:qname sa)
-               (:flag  sa)
-               (:rname sa)
-               (:pos   sa)
-               (:mapq  sa)
-               (:cigar sa)
-               (:rnext sa)
-               (:pnext sa)
-               (:tlen  sa)
-               (:seq   sa)
-               (:qual  sa)
-               (stringify-optional-fields (:options sa))])))
+(defn stringify-alignment [a]
+  (->> a
+       ((juxt :qname :flag :rname :pos :mapq :cigar :rnext :pnext :tlen :seq :qual
+              (comp opt/stringify-optional-fields :options)))
+       (cstr/join \tab)
+       cstr/trim))
 
 ;;; indexing bin
 
@@ -195,181 +69,3 @@
   (let [beg (dec (:pos aln))
         end (get-end aln)]
    (reg->bin beg end)))
-
-(def ^:private ^:const nibble-to-base-table
-  ;; Index: nibble of a compressed base.
-  ;; Value: base for the nibble.
-  "=ACMGRSVTWYHKDBN")
-
-(def ^:private two-bytes-to-compressed-bases-table
-  ;; Index: two bases (A,C) => ASCII (65,67) => 2r 1000001 1000011 => 8387
-  ;; Value: two bases (A,C) => nibbles (1,2) => 2r 0001 0010 => 18
-  (let [ba (byte-array (bit-shift-left 1 14))
-        byte-to-nibble-table (byte-array (bit-shift-left 1 7) (byte 15))]
-    (doseq [[i c] (map vector (range) nibble-to-base-table)]
-      (aset-byte byte-to-nibble-table (int c) i)
-      (aset-byte byte-to-nibble-table (int (.charAt (cstr/lower-case c) 0)) i))
-    (dotimes [i (alength ba)]
-      (let [u (unchecked-byte (bit-and 0x7F (unsigned-bit-shift-right i 7)))
-            l (unchecked-byte (bit-and 0x7F i))]
-        (->> (aget byte-to-nibble-table l)
-             (bit-or (bit-shift-left (aget byte-to-nibble-table u) 4))
-             unchecked-byte
-             (aset-byte ba i))))
-    ba))
-
-(defn str->compressed-bases
-  "Creates a buffer consists of compressed bases from ASCII sequence."
-  ^bytes [^String s]
-  (let [b (.getBytes s)
-        length (alength b)
-        result-len (quot (inc length) 2)
-        in-bb (ByteBuffer/wrap b)
-        out-bb (ByteBuffer/allocate result-len)]
-    (dotimes [i result-len]
-      (let [u (.get in-bb)
-            l (byte (if (.hasRemaining in-bb) (.get in-bb) \=))]
-        (->> (bit-and 0x7F l)
-             (bit-or (bit-shift-left (bit-and 0x7F u) 7))
-             (aget ^bytes two-bytes-to-compressed-bases-table)
-             (.put out-bb))))
-    (.array out-bb)))
-
-(def ^:const ^:private compressed-bases-to-bases-table
-  ;; Index: compressed base n containing two nibbles => 2n
-  ;; Value 2n+0: base for upper nibble of n.
-  ;; Value 2n+1: base for lower nibble of n.
-  (->> (for [i nibble-to-base-table j nibble-to-base-table] [i j])
-       (apply concat)
-       cstr/join))
-
-(defn compressed-bases->str
-  "Decode a sequence from byte array to String."
-  [^long length ^bytes compressed-bases ^long compressed-offset]
-  (let [cb (CharBuffer/allocate (inc length))
-        bb (ByteBuffer/wrap compressed-bases)]
-    (.position bb compressed-offset)
-    (dotimes [_ (quot (inc length) 2)]
-      (let [i (-> (.get bb) (bit-and 0xff) (* 2))]
-        (.put cb (.charAt compressed-bases-to-bases-table i))
-        (.put cb (.charAt compressed-bases-to-bases-table (inc i)))))
-    (.limit cb length)
-    (.flip cb)
-    (.toString cb)))
-
-(defn normalize-bases
-  "Converts bases in given buffer to upper-case. Also converts '.' to 'N'.
-   Bases are represented as buffer of ASCII characters."
-  ^bytes [^bytes bases]
-  (dotimes [i (alength bases)]
-    (let [b (aget bases i)]
-      (cond
-        (= b (byte \.)) (aset-byte bases i (byte \N))
-        (<= (byte \a) b (byte \z)) (aset-byte bases i (- b 32))))) ;; Upper-case ASCII offset
-  bases)
-
-;;; fastq and phred
-
-(defmacro fastq-char->phred-byte [ch]
-  `(byte (- (int ~ch) 33)))
-
-(defmacro phred-byte->fastq-char [b]
-  `(unchecked-char (unchecked-add ~b 33)))
-
-(defn fastq->phred ^bytes [^String fastq]
-  (let [b (.getBytes fastq)
-        in-bb (ByteBuffer/wrap b)
-        out-bb (ByteBuffer/allocate (alength b))]
-    (while (.hasRemaining in-bb)
-      (.put out-bb (fastq-char->phred-byte (.get in-bb))))
-    (.array out-bb)))
-
-(defmulti phred->fastq class)
-
-(defn phred-bytes->fastq
-  [^bytes b]
-  (when-not (nil? b)
-    (let [bb (ByteBuffer/wrap b)
-          cb (CharBuffer/allocate (alength b))]
-      (loop []
-        (when (.hasRemaining bb)
-          (.put cb (phred-byte->fastq-char (.get bb)))
-          (recur)))
-      (.flip cb)
-      (.toString cb))))
-
-(defmethod phred->fastq (class (byte-array nil))
-  [^bytes b]
-  (phred-bytes->fastq b))
-
-(def ^:const max-phred-score 93)
-
-(defmethod phred->fastq Integer
-  [n]
-  {:pre [(<= 0 n max-phred-score)]}
-  (phred-byte->fastq-char n))
-
-;;; Reference functions
-
-(defn make-refs
-  "Return a reference sequence from the sam header."
-  [hdr]
-  (for [sq (:SQ hdr)]
-    {:name (:SN sq), :len (:LN sq)}))
-
-(defn- ref-id*
-  [refs name]
-  (some #(when (= name (:name (second %))) (first %))
-        (map-indexed vector refs)))
-
-(def ref-id
-  "Returns reference ID from the reference sequence and the specified reference
-  name. If not found, returns nil."
-  (memoize ref-id*))
-
-(defn ref-name
-  "Returns a reference name from the reference ID. Returns nil if id is not
-  mapped."
-  [refs ^long id]
-  (when (<= 0 id (dec (count refs)))
-    (:name (nth refs id))))
-
-(defn ref-by-name
-  "Returns the first reference which has the specified name."
-  [refs name]
-  (some #(if (= (:name %) name) %) refs))
-
-(def ^:const flags
-  {:multiple         1 ; template having multiple segments in sequencing
-   :properly-aligned 2 ; each segment properly aligned according to the aligner
-   :unmapped         4 ; segment unmapped
-   :next-unmapped    8 ; next segment in the template unmapped
-   :reversed        16 ; SEQ begin reverse complemented
-   :next-reversed   32 ; SEQ of the next segment in the template being reverse complemented
-   :first           64 ; the first segment in the template
-   :last           128 ; the last segment in the template
-   :secondary      256 ; secondary alignment
-   :filtered-out   512 ; not passing filters, such as platform/vendor quality controls
-   :duplicated    1024 ; PCR or optical duplicate
-   :supplementary 2048 ; supplementary alignment
-   })
-
-(def ^:const flag-keywords
-  (vec (map vector (map key (sort-by val flags)) (range))))
-
-(defn decode-flags
-  "Returns a set of keywords for a given flag integer."
-  [f]
-  (into #{} (for [[k i] flag-keywords :when (bit-test f i)] k)))
-
-(defn encode-flags
-  "Returns a flag integer encoding set of keywords."
-  [s]
-  (reduce + (map flags s)))
-
-(defn primary?
-  "Returns true when an alignment with given flag is a primary line."
-  [f]
-  (cond
-    (integer? f) (zero? (bit-and f 0x900))
-    (set? f) (nil? (or (:supplementary f) (:secondary f)))))
diff --git a/src/cljam/io/util/cigar.clj b/src/cljam/io/sam/util/cigar.clj
similarity index 99%
rename from src/cljam/io/util/cigar.clj
rename to src/cljam/io/sam/util/cigar.clj
index b3ef5a3..6a9e4e6 100644
--- a/src/cljam/io/util/cigar.clj
+++ b/src/cljam/io/sam/util/cigar.clj
@@ -1,4 +1,4 @@
-(ns cljam.io.util.cigar
+(ns cljam.io.sam.util.cigar
   "Parser of CIGAR strings."
   (:import [java.nio ByteBuffer ByteOrder]))
 
diff --git a/src/cljam/io/sam/util/flag.clj b/src/cljam/io/sam/util/flag.clj
new file mode 100644
index 0000000..106a39e
--- /dev/null
+++ b/src/cljam/io/sam/util/flag.clj
@@ -0,0 +1,88 @@
+(ns cljam.io.sam.util.flag
+  "Utility functions for SAM flags.")
+
+(def ^:const flags
+  {:multiple         1 ; template having multiple segments in sequencing
+   :properly-aligned 2 ; each segment properly aligned according to the aligner
+   :unmapped         4 ; segment unmapped
+   :next-unmapped    8 ; next segment in the template unmapped
+   :reversed        16 ; SEQ begin reverse complemented
+   :next-reversed   32 ; SEQ of the next segment in the template being reverse complemented
+   :first           64 ; the first segment in the template
+   :last           128 ; the last segment in the template
+   :secondary      256 ; secondary alignment
+   :filtered-out   512 ; not passing filters, such as platform/vendor quality controls
+   :duplicated    1024 ; PCR or optical duplicate
+   :supplementary 2048 ; supplementary alignment
+   })
+
+(def ^:const flag-keywords
+  (vec (map vector (map key (sort-by val flags)) (range))))
+
+(defn decode
+  "Returns a set of keywords for a given flag integer."
+  [^long f]
+  (into #{} (for [[k i] flag-keywords :when (bit-test f i)] k)))
+
+(defn encode
+  "Returns a flag integer encoding set of keywords."
+  [flag-set]
+  (reduce + (map flags flag-set)))
+
+(defmacro encoded
+  "Macro to provide a encoded flag with set of keywords."
+  [flag-set-literal]
+  (let [f (encode flag-set-literal)]
+    f))
+
+(defn primary?
+  "Returns true when an alignment with given flag is a primary line."
+  [^long f]
+  (zero? (bit-and f 0x900)))
+
+(defn multiple?
+  "Tests if the template has multiple segments."
+  [^long f]
+  (bit-test f 0))
+
+(defn properly-aligned?
+  "Tests if the paired-end segments are properly aligned."
+  [^long f]
+  (bit-test f 1))
+
+(defn unmapped?
+  "Tests if the segment is unmapped."
+  [^long f]
+  (bit-test f 2))
+
+(defn both-unmapped?
+  "Tests if both the segment and its mate segment are unmapped."
+  [^long f]
+  (zero? (bit-xor (bit-and f 0xC) 0xC)))
+
+(defn reversed?
+  "Tests if the segment is reversed."
+  [^long f]
+  (bit-test f 4))
+
+(defn r1?
+  "Tests if the segment is the first in the template."
+  [^long f]
+  (bit-test f 6))
+
+(defn r2?
+  "Tests if the segment is the last in the template."
+  [^long f]
+  (bit-test f 7))
+
+(defn r1r2
+  "Returns 0 for single-end, 1 for R1 and 2 for R2."
+  [^long f]
+  (-> f
+      (bit-and 0xC0) ;; last-bit first-bit
+      (unsigned-bit-shift-right 6)))
+
+(defn secondary?
+  "Tests if the alignment is secondary."
+  [^long f]
+  (bit-test f 8))
diff --git a/src/cljam/io/sam/util/header.clj b/src/cljam/io/sam/util/header.clj
new file mode 100644
index 0000000..5ee7e62
--- /dev/null
+++ b/src/cljam/io/sam/util/header.clj
@@ -0,0 +1,124 @@
+(ns cljam.io.sam.util.header
+  "Utility functions for SAM header."
+  (:refer-clojure :exclude [sorted?])
+  (:require [clojure.string :as cstr]
+            [cljam.io.sam.common :as sam-common])
+  (:import clojure.lang.IEditableCollection))
+
+;;; parse
+
+(defn- parse-header-keyvalues
+  "e.g. \"LN:45 SN:ref\" -> {:LN 45, :SN \"ref\"}"
+  [keyvalues]
+  (into
+   {}
+   (map (fn [kv]
+          (let [[k v] (cstr/split kv #":" 2)]
+            [(keyword k)
+             (case k
+               "LN" (Integer/parseInt v)
+               "PI" (Integer/parseInt v)
+               v)])))
+   keyvalues))
+
+(defn parse-header-line
+  "e.g. \"@SQ	SN:ref	LN:45\" => [:SQ {:SN \"ref\" :LN 45}]"
+  [line]
+  (let [[typ & kvs] (cstr/split line #"\t")]
+    [(keyword (subs typ 1)) (parse-header-keyvalues kvs)]))
+
+(defn- finalize-rf
+  "Wrap a reducing function with finalizing function."
+  [rf f]
+  (fn finalize-rf-inner
+    ([] (rf))
+    ([x] (f (rf x)))
+    ([x y] (rf x y))))
+
+(defn- into-rf
+  "Returns a reducing function which returns a new coll with elements conjoined."
+  [to]
+  (if (instance? IEditableCollection to)
+      (fn into-rf-editable
+        ([] (transient to))
+        ([x] (with-meta (persistent! x) (meta to)))
+        ([r x] (conj! r x)))
+      (fn into-rf-non-editable
+        ([] to)
+        ([x] x)
+        ([r x] (conj r x)))))
+
+(defn- group-by-rf
+  "Returns a reducing function acts like `group-by`.
+  Second argument `rf` is a reducing function appliede to each group. Default is (into-rf [])."
+  ([keyfn] (group-by-rf keyfn (into-rf [])))
+  ([keyfn rf]
+   (fn group-by-rf-inner
+     ([] (transient {}))
+     ([x] (into {} (map (fn group-by-rf-finalize [[k v]] [k (rf v)])) (persistent! x)))
+     ([x y] (let [k (keyfn y)]
+              (if-let [old (get x k)]
+                (assoc! x k (rf old y))
+                (assoc! x k (rf (rf) y))))))))
+
+(def into-header
+  (-> (group-by-rf first ((map second) (into-rf [])))
+      (finalize-rf (fn [m] (if (some? (:HD m)) (update m :HD first) m)))))
+
+(defn parse-header
+  "Parse a header string, returning a map of the header."
+  [s]
+  (->> (cstr/split-lines s)
+       (transduce
+        (map parse-header-line)
+        into-header)))
+
+;;; stringify
+
+(defn- stringify-header-keyvalues [kv-map]
+  (cstr/join \tab
+             (map (fn [kv]
+                    (let [[k v] (seq kv)]
+                      (str (name k) \: v)))
+                  kv-map)))
+
+(defn stringify-header [hdr]
+  (cstr/join \newline
+             (map (fn [h]
+                    (let [[typ kvs] h]
+                      (if (= typ :HD)
+                        (str "@HD" \tab (stringify-header-keyvalues kvs))
+                        (cstr/join \newline
+                                   (map #(str \@ (name typ) \tab (stringify-header-keyvalues %)) kvs)))))
+                  (seq hdr))))
+
+;;; @HD
+
+(defn update-version
+  "Overwrites format version in SAM header."
+  [header]
+  (assoc-in header [:HD :VN] sam-common/sam-version))
+
+(def ^:const order-unknown :unknown)
+(def ^:const order-unsorted :unsorted)
+(def ^:const order-coordinate :coordinate)
+(def ^:const order-queryname :queryname)
+
+(defn sorted-by
+  "Replaces the sorting order field in SAM header."
+  [order header]
+  (assoc-in header [:HD :SO] (name order)))
+
+(defn sort-order
+  "Returns sorting order of the sam as Keyword. Returning order is one of the
+  following: :queryname, :coordinate, :unsorted, :unknown."
+  [header]
+  (or (keyword (:SO (:HD header))) order-unknown))
+
+(defn sorted?
+  "Returns true if the sam is sorted, false if not. It is detected by
+  `@HD SO:***` tag in the header."
+  [header]
+  (let [so (:SO (:HD header))]
+    (or (= so (name order-queryname))
+        (= so (name order-coordinate)))))
diff --git a/src/cljam/io/sam/util/option.clj b/src/cljam/io/sam/util/option.clj
new file mode 100644
index 0000000..519f478
--- /dev/null
+++ b/src/cljam/io/sam/util/option.clj
@@ -0,0 +1,152 @@
+(ns cljam.io.sam.util.option
+  "Utility functions for SAM optional fields."
+  (:require [clojure.string :as cstr]
+            [proton.core :as p]))
+
+;;; parse
+
+(defn- parse-tag-single [val-type val]
+  (case val-type
+    \Z val
+    \A (first val)
+    \I (p/as-long val)
+    \i (p/as-long val)
+    \s (p/as-long val)
+    \S (p/as-long val)
+    \c (p/as-long val)
+    \C (p/as-long val)
+    \f (p/as-double val)
+    \H (p/hex->bytes val)
+    (-> "Unrecognized tag type: %s, for value: %s"
+        (format val-type val)
+        Exception.
+        throw)))
+
+(defn parse-optional-field [op]
+  (let [[tag val-type-str val] (cstr/split op #":" 3)
+        val-type (first val-type-str)]
+    {(keyword tag) {:type val-type-str
+                    :value (if (= val-type \B)
+                             val
+                             (parse-tag-single val-type val))}}))
+
+;;; stringify
+
+(defn stringify-optional-fields [options]
+  (->> options
+       (map
+        (fn [op]
+          (let [[tag {:keys [type value]}] (first (seq op))]
+            (cstr/join \: [(name tag) type value]))))
+       (cstr/join \tab)))
+
+;;; accessors
+
+(defn value-for-tag
+  [tag aln]
+  (:value (some tag (:options aln))))
+
+(def
+  ^{:doc "CIGAR string of the mate alignment."
+    :arglists '([aln])}
+  mate-cigar
+  (partial value-for-tag :MC))
+
+(def
+  ^{:doc "Score of the alignment."
+    :arglists '([aln])}
+  score
+  (partial value-for-tag :AS))
+
+(def
+  ^{:doc "Barcode sequence."
+    :arglists '([aln])}
+  barcode
+  (partial value-for-tag :BC))
+
+(def
+  ^{:doc "Edit distance from reference of the alignment."
+    :arglists '([aln])}
+  edit-distance
+  (partial value-for-tag :NM))
+
+(defn parse-mismatching-positions-str
+  "Parse mismatching positions in the SAM optional fields. Returns a sequence
+  consisting of vectors which are one of [:match matching-length],
+  [:mismatch a-reference-base-char] and [:deletion reference-bases-string]."
+  [s]
+  (when s
+    (let [[_ head tail] (re-matches #"(\d+)(.*)" s)]
+      (->> (re-seq #"(([A-Z])|\^([A-Z]+))(\d+)" tail)
+           (mapcat
+            (fn [[_ _ mismatch deletion match]]
+              [(if mismatch
+                 [:mismatch (first mismatch)]
+                 [:deletion deletion])
+               [:match (p/as-long match)]]))
+           (cons [:match (p/as-long head)])))))
+
+(def
+  ^{:doc "Mismatching positions and bases of the alignment."
+    :arglists '([aln])}
+  mismatching-positions
+  (comp parse-mismatching-positions-str (partial value-for-tag :MD)))
+
+(def
+  ^{:doc "Ratio of the primary alignment score and the alternative one."
+    :arglists '([aln])}
+  primary-to-alt-score
+  (partial value-for-tag :pa))
+
+(defn parse-supplementary-alignments-str
+  "Parse serialized supplementary alignments."
+  [s]
+  (when s
+    (->> (re-seq #"(\S+?),(\d+),([+-]),((?:\d+[MIDSH])+),(\d+),(\d+);" s)
+         (map (fn [[_ & rests]]
+                (-> [:rname :pos :strand :cigar :mapq :edit-distance]
+                    (zipmap rests)
+                    (update :pos p/as-long)
+                    (update :mapq p/as-long)
+                    (update :strand first)
+                    (update :edit-distance p/as-long)))))))
+
+(def
+  ^{:doc "List of supplementary alignments."
+    :arglists '([aln])}
+  supplementary-alignments
+  (comp parse-supplementary-alignments-str (partial value-for-tag :SA)))
+
+(defn parse-alternative-hits-str
+  "Parse serialized supplementary alignments."
+  [s]
+  (when s
+    (->> (re-seq #"(\S+?),([+-]?\d+),((?:\d+[MIDSH])+),(\d+);" s)
+         (map (fn [[_ & rests]]
+                (-> (zipmap [:rname :pos :cigar :edit-distance] rests)
+                    (update :pos p/as-long)
+                    (update :edit-distance p/as-long)))))))
+
+(def
+  ^{:doc "List of alternative alignments."
+    :arglists '([aln])}
+  alternative-hits
+  (comp parse-alternative-hits-str (partial value-for-tag :XA)))
+
+(def
+  ^{:doc "Suboptimal alignment score."
+    :arglists '([aln])}
+  suboptimal-score
+  (partial value-for-tag :XS))
+
+(def
+  ^{:doc "Name of read group of the alignment."
+    :arglists '([aln])}
+  read-group
+  (partial value-for-tag :RG))
+
+(def
+  ^{:doc "Comment of reference sequence."
+    :arglists '([aln])}
+  ref-comment
+  (partial value-for-tag :XR))
diff --git a/src/cljam/io/sam/util/quality.clj b/src/cljam/io/sam/util/quality.clj
new file mode 100644
index 0000000..e19cdb4
--- /dev/null
+++ b/src/cljam/io/sam/util/quality.clj
@@ -0,0 +1,42 @@
+(ns cljam.io.sam.util.quality
+  "Utility functions for phred quality strings."
+  (:import [java.nio ByteBuffer CharBuffer]))
+
+(defmacro fastq-char->phred-byte [ch]
+  `(byte (- (int ~ch) 33)))
+
+(defmacro phred-byte->fastq-char [b]
+  `(unchecked-char (unchecked-add ~b 33)))
+
+(defn fastq->phred ^bytes [^String fastq]
+  (let [b (.getBytes fastq)
+        in-bb (ByteBuffer/wrap b)
+        out-bb (ByteBuffer/allocate (alength b))]
+    (while (.hasRemaining in-bb)
+      (.put out-bb (fastq-char->phred-byte (.get in-bb))))
+    (.array out-bb)))
+
+(defmulti phred->fastq class)
+
+(defn phred-bytes->fastq
+  [^bytes b]
+  (when-not (nil? b)
+    (let [bb (ByteBuffer/wrap b)
+          cb (CharBuffer/allocate (alength b))]
+      (loop []
+        (when (.hasRemaining bb)
+          (.put cb (phred-byte->fastq-char (.get bb)))
+          (recur)))
+      (.flip cb)
+      (.toString cb))))
+
+(defmethod phred->fastq (class (byte-array nil))
+  [^bytes b]
+  (phred-bytes->fastq b))
+
+(def ^:const max-phred-score 93)
+
+(defmethod phred->fastq Integer
+  [n]
+  {:pre [(<= 0 n max-phred-score)]}
+  (phred-byte->fastq-char n))
diff --git a/src/cljam/io/sam/util/refs.clj b/src/cljam/io/sam/util/refs.clj
new file mode 100644
index 0000000..d818980
--- /dev/null
+++ b/src/cljam/io/sam/util/refs.clj
@@ -0,0 +1,35 @@
+(ns cljam.io.sam.util.refs
+  "Utility functions for SAM references."
+  (:require [clojure.set :as cset]))
+
+(defn make-refs
+  "Return a reference sequence from the sam header."
+  [hdr]
+  (map
+   #(cset/rename-keys
+     %
+     {:SN :name, :LN :len, :AH :alt, :AS :assembly,
+      :M5 :md5, :SP :species, :UR :uri})
+   (:SQ hdr)))
+
+(defn- ref-id*
+  [refs name]
+  (some #(when (= name (:name (second %))) (first %))
+        (map-indexed vector refs)))
+
+(def ref-id
+  "Returns reference ID from the reference sequence and the specified reference
+  name. If not found, returns nil."
+  (memoize ref-id*))
+
+(defn ref-name
+  "Returns a reference name from the reference ID. Returns nil if id is not
+  mapped."
+  [refs ^long id]
+  (when (<= 0 id (dec (count refs)))
+    (:name (nth refs id))))
+
+(defn ref-by-name
+  "Returns the first reference which has the specified name."
+  [refs name]
+  (some #(if (= (:name %) name) %) refs))
diff --git a/src/cljam/io/sam/util/sequence.clj b/src/cljam/io/sam/util/sequence.clj
new file mode 100644
index 0000000..b28c021
--- /dev/null
+++ b/src/cljam/io/sam/util/sequence.clj
@@ -0,0 +1,76 @@
+(ns cljam.io.sam.util.sequence
+  "Utility functions for base sequences."
+  (:require [clojure.string :as cstr])
+  (:import [java.nio ByteBuffer CharBuffer]))
+
+(def ^:private ^:const nibble-to-base-table
+  ;; Index: nibble of a compressed base.
+  ;; Value: base for the nibble.
+  "=ACMGRSVTWYHKDBN")
+
+(def ^:private two-bytes-to-compressed-bases-table
+  ;; Index: two bases (A,C) => ASCII (65,67) => 2r 1000001 1000011 => 8387
+  ;; Value: two bases (A,C) => nibbles (1,2) => 2r 0001 0010 => 18
+  (let [ba (byte-array (bit-shift-left 1 14))
+        byte-to-nibble-table (byte-array (bit-shift-left 1 7) (byte 15))]
+    (doseq [[i c] (map vector (range) nibble-to-base-table)]
+      (aset-byte byte-to-nibble-table (int c) i)
+      (aset-byte byte-to-nibble-table (int (.charAt (cstr/lower-case c) 0)) i))
+    (dotimes [i (alength ba)]
+      (let [u (unchecked-byte (bit-and 0x7F (unsigned-bit-shift-right i 7)))
+            l (unchecked-byte (bit-and 0x7F i))]
+        (->> (aget byte-to-nibble-table l)
+             (bit-or (bit-shift-left (aget byte-to-nibble-table u) 4))
+             unchecked-byte
+             (aset-byte ba i))))
+    ba))
+
+(defn str->compressed-bases
+  "Creates a buffer consists of compressed bases from ASCII sequence."
+  ^bytes [^String s]
+  (let [b (.getBytes s)
+        length (alength b)
+        result-len (quot (inc length) 2)
+        in-bb (ByteBuffer/wrap b)
+        out-bb (ByteBuffer/allocate result-len)]
+    (dotimes [i result-len]
+      (let [u (.get in-bb)
+            l (byte (if (.hasRemaining in-bb) (.get in-bb) \=))]
+        (->> (bit-and 0x7F l)
+             (bit-or (bit-shift-left (bit-and 0x7F u) 7))
+             (aget ^bytes two-bytes-to-compressed-bases-table)
+             (.put out-bb))))
+    (.array out-bb)))
+
+(def ^:const ^:private compressed-bases-to-bases-table
+  ;; Index: compressed base n containing two nibbles => 2n
+  ;; Value 2n+0: base for upper nibble of n.
+  ;; Value 2n+1: base for lower nibble of n.
+  (->> (for [i nibble-to-base-table j nibble-to-base-table] [i j])
+       (apply concat)
+       cstr/join))
+
+(defn compressed-bases->str
+  "Decode a sequence from byte array to String."
+  [^long length ^bytes compressed-bases ^long compressed-offset]
+  (let [cb (CharBuffer/allocate (inc length))
+        bb (ByteBuffer/wrap compressed-bases)]
+    (.position bb compressed-offset)
+    (dotimes [_ (quot (inc length) 2)]
+      (let [i (-> (.get bb) (bit-and 0xff) (* 2))]
+        (.put cb (.charAt compressed-bases-to-bases-table i))
+        (.put cb (.charAt compressed-bases-to-bases-table (inc i)))))
+    (.limit cb length)
+    (.flip cb)
+    (.toString cb)))
+
+(defn normalize-bases
+  "Converts bases in given buffer to upper-case. Also converts '.' to 'N'.
+   Bases are represented as buffer of ASCII characters."
+  ^bytes [^bytes bases]
+  (dotimes [i (alength bases)]
+    (let [b (aget bases i)]
+      (cond
+        (= b (byte \.)) (aset-byte bases i (byte \N))
+        (<= (byte \a) b (byte \z)) (aset-byte bases i (- b 32))))) ;; Upper-case ASCII offset
+  bases)
diff --git a/src/cljam/io/sam/writer.clj b/src/cljam/io/sam/writer.clj
index ccb2834..40a27be 100644
--- a/src/cljam/io/sam/writer.clj
+++ b/src/cljam/io/sam/writer.clj
@@ -2,8 +2,8 @@
   "Provides writing features."
   (:require [clojure.java.io :as cio]
             [clojure.tools.logging :as logging]
-            [cljam.io.sam.util :refer [stringify-header
-                                       stringify-alignment]]
+            [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.header :as header]
             [cljam.io.protocols :as protocols])
   (:import [java.io BufferedWriter Closeable]))
 
@@ -35,14 +35,14 @@
 (defn- write-header*
   [^SAMWriter sam-writer header]
   (let [wtr ^BufferedWriter (.writer sam-writer)]
-    (.write wtr ^String (stringify-header header))
+    (.write wtr ^String (header/stringify-header header))
     (.newLine wtr)))
 
 (defn- write-alignments*
-  [^SAMWriter sam-writer alns refs]
+  [^SAMWriter sam-writer alns _]
   (let [wtr ^BufferedWriter (.writer sam-writer)]
    (doseq [a alns]
-     (.write wtr ^String (stringify-alignment a))
+     (.write wtr ^String (sam-util/stringify-alignment a))
      (.newLine wtr))))
 
 (defn- write-blocks*
diff --git a/src/cljam/tools/cli.clj b/src/cljam/tools/cli.clj
index f41ac05..4a723e4 100644
--- a/src/cljam/tools/cli.clj
+++ b/src/cljam/tools/cli.clj
@@ -6,6 +6,7 @@
             [clojure.tools.cli :refer [parse-opts]]
             [cljam.io.sam :as sam]
             [cljam.io.sam.util :as sam-util]
+            [cljam.io.sam.util.header :as header]
             [cljam.io.sequence :as cseq]
             [cljam.algo.bam-indexer :as bai]
             [cljam.algo.normal :as normal]
@@ -68,7 +69,7 @@
                                  "sam"  (sam/sam-reader f)
                                  "bam"  (sam/bam-reader f))]
         (when (:header options)
-          (println (sam-util/stringify-header (sam/read-header r))))
+          (println (header/stringify-header (sam/read-header r))))
         (doseq [aln (if (:region options)
                       (if-let [region (region/parse-region (:region options))]
                         (if (sam/indexed? r)
@@ -161,8 +162,8 @@
       (with-open [r (sam/reader in)
                   w (sam/writer out)]
         (condp = (:order options)
-          (name sorter/order-coordinate) (sorter/sort-by-pos r w {:chunk-size (:chunk options)})
-          (name sorter/order-queryname) (sorter/sort-by-qname r w {:chunk-size (:chunk options)})))))
+          (name header/order-coordinate) (sorter/sort-by-pos r w {:chunk-size (:chunk options)})
+          (name header/order-queryname) (sorter/sort-by-qname r w {:chunk-size (:chunk options)})))))
   nil)
 
 ;; ### index command
@@ -270,7 +271,7 @@
       (with-open [r (sam/reader f)]
         (when (= (type r) cljam.io.sam.reader.SAMReader)
           (exit 1 "Not support SAM file"))
-        (when-not (sorter/sorted-by? r)
+        (when-not (sorter/sorted? r)
           (exit 1 "Not sorted"))
         (if (:region options)
           (if-let [region (region/parse-region (:region options))]
diff --git a/src/cljam/util/sequence.clj b/src/cljam/util/sequence.clj
new file mode 100644
index 0000000..5ee489c
--- /dev/null
+++ b/src/cljam/util/sequence.clj
@@ -0,0 +1,28 @@
+(ns cljam.util.sequence
+  (:require [clojure.string :as cstr])
+  (:import [java.nio CharBuffer]))
+
+(def ^:private revcomp-table
+  (let [ba (byte-array 128)]
+    (dotimes [i 128] (aset-byte ba i (byte \N)))
+    (doseq [s ["AT" "GC" "NN"]
+            [a b] [(cstr/upper-case s) (cstr/lower-case s)]]
+      (aset-byte ba (int a) (byte b))
+      (aset-byte ba (int b) (byte a)))
+    ba))
+
+(defn revcomp
+  "Returns a reverse-complement sequence of given sequence. All characters other
+  than ATGCNatgcn will be replaced with N. Masks will be kept."
+  [^String s]
+  (let [l (.length s)
+        cb (CharBuffer/allocate l)]
+    (dotimes [i l]
+      (->> (unchecked-dec (- l i))
+           (.charAt s)
+           unchecked-int
+           (aget ^bytes revcomp-table)
+           unchecked-char
+           (.put cb)))
+    (.flip cb)
+    (.toString cb)))


Test patch:
diff --git a/test/cljam/algo/sorter_test.clj b/test/cljam/algo/sorter_test.clj
index 169444f..fe83a8d 100644
--- a/test/cljam/algo/sorter_test.clj
+++ b/test/cljam/algo/sorter_test.clj
@@ -2,7 +2,8 @@
   (:require [clojure.test :refer :all]
             [cljam.test-common :refer :all]
             [cljam.io.sam :as sam]
-            [cljam.algo.sorter :as sorter])
+            [cljam.algo.sorter :as sorter]
+            [cljam.io.sam.util.header :as header])
   (:import [java.io Closeable]))
 
 (use-fixtures :once disable-log-fixture)
@@ -47,24 +48,24 @@
     (is (not-throw? (with-reader sorter/sort-by-pos test-bam-file tmp-coordinate-sorted-bam-file)))
     (is (not-throw? (with-reader sorter/sort-by-qname test-sam-file tmp-queryname-sorted-sam-file)))
     (is (not-throw? (with-reader sorter/sort-by-qname test-bam-file tmp-queryname-sorted-bam-file)))
-    (is (not (with-reader sorter/sorted-by? test-sam-file)))
-    (is (not (with-reader sorter/sorted-by? test-bam-file)))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-bam-file))
+    (is (not (with-reader sorter/sorted? test-sam-file)))
+    (is (not (with-reader sorter/sorted? test-bam-file)))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-sam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-sam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-bam-file))
     (is (= (with-reader sorter/sort-order test-sam-file)
-           sorter/order-unknown))
+           header/order-unknown))
     (is (= (with-reader sorter/sort-order test-bam-file)
-           sorter/order-unknown))
+           header/order-unknown))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-sam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-queryname-sorted-sam-file)
-           sorter/order-queryname))
+           header/order-queryname))
     (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file)
-           sorter/order-queryname))
+           header/order-queryname))
     (is (qname-sorted? tmp-queryname-sorted-sam-file))
     (is (qname-sorted? tmp-queryname-sorted-bam-file))))
 
@@ -79,30 +80,30 @@
     (is (not-throw? (with-reader sorter/sort-by-pos tmp-shuffled-bam-file tmp-coordinate-sorted-bam-bam-file)))
     (is (not-throw? (with-reader sorter/sort-by-qname tmp-shuffled-sam-file tmp-queryname-sorted-sam-file-2)))
     (is (not-throw? (with-reader sorter/sort-by-qname tmp-shuffled-bam-file tmp-queryname-sorted-bam-file-2)))
-    (is (not (with-reader sorter/sorted-by? tmp-shuffled-sam-file)))
-    (is (not (with-reader sorter/sorted-by? tmp-shuffled-bam-file)))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-sam-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-sam-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-sam-file-2))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-bam-file-2))
+    (is (not (with-reader sorter/sorted? tmp-shuffled-sam-file)))
+    (is (not (with-reader sorter/sorted? tmp-shuffled-bam-file)))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-sam-sam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-sam-bam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-sam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-bam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-sam-file-2))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-bam-file-2))
     (is (get #{:queryname :coordinate :unsorted :unknown}
              (with-reader sorter/sort-order tmp-shuffled-sam-file)))
     (is (get #{:queryname :coordinate :unsorted :unknown}
              (with-reader sorter/sort-order tmp-shuffled-bam-file)))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-sam-sam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-sam-bam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-sam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-bam-file)
-           sorter/order-coordinate))
+           header/order-coordinate))
     (is (= (with-reader sorter/sort-order tmp-queryname-sorted-sam-file-2)
-           sorter/order-queryname))
+           header/order-queryname))
     (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file-2)
-           sorter/order-queryname))
+           header/order-queryname))
     ;; check sorting order
     (is (not-throw? (check-sort-order (slurp-sam-for-test tmp-coordinate-sorted-sam-sam-file))))
     (is (not-throw? (check-sort-order (slurp-sam-for-test tmp-coordinate-sorted-bam-sam-file))))
@@ -131,7 +132,7 @@
          (with-open [r (sam/reader tmp-shuffled-bam-file)
                      w (sam/writer tmp-coordinate-sorted-bam-bam-file)]
            (sorter/sort-by-pos r w {:chunk-size 3}))))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-bam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-bam-file))
     (is (not-throw? (check-sort-order (slurp-bam-for-test tmp-coordinate-sorted-bam-bam-file))))
     (is (coord-sorted? tmp-coordinate-sorted-bam-bam-file))
 
@@ -139,7 +140,7 @@
          (with-open [r (sam/reader tmp-shuffled-sam-file)
                      w (sam/writer tmp-coordinate-sorted-sam-sam-file)]
            (sorter/sort-by-pos r w {:chunk-size 3 :cache-fmt :sam}))))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-sam-sam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-sam-sam-file))
     (is (not-throw? (check-sort-order (slurp-sam-for-test tmp-coordinate-sorted-sam-sam-file))))
     (is (coord-sorted? tmp-coordinate-sorted-sam-sam-file))
 
@@ -148,14 +149,14 @@
          (with-open [r (sam/reader tmp-shuffled-bam-file)
                      w (sam/writer tmp-queryname-sorted-bam-file-2)]
            (sorter/sort-by-qname r w {:chunk-size 3}))))
-    (with-reader sorter/sorted-by? tmp-queryname-sorted-bam-file-2)
+    (with-reader sorter/sorted? tmp-queryname-sorted-bam-file-2)
     (is (qname-sorted? tmp-queryname-sorted-bam-file-2))
 
     (is (not-throw?
          (with-open [r (sam/reader tmp-shuffled-bam-file)
                      w (sam/writer tmp-queryname-sorted-sam-file-2)]
            (sorter/sort-by-qname r w {:chunk-size 3 :cache-fmt :sam}))))
-    (with-reader sorter/sorted-by? tmp-queryname-sorted-sam-file-2)
+    (with-reader sorter/sorted? tmp-queryname-sorted-sam-file-2)
     (is (qname-sorted? tmp-queryname-sorted-sam-file-2))))
 
 (deftest-slow about-sorting-medium-file
@@ -165,16 +166,16 @@
     (is (not-throw? (with-reader sorter/sort-by-pos medium-bam-file tmp-coordinate-sorted-bam-file)))
     (is (not-throw? (with-reader sorter/sort-by-qname medium-bam-file tmp-queryname-sorted-sam-file)))
     (is (not-throw? (with-reader sorter/sort-by-qname medium-bam-file tmp-queryname-sorted-bam-file)))
-    (is (not (with-reader sorter/sorted-by? medium-bam-file)))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-sam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-bam-file))
-    (is (= (with-reader sorter/sort-order medium-bam-file) sorter/order-unknown))
-    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-sam-file) sorter/order-coordinate))
-    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-file) sorter/order-coordinate))
-    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-sam-file) sorter/order-queryname))
-    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file) sorter/order-queryname))
+    (is (not (with-reader sorter/sorted? medium-bam-file)))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-sam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-sam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-bam-file))
+    (is (= (with-reader sorter/sort-order medium-bam-file) header/order-unknown))
+    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-sam-file) header/order-coordinate))
+    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-file) header/order-coordinate))
+    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-sam-file) header/order-queryname))
+    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file) header/order-queryname))
     ;; check sorting order
     (is (not-throw? (check-sort-order (slurp-sam-for-test tmp-coordinate-sorted-sam-file))))
     (is (not-throw? (check-sort-order (slurp-bam-for-test tmp-coordinate-sorted-bam-file))))
@@ -197,12 +198,12 @@
                      w (sam/writer tmp-queryname-sorted-bam-file)]
            ;; Use small chunk size to avoid OOM
            (sorter/sort-by-qname r w {:chunk-size 100000}))))
-    (is (with-reader sorter/sorted-by? large-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-coordinate-sorted-bam-file))
-    (is (with-reader sorter/sorted-by? tmp-queryname-sorted-bam-file))
-    (is (= (with-reader sorter/sort-order large-bam-file) sorter/order-coordinate))
-    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-file) sorter/order-coordinate))
-    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file) sorter/order-queryname))
+    (is (with-reader sorter/sorted? large-bam-file))
+    (is (with-reader sorter/sorted? tmp-coordinate-sorted-bam-file))
+    (is (with-reader sorter/sorted? tmp-queryname-sorted-bam-file))
+    (is (= (with-reader sorter/sort-order large-bam-file) header/order-coordinate))
+    (is (= (with-reader sorter/sort-order tmp-coordinate-sorted-bam-file) header/order-coordinate))
+    (is (= (with-reader sorter/sort-order tmp-queryname-sorted-bam-file) header/order-queryname))
     ;; check sorting order
     (is (coord-sorted? tmp-coordinate-sorted-bam-file))
     (is (qname-sorted? tmp-queryname-sorted-bam-file))))
diff --git a/test/cljam/io/util/cigar_test.clj b/test/cljam/io/sam/util/cigar_test.clj
similarity index 92%
rename from test/cljam/io/util/cigar_test.clj
rename to test/cljam/io/sam/util/cigar_test.clj
index 42c94f2..34dd987 100644
--- a/test/cljam/io/util/cigar_test.clj
+++ b/test/cljam/io/sam/util/cigar_test.clj
@@ -1,12 +1,12 @@
-(ns cljam.io.util.cigar-test
+(ns cljam.io.sam.util.cigar-test
   (:require [clojure.test :refer :all]
-            [cljam.io.util.cigar :as cgr]))
+            [cljam.io.sam.util.cigar :as cigar]))
 
 (deftest about-parse
-  (is (= (cgr/parse  "1S2I6M1P11I") '([1 \S] [2 \I] [6 \M] [1 \P] [11 \I]))))
+  (is (= (cigar/parse  "1S2I6M1P11I") '([1 \S] [2 \I] [6 \M] [1 \P] [11 \I]))))
 
 (deftest cigar-to-index
-  (are [?cigar ?index] (= (map (fn [[op x :as xs]] (if (= op :m) x xs)) (cgr/to-index* ?cigar)) ?index)
+  (are [?cigar ?index] (= (map (fn [[op x :as xs]] (if (= op :m) x xs)) (cigar/to-index* ?cigar)) ?index)
     "4M"                 [0 1 2 3]
     "1M3I"               [[:i 0 [1 2 3]]]
     "1M3D"               [[:d 0 [1 2 3]] \* \* \*]
diff --git a/test/cljam/io/sam/util/flag_test.clj b/test/cljam/io/sam/util/flag_test.clj
new file mode 100644
index 0000000..5ed0d26
--- /dev/null
+++ b/test/cljam/io/sam/util/flag_test.clj
@@ -0,0 +1,96 @@
+(ns cljam.io.sam.util.flag-test
+  (:require [clojure.test :refer :all]
+            [cljam.io.sam.util.flag :as flag]))
+
+(deftest flags
+  (are [?flag ?primary ?set] (and (= (flag/decode ?flag) ?set)
+                                  (= (flag/encode ?set) ?flag)
+                                  (= (flag/primary? ?flag) ?primary))
+    0     true  #{}
+    1     true  #{:multiple}
+    2     true  #{:properly-aligned}
+    3     true  #{:multiple :properly-aligned}
+    4     true  #{:unmapped}
+    16    true  #{:reversed}
+    83    true  #{:multiple :properly-aligned :reversed :first}
+    163   true  #{:multiple :properly-aligned :next-reversed :last}
+    99    true  #{:multiple :properly-aligned :next-reversed :first}
+    147   true  #{:multiple :properly-aligned :reversed :last}
+    121   true  #{:multiple :next-unmapped :reversed :next-reversed :first}
+    181   true  #{:multiple :unmapped :reversed :next-reversed :last}
+    77    true  #{:multiple :unmapped :next-unmapped :first}
+    141   true  #{:multiple :unmapped :next-unmapped :last}
+    256   false #{:secondary}
+    257   false #{:multiple :secondary}
+    2048  false #{:supplementary}
+    2049  false #{:multiple :supplementary}
+    2304  false #{:secondary :supplementary}
+    0x900 false #{:secondary :supplementary}))
+
+(deftest flag-tests
+  (testing "multiple?"
+    (are [?flag]
+        (= (flag/multiple? ?flag) false)
+      0 4)
+    (are [?flag]
+        (= (flag/multiple? ?flag) true)
+      67 79 83 99 147 403 355))
+  (testing "properly-aligned?"
+    (are [?flag]
+        (= (flag/properly-aligned? ?flag) false)
+      0 4)
+    (are [?flag]
+        (= (flag/properly-aligned? ?flag) true)
+      67 79 83 99 147 403 355))
+  (testing "unmapped?"
+    (are [?flag]
+        (= (flag/unmapped? ?flag) false)
+      0 67 83 99 147 403 355)
+    (are [?flag]
+        (= (flag/unmapped? ?flag) true)
+      4 79))
+  (testing "both-unmapped?"
+    (are [?flag]
+        (= (flag/both-unmapped? ?flag) false)
+      0 4 67 83 99 147 403 355)
+    (are [?flag]
+        (= (flag/both-unmapped? ?flag) true)
+      79))
+  (testing "reversed?"
+    (are [?flag]
+        (= (flag/reversed? ?flag) false)
+      0 4 67 79 99 355)
+    (are [?flag]
+        (= (flag/reversed? ?flag) true)
+      16 83 147 403))
+  (testing "r1?"
+    (are [?flag]
+        (= (flag/r1? ?flag) false)
+      0 4 16 147 403)
+    (are [?flag]
+        (= (flag/r1? ?flag) true)
+      67 79 83 99 355))
+  (testing "r2?"
+    (are [?flag]
+        (= (flag/r2? ?flag) false)
+      0 4 16 67 79 83 99 355)
+    (are [?flag]
+        (= (flag/r2? ?flag) true)
+      147 403))
+  (testing "r1r2"
+    (are [?flag]
+        (= (flag/r1r2 ?flag) 0)
+      0 4 16)
+    (are [?flag]
+        (= (flag/r1r2 ?flag) 1)
+      67 79 83 99 355)
+    (are [?flag]
+        (= (flag/r1r2 ?flag) 2)
+      147 403))
+  (testing "secondary?"
+    (are [?flag]
+        (= (flag/secondary? ?flag) false)
+      0 4 16 67 79 83 99 147)
+    (are [?flag]
+        (= (flag/secondary? ?flag) true)
+      403 355)))
diff --git a/test/cljam/io/sam/util/header_test.clj b/test/cljam/io/sam/util/header_test.clj
new file mode 100644
index 0000000..50d72ae
--- /dev/null
+++ b/test/cljam/io/sam/util/header_test.clj
@@ -0,0 +1,30 @@
+(ns cljam.io.sam.util.header-test
+  (:require [clojure.test :refer :all]
+            [cljam.io.sam.util.header :as header]))
+
+(deftest into-rf
+  (let [rf-vec (#'header/into-rf [])
+        rf-seq (#'header/into-rf nil)]
+    (is (= (-> (rf-vec)
+               (rf-vec \a)
+               (rf-vec \b)
+               (rf-vec \c)
+               (rf-vec))
+           [\a \b \c]))
+    (is (= (-> (rf-seq)
+               (rf-seq \a)
+               (rf-seq \b)
+               (rf-seq \c)
+               (rf-seq))
+           '(\c \b \a)))))
+
+(deftest about-parse-header
+  (is (= (header/parse-header "@HD	VN:1.3	SO:coordinate\n@SQ	SN:ref	LN:10\n@SQ	SN:ref2	LN:20\n@PG	ID:cljam	PN:cljam	VN:1.0	CL:java -jar cljam.jar")
+         {:HD {:VN "1.3" :SO "coordinate"}
+          :SQ [{:SN "ref" :LN 10} {:SN "ref2" :LN 20}]
+          :PG [{:ID "cljam" :PN "cljam" :VN "1.0" :CL "java -jar cljam.jar"}]}))
+  (is (= (header/parse-header "@HD\tVN:1.4\tSO:coordinate\n@SQ\tSN:FOO:BAR:10-100;BAZ|QUX,QUUX\tLN:1\n@PG\tID:cljam\tPN:cljam\tVN:1.0\tCL:cljam")
+         {:HD {:VN "1.4" :SO "coordinate"}
+          :SQ [{:SN "FOO:BAR:10-100;BAZ|QUX,QUUX"
+                :LN 1}]
+          :PG [{:ID "cljam" :PN "cljam" :VN "1.0" :CL "cljam"}]})))
diff --git a/test/cljam/io/sam/util/option_test.clj b/test/cljam/io/sam/util/option_test.clj
new file mode 100644
index 0000000..83260ae
--- /dev/null
+++ b/test/cljam/io/sam/util/option_test.clj
@@ -0,0 +1,68 @@
+(ns cljam.io.sam.util.option-test
+  (:require [clojure.test :refer :all]
+            [cljam.io.sam.util.option :as opt]))
+
+(deftest parse-optional-field
+  (testing "regression"
+    (are [?str ?expect]
+        (and (= (opt/parse-optional-field ?str) ?expect)
+             (= (opt/stringify-optional-fields [?expect]) ?str))
+      "AS:i:0" {:AS {:type "i" :value 0}}
+      "BC:Z:CGTAC" {:BC {:type "Z" :value "CGTAC"}}
+      "pa:f:0.987" {:pa {:type "f" :value 0.987}}
+      "XX:A:A" {:XX {:type "A" :value \A}}
+      "ZZ:B:i,1,2,3" {:ZZ {:type "B" :value "i,1,2,3"}}))
+  (testing "hex"
+    (is (= (update-in (opt/parse-optional-field "YY:H:1AE301") [:YY :value] seq)
+           {:YY {:type "H" :value (map unchecked-byte [0x1A 0xE3 0x1])}}))))
+
+(deftest stringify-optional-fields
+  (is (= (opt/stringify-optional-fields [])
+         ""))
+  (is (= (opt/stringify-optional-fields [{:AS {:type "i" :value 0}} {:BC {:type "Z" :value "AAT"}}])
+         "AS:i:0\tBC:Z:AAT")))
+
+(deftest optional-fields
+  (let [s ["NM:i:4"
+           "MD:Z:103"
+           "MC:Z:2S13M"
+           "AS:i:103"
+           "XS:i:103"
+           "RG:Z:ReadGroup01"
+           "BC:Z:CGTAC"
+           "SA:Z:chr1,550,+,70S50M,0,4;chr1,550,-,40S30M50S,0,0;"
+           "pa:f:0.987"
+           "XA:Z:chr18,-80000000,10S90M10D20M10D10M,6;chr1,-240000000,10M10D70M10I10M10I10M10I10M,7;"
+           "XR:Z:Reference Comment"]
+        aln {:options (map opt/parse-optional-field s)}]
+    (is (= (opt/score aln) 103))
+    (is (= (opt/edit-distance aln) 4))
+    (is (= (opt/mismatching-positions aln) [[:match 103]]))
+    (is (= (opt/mate-cigar aln) "2S13M"))
+    (is (= (opt/suboptimal-score aln) 103))
+    (is (= (opt/read-group aln) "ReadGroup01"))
+    (is (= (opt/barcode aln) "CGTAC"))
+    (is (= (opt/supplementary-alignments aln)
+           [{:rname "chr1", :pos 550, :strand \+,
+             :cigar "70S50M", :mapq 0, :edit-distance 4}
+            {:rname "chr1", :pos 550, :strand \-,
+             :cigar "40S30M50S", :mapq 0, :edit-distance 0}]))
+    (is (= (opt/primary-to-alt-score aln) 0.987))
+    (is (= (opt/alternative-hits aln)
+           [{:rname "chr18", :pos -80000000, :cigar "10S90M10D20M10D10M", :edit-distance 6}
+            {:rname "chr1", :pos -240000000, :cigar "10M10D70M10I10M10I10M10I10M", :edit-distance 7}]))
+    (is (= (opt/ref-comment aln) "Reference Comment"))))
+
+(deftest md-string
+  (are [?str ?expect]
+      (= (opt/parse-mismatching-positions-str ?str) ?expect)
+    "100"
+    [[:match 100]]
+    "132T0"
+    [[:match 132] [:mismatch \T] [:match 0]]
+    "10A5^AC6"
+    [[:match 10] [:mismatch \A] [:match 5] [:deletion "AC"] [:match 6]]
+    "30C5C35C20"
+    [[:match 30] [:mismatch \C] [:match 5] [:mismatch \C] [:match 35] [:mismatch \C] [:match 20]]
+    "55^CTAACCCTAA63T8A2"
+    [[:match 55] [:deletion "CTAACCCTAA"] [:match 63] [:mismatch \T] [:match 8] [:mismatch \A] [:match 2]]))
diff --git a/test/cljam/io/sam/util/refs_test.clj b/test/cljam/io/sam/util/refs_test.clj
new file mode 100644
index 0000000..5c29566
--- /dev/null
+++ b/test/cljam/io/sam/util/refs_test.clj
@@ -0,0 +1,30 @@
+(ns cljam.io.sam.util.refs-test
+  (:require [clojure.test :refer :all]
+            [cljam.test-common :refer :all]
+            [cljam.io.sam.util.refs :as refs]))
+
+;; Reference functions
+;; -------------------
+
+(def refs '({:name "ref", :len 45} {:name "ref2", :len 40}))
+
+(deftest make-refs
+  (is (= (refs/make-refs (:header test-sam)) refs)))
+
+(deftest ref-id
+  (are [?name ?expected] (= (refs/ref-id refs ?name) ?expected)
+    "ref"      0
+    "ref2"     1
+    "notfound" nil))
+
+(deftest ref-name
+  (are [?id ?expected] (= (refs/ref-name refs ?id) ?expected)
+    0 "ref"
+    1 "ref2"
+    9 nil))
+
+(deftest ref-by-name
+  (are [?name ?expected] (= (refs/ref-by-name refs ?name) ?expected)
+    "ref"      {:name "ref", :len 45}
+    "ref2"     {:name "ref2", :len 40}
+    "notfound" nil))
diff --git a/test/cljam/io/sam/util/sequence_test.clj b/test/cljam/io/sam/util/sequence_test.clj
new file mode 100644
index 0000000..62c3c85
--- /dev/null
+++ b/test/cljam/io/sam/util/sequence_test.clj
@@ -0,0 +1,68 @@
+(ns cljam.io.sam.util.sequence-test
+  (:require [clojure.test :refer :all]
+            [clojure.string :as cstr]
+            [cljam.io.sam.util.sequence :as sam-seq]
+            [cljam.util :as util]))
+
+(def nibble-table "=ACMGRSVTWYHKDBN")
+
+(defn encode [^String s]
+  (->> (concat s [\=])
+       (partition 2)
+       (map (fn [[u l]]
+              (let [ui (.indexOf ^String nibble-table (cstr/upper-case u))
+                    li (.indexOf ^String nibble-table (cstr/upper-case l))
+                    uu (if-not (neg? ui) ui 15)
+                    ll (if-not (neg? li) li 15)]
+                (unchecked-byte (bit-or (bit-shift-left uu 4) (bit-and 0xff ll))))))))
+
+(deftest str->compressed-bases-1
+  (are [?str ?expected] (and (= (map #(bit-and 0xff %)
+                                     (sam-seq/str->compressed-bases ?str))
+                                ?expected)
+                             (= (map #(bit-and 0xff %)
+                                     (sam-seq/str->compressed-bases ?str))
+                                (map #(bit-and 0xff %) (encode ?str)))
+                             (= (map #(bit-and 0xff %)
+                                     (sam-seq/str->compressed-bases (cstr/lower-case ?str)))
+                                ?expected))
+    "="    [0]
+    "=A"   [1]
+    "=C"   [2]
+    "=G"   [4]
+    "=T"   [8]
+    "=."   [15]
+    "A"    [16]
+    "C"    [32]
+    "G"    [64]
+    "T"    [128]
+    "."    [240]
+    "==A"  [0 16]
+    "===A" [0 1]))
+
+(deftest str->compressed-bases-2
+ (dotimes [_ 100]
+   (let [s (apply str (repeatedly (inc (rand-int 100)) #(rand-nth nibble-table)))]
+     (is (= (seq (sam-seq/str->compressed-bases s)) (encode s))))))
+
+(deftest compressed-bases->str
+  (are [?length ?bases ?offset ?expected] (= (sam-seq/compressed-bases->str ?length (byte-array (mapv util/ubyte ?bases)) ?offset)
+                                             ?expected)
+    1   [0x00]                                    0 "="
+    2   [0x00]                                    0 "=="
+    1   [0x10]                                    0 "A"
+    2   [0x12]                                    0 "AC"
+    4   [0x12 0x8F]                               0 "ACTN"
+    1   [0x12 0x8F]                               1 "T"
+    2   [0x12 0x8F]                               1 "TN"
+    16  [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 0 nibble-table
+    14  [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 1 (subs nibble-table 2)
+    2   [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 7 "BN"
+    512 (range 256)                               0 (->> (for [i nibble-table j nibble-table] [i j])
+                                                         (apply concat)
+                                                         cstr/join)))
+
+(deftest normalize-bases
+  (are [?src ?result] (= (vec (sam-seq/normalize-bases (byte-array (map byte ?src))))
+                         (map byte ?result))
+    [\a \b \c \. \d \e \n \N] [\A \B \C \N \D \E \N \N]))
diff --git a/test/cljam/io/sam/util_test.clj b/test/cljam/io/sam/util_test.clj
deleted file mode 100644
index 908073d..0000000
--- a/test/cljam/io/sam/util_test.clj
+++ /dev/null
@@ -1,149 +0,0 @@
-(ns cljam.io.sam.util-test
-  "Tests for cljam.io.sam.util."
-  (:require [clojure.test :refer :all]
-            [clojure.string :as cstr]
-            [cljam.test-common :refer :all]
-            [cljam.util :as util]
-            [cljam.io.sam.util :as sam-util]))
-
-(deftest about-parse-header
-  (is (= (sam-util/parse-header "@HD	VN:1.3	SO:coordinate\n@SQ	SN:ref	LN:10\n@SQ	SN:ref2	LN:20\n@PG	ID:cljam	PN:cljam	VN:1.0	CL:java -jar cljam.jar")
-         {:HD {:VN "1.3" :SO "coordinate"}
-          :SQ [{:SN "ref" :LN 10} {:SN "ref2" :LN 20}]
-          :PG [{:ID "cljam" :PN "cljam" :VN "1.0" :CL "java -jar cljam.jar"}]}))
-  (is (= (sam-util/parse-header "@HD\tVN:1.4\tSO:coordinate\n@SQ\tSN:FOO:BAR:10-100;BAZ|QUX,QUUX\tLN:1\n@PG\tID:cljam\tPN:cljam\tVN:1.0\tCL:cljam")
-         {:HD {:VN "1.4" :SO "coordinate"}
-          :SQ [{:SN "FOO:BAR:10-100;BAZ|QUX,QUUX"
-                :LN 1}]
-          :PG [{:ID "cljam" :PN "cljam" :VN "1.0" :CL "cljam"}]})))
-
-(def nibble-table "=ACMGRSVTWYHKDBN")
-
-(defn encode [^String s]
-  (->> (concat s [\=])
-       (partition 2)
-       (map (fn [[u l]]
-              (let [ui (.indexOf ^String nibble-table (cstr/upper-case u))
-                    li (.indexOf ^String nibble-table (cstr/upper-case l))
-                    uu (if-not (neg? ui) ui 15)
-                    ll (if-not (neg? li) li 15)]
-                (unchecked-byte (bit-or (bit-shift-left uu 4) (bit-and 0xff ll))))))))
-
-(deftest str->compressed-bases-1
-  (are [?str ?expected] (and (= (map #(bit-and 0xff %)
-                                     (sam-util/str->compressed-bases ?str))
-                                ?expected)
-                             (= (map #(bit-and 0xff %)
-                                     (sam-util/str->compressed-bases ?str))
-                                (map #(bit-and 0xff %) (encode ?str)))
-                             (= (map #(bit-and 0xff %)
-                                     (sam-util/str->compressed-bases (cstr/lower-case ?str)))
-                                ?expected))
-    "="    [0]
-    "=A"   [1]
-    "=C"   [2]
-    "=G"   [4]
-    "=T"   [8]
-    "=."   [15]
-    "A"    [16]
-    "C"    [32]
-    "G"    [64]
-    "T"    [128]
-    "."    [240]
-    "==A"  [0 16]
-    "===A" [0 1]))
-
-(deftest str->compressed-bases-2
- (dotimes [_ 100]
-   (let [s (apply str (repeatedly (inc (rand-int 100)) #(rand-nth nibble-table)))]
-     (is (= (seq (sam-util/str->compressed-bases s)) (encode s))))))
-
-(deftest compressed-bases->str
-  (are [?length ?bases ?offset ?expected] (= (sam-util/compressed-bases->str ?length (byte-array (mapv util/ubyte ?bases)) ?offset)
-                                             ?expected)
-    1   [0x00]                                    0 "="
-    2   [0x00]                                    0 "=="
-    1   [0x10]                                    0 "A"
-    2   [0x12]                                    0 "AC"
-    4   [0x12 0x8F]                               0 "ACTN"
-    1   [0x12 0x8F]                               1 "T"
-    2   [0x12 0x8F]                               1 "TN"
-    16  [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 0 nibble-table
-    14  [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 1 (subs nibble-table 2)
-    2   [0x01 0x23 0x45 0x67 0x89 0xAB 0xCD 0xEF] 7 "BN"
-    512 (range 256)                               0 (->> (for [i nibble-table j nibble-table] [i j])
-                                                         (apply concat)
-                                                         cstr/join)))
-
-;; Reference functions
-;; -------------------
-
-(def refs '({:name "ref", :len 45} {:name "ref2", :len 40}))
-
-(deftest make-refs
-  (is (= (sam-util/make-refs (:header test-sam)) refs)))
-
-(deftest ref-id
-  (are [?name ?expected] (= (sam-util/ref-id refs ?name) ?expected)
-    "ref"      0
-    "ref2"     1
-    "notfound" nil))
-
-(deftest ref-name
-  (are [?id ?expected] (= (sam-util/ref-name refs ?id) ?expected)
-    0 "ref"
-    1 "ref2"
-    9 nil))
-
-(deftest ref-by-name
-  (are [?name ?expected] (= (sam-util/ref-by-name refs ?name) ?expected)
-    "ref"      {:name "ref", :len 45}
-    "ref2"     {:name "ref2", :len 40}
-    "notfound" nil))
-
-(deftest flags
-  (are [?flag ?primary ?set] (and (= (sam-util/decode-flags ?flag) ?set)
-                                  (= (sam-util/encode-flags ?set) ?flag)
-                                  (= (sam-util/primary? ?flag) ?primary)
-                                  (= (sam-util/primary? ?set) ?primary))
-    0     true  #{}
-    1     true  #{:multiple}
-    2     true  #{:properly-aligned}
-    3     true  #{:multiple :properly-aligned}
-    4     true  #{:unmapped}
-    16    true  #{:reversed}
-    83    true  #{:multiple :properly-aligned :reversed :first}
-    163   true  #{:multiple :properly-aligned :next-reversed :last}
-    99    true  #{:multiple :properly-aligned :next-reversed :first}
-    147   true  #{:multiple :properly-aligned :reversed :last}
-    121   true  #{:multiple :next-unmapped :reversed :next-reversed :first}
-    181   true  #{:multiple :unmapped :reversed :next-reversed :last}
-    77    true  #{:multiple :unmapped :next-unmapped :first}
-    141   true  #{:multiple :unmapped :next-unmapped :last}
-    256   false #{:secondary}
-    257   false #{:multiple :secondary}
-    2048  false #{:supplementary}
-    2049  false #{:multiple :supplementary}
-    2304  false #{:secondary :supplementary}
-    0x900 false #{:secondary :supplementary}))
-
-(deftest normalize-bases
-  (are [?src ?result] (= (vec (sam-util/normalize-bases (byte-array (map byte ?src))))
-                         (map byte ?result))
-    [\a \b \c \. \d \e \n \N] [\A \B \C \N \D \E \N \N]))
-
-(deftest into-rf
-  (let [rf-vec (#'sam-util/into-rf [])
-        rf-seq (#'sam-util/into-rf nil)]
-    (is (= (-> (rf-vec)
-               (rf-vec \a)
-               (rf-vec \b)
-               (rf-vec \c)
-               (rf-vec))
-           [\a \b \c]))
-    (is (= (-> (rf-seq)
-               (rf-seq \a)
-               (rf-seq \b)
-               (rf-seq \c)
-               (rf-seq))
-           '(\c \b \a)))))
diff --git a/test/cljam/util/sequence_test.clj b/test/cljam/util/sequence_test.clj
new file mode 100644
index 0000000..53f1f36
--- /dev/null
+++ b/test/cljam/util/sequence_test.clj
@@ -0,0 +1,20 @@
+(ns cljam.util.sequence-test
+  (:require [clojure.test :refer :all]
+            [cljam.util.sequence :as util-seq]))
+
+(deftest revcomp
+  (are [?forward ?reverse]
+      (and (= (util-seq/revcomp ?forward) ?reverse)
+           (= (util-seq/revcomp ?reverse) ?forward))
+    "" ""
+    "A" "T"
+    "G" "C"
+    "N" "N"
+    "a" "t"
+    "g" "c"
+    "n" "n"
+    "AT" "AT"
+    "AAT" "ATT"
+    "ACGTGT" "ACACGT"
+    "GAANTGGN" "NCCANTTC"
+    "aacacacnnnnacacTTTAGAGCNNacacnttg" "caangtgtNNGCTCTAAAgtgtnnnngtgtgtt"))