How to estimate Jaccard similarity/distances with MinHash.jl

General Usage
1

Hello, I want to rapidly estimate a distance matrix using Jaccard distance (1 - Jaccard similarity) for a large binary matrix (rows are genomes, columns are genes found in common across genomes).

MinHash seems like the perfect algorithm for this problem. I’m not using k-mers but presence/absence, so I need to roll something different from software like mash or sourmash.

Using Minhash.jl, I am able to rapidly calculate the number of shared genes in a pair of genomes using Minhash.intersectionlength(). However, this is not sufficient to calculate Jaccard similarity, since I have to normalize by the union of genes in the given pair of genomes. For MinHash.jl, I am treating each genome as an array of protein sequences (strings) as input for hashing.

I rolled my own union function for the hashes, but this is slow, especially compared to the speed of Minhash.intersectionlength(). My question is: how can I rapidly calculate/estimate Jaccard similarity using MinHash.jl? @jakobnissen

I also have a nagging feeling that I may be using the API for MinHash.jl incorrectly, since the whole point of the MinHash algorithm is to rapidly estimate Jaccard similarity between pairs of sets.

Thanks!

2

If I understand correctly, you would like something similar to intersection_length, but for the union instead of the intersection. It can be achieved like this:

function union_length(x::MinHashSketch, y::MinHashSketch)
    xi, yi = 1, 1
    n = 0
    @inbounds while (xi ≤ length(x.hashes)) & (yi ≤ length(y.hashes))
        xv, yv = x.hashes[xi], y.hashes[yi]
        n += 1
        xi += xv ≤ yv
        yi += yv ≤ xv
    end
    return n
end

In your case you might want to calculate both in one pass:

function combined_length(x::MinHashSketch, y::MinHashSketch)
    xi, yi = 1, 1
    n_intersections = 0
    n_unions = 0
    @inbounds while (xi ≤ length(x.hashes)) & (yi ≤ length(y.hashes))
        xv, yv = x.hashes[xi], y.hashes[yi]
        n_unions += 1
        n_intersections += xv == yv
        xi += xv ≤ yv
        yi += yv ≤ xv
    end
    return (n_intersections, n_unions)
end

Note that I haven’t tested these functions, so please test them first!

3

Do you think I should include a jaccard function in MinHash?

4

Thanks, Jakob! Yes, this is along the lines of what I am looking for.

Could you also provide a version of unionlength with the same type signature as
function intersectionlength(sketches::AbstractVector{MinHashSketch}) ?

(I tried to puzzle this out myself, but I’m afraid I’m not sophisticated enough).

a jaccard function in MinHash would be great too, especially if it could produce a similarity matrix from an AbstractVector{MinHashSketch}!