Search

Home > the bioinformatics chat > #8 Perfect k-mer hashing in Sailfish
Podcast: the bioinformatics chat
Episode:

#8 Perfect k-mer hashing in Sailfish
Category: Science & Medicine
Duration: 00:22:08
Publish Date: 2017-08-05 14:00:00
Description:

The original version of Sailfish, an RNA-Seq quantification tool, used minimal perfect hash functions to replace k-mers with unique integers. (The current version appears to be using a Cuckoo hashmap instead.)

This is my attempt to explain how a minimal perfect hash function could be built. The algorithm described here is not exactly the same as the one Sailfish used, but it follows the same idea.

Sections:

  • Sailfish and perfect hashing (1:15)
  • Perfect hashing based on binary search or hash tables (4:34)
  • Random hash functions (7:34)
  • Perfect hash function based on an acyclic graph (12:16)

Links:
Total Play: 0