Sketching techniques for bioinformatics and Invertible Bloom Lookup Tables

In this talk, we focus on sketching techniques used for efficient processing of big datasets of biosequence data in bioinformatics. After a very brief overview of sketches currently used in bioinformatic tools, we focus on Invertible Bloom lookup tables (IBLTs) which can be seen as hash tables that can store an unlimited number of keys and still are able to report the currently stored keys as long as their number is limited. We show that IBLTs can be useful to recover differences between similar datasets and therefore can act as sketches supporting set difference recovery (set reconciliation). We speculate about possible application of IBLTs to comparison of genomic datasets mentioning some related earlier results we presented to WABI’22.