strobemers

Strobemers in Go

Introduction

This is a Go implementation of the strobemers (minstrobes and randstrobes), with some differences.

The implementation of Randstrobes has a not-bad performance (2-3X slower) compared to regular k-mer, while it's 10-20X slower than ntHash. Besides, Randstrobes is only slightly slower than MinStrobes (see benchmark).

Attention

The current implementation only computes strobemers of the positive strand, because the strobes are asymmetrical and the location matters.

Installation

go get github.com/shenwei356/strobemers

Quick Start

We followed the code style of ntHash.

n := 2
l := 3
w_min := 3
w_max := 5
rs, err := strobemers.NewRandStrobes(seq, n, l, w_min, w_max)
checkError(err)

var hash uint64
var ok bool
var i int  // 0-based index
var positions []int // 0-based indexes of all strobes

rs.SetWindowShrink(true)
for {
    hash, ok = rs.Next()
    if !ok {
        break
    }

    i = rs.Index()
    positions = rs.Indexes()
}

Differences

Here are some differences compared to the original implementation, see discussion: #1, #2.

Benchmark

$ go test . -bench=Benchmark* -benchmem \
    | grep Bench \
    | perl -pe 's/\s\s+/\t/g' \
    | csvtk cut -Ht -f 1,3-5 \
    | csvtk add-header -t -n test,time,memory,allocs \
    | csvtk pretty -t -r

                                 test           time       memory        allocs
-------------------------------------   ------------   ----------   -----------
           BenchmarkNTHash/1.00_KB-16     8590 ns/op      48 B/op   1 allocs/op
            BenchmarkKmers/1.00_KB-16    55579 ns/op      32 B/op   1 allocs/op
 BenchmarkMinStrobesOrder2/1.00_KB-16   104520 ns/op   25064 B/op   7 allocs/op
 BenchmarkMinStrobesOrder3/1.00_KB-16   111662 ns/op   25064 B/op   7 allocs/op
BenchmarkRandStrobesOrder2/1.00_KB-16    93436 ns/op    8432 B/op   3 allocs/op
BenchmarkRandStrobesOrder3/1.00_KB-16   152461 ns/op    8432 B/op   3 allocs/op

Similar Projects

• strobemer_cpptest

References

• ntHash
• strobemers