SSHash as a C++ API / library

[jamshed]

Hello @jermp: thank you for designing this awesome data structure! We at @COMBINE-lab (tag: @rob-p) are finding SSHash very useful.

We are interested in using SSHash from within C++ codes, and were wondering if you could provide some C++ API / header for that. We are, for now, interested in the following basic functionalities. I'm using the "unitig" terminology in the following, but the input sequence types (i.e. unitigs / maximal paths) does not matter.

Given a k-mer x, find its:

• hash value determined by SSHash, i.e. lookup(x)
• unitig ID, i.e. unitig(x)
• offset within the unitig that contains it, i.e. unitig_offset(x)

Given a unitig ID u, find its:

• size, i.e. size(u)
• list of neighbor unitigs, neighbors(u): this likely consists of a query of 2 * 4 (canonical) k-mers.

We hope that these might be feasible for you to provide.

Thanks again!

[jermp]

Hi @jamshed and thank you for this discussion. I'm happy that you're finding the SSHash lib useful.
That's why it exists after all: to be used in other projects :D

What you ask it's almost already there; just a matter of re-structuring the API a little bit.
I will do it in the following days and get back to you!

However, I'm asking some clarifications on the "unitig" queries.

1. Do you need the size of the unitig as a separate method of the dictionary, or can the size be returned when, e.g., doing unitig(x) ? (For example, the method unitig(x), can directly return the triple <unitig_id,unitig_size,offset_within_unitig>.)
2. What do you exactly mean by "neighbour unitigs"? You mean the list of neighbouring k-mers of the unitig? That is, roughly speaking, all k-mers "to the left" of the first k-mer in the unitig and "to the right" of the last k-mer in the unitig. If so, yes, this involves 2 x 4 lookup queries -- this is a navigational query for the k-mers at the two extremes of the unitig.

[jermp]

Also, together with @rob-p, we discussed some time ago that it could also be useful
to return the orientation of the k-mer in the unitig, i.e., a 4-tuple instead of the 3-tuple
I mentioned above: <unitig_id,unitig_size,offset_within_unitig,orientation>.
Is this the operation you need? Thanks!

[jamshed]

Hi @jermp, thank you for your proposals! About your queries:

• The size of the unitig u as a separate method, size(u), would be useful for some use-cases, when you're working with unitig identifiers, irrespective of its constituent k-mers. For example, say when you're traversing a unitig-tiling of sequences, or trying to manipulate the compacted de Bruijn graph where you're primarily working with the unitigs as the vertices.
• By the "neighbor" unitigs of some given unitig u, I mean that the set of other unitigs that are adjacent to this unitig. This makes better sense for compacted de Bruijn graphs, where the unitigs are vertices themselves. You're right about querying all k-mers to the "left" and "right" to determine the neghbor k-mers; but it would also be great if we may have another level of indirection and get the set of unitig IDs that contains those neighboring k-mers. That is, you can imagine two neighbor methods: one that gives you the k-mers, and one for their unitigs. Of course, the second one can just be a wrapper over the first one---collecting the unitig(x) for each neighbor k-mer x.
• Sure, a 4-tuple for a k-mer query unitig(x) makes sense.

I think you could also add any other basic functionalities that you think would be generally useful, to the specific ones I mentioned! Thanks!

[rob-p]

Hi @jermp,

Thanks for your willingness to build out a public API for this :)! I think @jamshed’s description outlines our current intended use case well. One other thing I’d add that I think is critically important, but that may not be obvious given the above discussion (and what I’ve hacked together locally for an older version of SShash) is the return of the tuple above in the case of the streaming query! Since the streaming query is so much faster than point queries for certain common cases, I imagine we’ll be making frequent use of that as well.

There is one more design consideration that is a bit of bikeshedding. If one is returning a 4-tuple like the one above, having it returned as a specific struct rather than as an std::tuple may help to minimize confusion at the caller about exactly which values occur at which positions.

Thanks,
Rob

[jermp]

Many thanks to both of you @jamshed and @rob-p for the clarifications and use cases!
I think I'm good for the moment and can proceed with the implementation of the requested functionalities.
So, to sum up, we have:

1. two unitig-based queries, like size(u) and neighbours(u);
2. one k-mer-based query which returns the 4-tuple (of course as a semantic struct!) <unitig_id,unitig_size,offset_within_unitig,orientation>. This both as a point and streaming query. I'm planning to call it contig query as a generic term for x-tig, with x variable :)

One minor point could be: are there use cases where one only needs the contig ID of k-mer x?
I'm asking this because returning the tuple if one only needs the ID can be expensive and in this
case, a separate method should be used instead.

Thanks!

[jamshed]

Hi @jermp: to answer your last question, yes, we have use-cases where we're only interested in the contig ID of a k-mer x, and nothing else. You may think of this as applicable when you may want to only cluster same-contig k-mers together.

[jermp]

Excellent, thanks! I will provide the methods in the upcoming days and get back to you. (Tomorrow is a busy day; expect this to be done over the weekend.)

[jermp]

Hello @jamshed and @rob-p,
a quick update: in the dev branch I've pushed some additional functionalities.
See https://github.com/jermp/sshash/blob/dev/include/dictionary.hpp.

I've called the new queries "lookup_advanced" since it better conveys the idea that they are still kmer lookup
but return more information compared to a traditional lookup.

I still need to add the neighbour(u) query and modify the streaming query to return the contig info.
After this is done, I will be merging the dev branch into the master one.

[jermp]

Hi @jamshed and @rob-p,
all done also with streaming queries. Can you confirm that everything works on your end as well?
The other neighbour query is forthcoming...
Best,
-Giulio

[rob-p]

ZOMG; exciting! Thanks @jermp — we'll test this out.

--Rob

[rob-p]

Hi @jermp,

Well, I'm always reticent to claim that something's working 100% as expected, but this is looking amazing! I swapped out your new implementation with my previous hack of a streaming_contig_info_query (that gave functionally identical information to the new advanced_query but with a different implementation), and in the context of a PoC mapper, the results over 40M reads are identical. So, either "it's working", or we happened to make identical and equivalent errors ;P. Also, the ease with which the implementations could be switched out is really a testament to the beauty of the API here :).

--Rob

[jermp]

I'm so glad to hear this! Excellent. And thank you again, @jamshed and @rob-p, for formalizing the API in this discussion.

[jermp]

https://github.com/jermp/sshash/releases/tag/v3.0.0

With this release, we now have all the requested functionalities. If you're happy with that, I would close this issue for the moment, but feel free to re-open it. Thanks!