Go offline with the Player FM app!
#8 Perfect k-mer hashing in Sailfish
Manage episode 186184557 series 1537951
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:
- The Sailfish paper
- The paper describing the perfect hashing algorithm
- The birthday paradox
- Integrative Biology & Medicine
If you enjoyed this episode, please consider supporting the podcast on Patreon.
70 episodes
Manage episode 186184557 series 1537951
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:
- The Sailfish paper
- The paper describing the perfect hashing algorithm
- The birthday paradox
- Integrative Biology & Medicine
If you enjoyed this episode, please consider supporting the podcast on Patreon.
70 episodes
ทุกตอน
×Welcome to Player FM!
Player FM is scanning the web for high-quality podcasts for you to enjoy right now. It's the best podcast app and works on Android, iPhone, and the web. Signup to sync subscriptions across devices.