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.

#8 Perfect k-mer hashing in Sailfish

A podcast about computational biology, bioinformatics, and next generation sequencing.

Science

Life Sciences

In this episode, Marie Sadler talks
about her recent Cell Genomics paper, Multi-layered genetic approaches to
identify approved drug targets.

Previous studies have found that the drugs that target a gene linked to the
disease are more likely to be approved. Yet there are many ways to define what
it means for a gene to be linked to the disease. Perhaps the most
straightforward approach is to rely on the genome-wide association studies (GWAS) data,
but that data can also be integrated with quantitative trait loci (eQTL or pQTL) information
to establish less obvious links between genetic variants (which often lie
outside of genes) and genes. Finally, there’s exome sequencing, which, unlike
GWAS, captures rare genetic variants. So in this paper, Marie and her
colleagues set out to benchmark these different methods against one another.

Listen to the episode to find out how these methods work, which ones
work better, and how network propagation can improve the prediction accuracy.

      

      
      Links:


  Multi-layered genetic approaches to identify approved drug targets
(Marie C. Sadler, Chiara Auwerx, Patrick Deelen, Zoltán Kutalik)
  Marie on GitHub
  Interview with Mariana Mamonova, the Ukrainian marine infantry combat medic who spent 6 months in russian captivity while pregnant


      

      
      Thank you to Jake Yeung, Michael Weinstein, and other Patreon members for supporting this episode.

#70 Prioritizing drug target genes with Marie Sadler

Today on the podcast we have Tomasz Kociumaka and Dominik Kempa,
the authors of the preprint
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space.

The suffix array is one of the foundational data structures in bioinformatics,
serving as an index that allows fast substring searches in a large text.
However, in its raw form, the suffix array occupies the space proportional to (and
several times larger than) the original text.

In their paper, Tomasz and Dominik construct a new index, δ-SA, which on the
one hand can be used in the same way (answer the same queries) as the suffix
array and the inverse suffix array, and on the other hand, occupies the space
roughly proportional to the gzip’ed text (or, more precisely, to the measure δ
that they define — hence the name).

Moreover, they mathematically prove that this index is optimal, in the sense
that any index that supports these queries — or even much weaker queries, such
as simply accessing the i-th character of the text — cannot be significantly
smaller (as a function of δ) than δ-SA.


      

      
      Links:


  Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space (Dominik Kempa, Tomasz Kociumaka)


      

      
      Thank you to Jake Yeung and other Patreon members for supporting this episode.

#69 Suffix arrays in optimal compressed space and δ-SA with Tomasz Kociumaka and Dominik Kempa

In this episode,
David Dylus talks about
Read2Tree,
a tool that builds alignment matrices and phylogenetic trees from raw
sequencing reads.
By leveraging the database of orthologous genes called OMA, Read2Tree bypasses traditional, time-consuming steps such as genome assembly, annotation and all-versus-all sequence comparisons.

      

      
      Links:


  Inference of phylogenetic trees directly from raw sequencing reads using Read2Tree
(David Dylus, Adrian Altenhoff, Sina Majidian, Fritz J. Sedlazeck, Christophe Dessimoz)
  Background story
  Read2Tree on GitHub
  OMA browser
  The Guardian’s podcast about Victoria Amelina and Volodymyr Vakulenko


      

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

#68 Phylogenetic inference from raw reads and Read2Tree with David Dylus

This is the third and final episode in the AlphaFold series, originally recorded on February 23, 2022,
with Amelie Stein, now an associate professor at the University of Copenhagen.

In the episode, Amelie explains what 

#67 AlphaFold and variant effect prediction with Amelie Stein

This is the second episode in the AlphaFold series, originally recorded on February 14, 2022,
with Janani Durairaj, a postdoctoral
researcher at the University of Basel.

Janani talks about how she used shape-mers and topic modelling to discover
classes of proteins assembled by AlphaFold 2 that were absent from the Protein
Data Bank (PDB).

      

      
      The bioinformatics discussion starts at 03:35.

Links:


  A structural biology community assessment of AlphaFold2 applications
(Mehmet Akdel, Douglas E. V. Pires, Eduard Porta Pardo, Jürgen Jänes, Arthur O. Zalevsky, Bálint Mészáros, Patrick Bryant, Lydia L. Good, Roman A. Laskowski, Gabriele Pozzati, Aditi Shenoy, Wensi Zhu, Petras Kundrotas, Victoria Ruiz Serra, Carlos H. M. Rodrigues, Alistair S. Dunham, David Burke, Neera Borkakoti, Sameer Velankar, Adam Frost, Jérôme Basquin, Kresten Lindorff-Larsen, Alex Bateman, Andrey V. Kajava, Alfonso Valencia, Sergey Ovchinnikov, Janani Durairaj, David B. Ascher, Janet M. Thornton, Norman E. Davey, Amelie Stein, Arne Elofsson, Tristan I. Croll & Pedro Beltrao)
  The Protein Universe Atlas
  What is hidden in the darkness? Deep-learning assisted large-scale protein family curation uncovers novel protein families and folds (Janani Durairaj, Andrew M. Waterhouse, Toomas Mets, Tetiana Brodiazhenko, Minhal Abdullah, Gabriel Studer, Mehmet Akdel, Antonina Andreeva, Alex Bateman, Tanel Tenson, Vasili Hauryliuk, Torsten Schwede, Joana Pereira)
  Geometricus: Protein Structures as Shape-mers derived from Moment Invariants on GitHub
  The group page
  The Folded Weekly newsletter
  A New York Times article about the Kramatorsk missile strike. The Instagram video, part of which you can hear at the beginning of the episode, appears to have been deleted.


      

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

#8 Perfect k-mer hashing in Sailfish

Download our free app to listen on your phone