Artwork

Content provided by Roman Cheplyaka. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Roman Cheplyaka or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://player.fm/legal.
Player FM - Podcast App
Go offline with the Player FM app!

#8 Perfect k-mer hashing in Sailfish

22:08
 
Share
 

Manage episode 186184557 series 1537951
Content provided by Roman Cheplyaka. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Roman Cheplyaka or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://player.fm/legal.

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:

If you enjoyed this episode, please consider supporting the podcast on Patreon.

  continue reading

70 episodes

Artwork
iconShare
 
Manage episode 186184557 series 1537951
Content provided by Roman Cheplyaka. All podcast content including episodes, graphics, and podcast descriptions are uploaded and provided directly by Roman Cheplyaka or their podcast platform partner. If you believe someone is using your copyrighted work without your permission, you can follow the process outlined here https://player.fm/legal.

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:

If you enjoyed this episode, please consider supporting the podcast on Patreon.

  continue reading

70 episodes

All episodes

×
 
Loading …

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.

 

Quick Reference Guide