the bioinformatics chat

In this episode, Jacob Schreiber interviews Jill Moore about recent research from the ENCODE Project. They begin their discussion with an overview and goals of the ENCODE Project, and then discuss a bundle of papers that were recently published in various Nature journals and the flagship paper, Expanded encyclopaedias of DNA elements in the human and mouse genomes. They conclude their discussion by talking about the challenges with managing a large project as a trainee in a consortium setting.

Links:

• Expanded encyclopaedias of DNA elements in the human and mouse genomes (The ENCODE Project Consortium, Jill E. Moore, […], Zhiping Weng)
• SCREEN
• The ENCODE Portal
• The ENCODE3 Publication Bundle

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

In systems biology, Boolean networks are a way to model interactions such as gene regulation or cell signaling. The standard interpretations of Boolean networks are the synchronous, asynchronous, and fully asynchronous semantics.

In this episode, Loïc Paulevé explains how the same Boolean networks can be interpreted in a new, “most permissive” way. Loïc proved mathematically that his semantics can reproduce all behaviors achievable by a compatible quantitative model, whereas the traditional interpretations in general cannot. Furthermore, it turns out that deciding whether a certain state in a Boolean network is reachable can be done much more efficiently in MPBNs than in the traditional interpretations.

Links:

• Reconciling Qualitative, Abstract, and Scalable Modeling of Biological Networks (Loïc Paulevé, Juraj Kolčák, Thomas Chatain, Stefan Haar)
• mpbn on GitHub: an implementation of reachability and attractor analysis in Most Permissive Boolean Networks
• BoNesis on GitHub: synthesis of Most Permissive Boolean Networks from network architecture and dynamical properties

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

In this episode, Jacob Schreiber interviews Marinka Zitnik about applications of machine learning to drug development. They begin their discussion with an overview of open research questions in the field, including limiting the search space of high-throughput testing methods, designing drugs entirely from scratch, predicting ways that existing drugs can be repurposed, and identifying likely side-effects of combining existing drugs in novel ways. Focusing on the last of these areas, they then discuss one of Marinka’s recent papers, Modeling polypharmacy side effects with graph convolutional networks.

Links:

• Modeling polypharmacy side effects with graph convolutional networks (Marinka Zitnik, Monica Agrawal, Jure Leskovec)
• Network Medicine Framework for Identifying Drug Repurposing Opportunities for COVID-19 (Deisy Morselli Gysi, Ítalo Do Valle, Marinka Zitnik, Asher Ameli, Xiao Gan, Onur Varol, Helia Sanchez, Rebecca Marlene Baron, Dina Ghiassian, Joseph Loscalzo, Albert-László Barabási)
• AI Cures initiative

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

NGLess is a programming language specifically targeted at next generation sequencing (NGS) data processing. In this episode we chat with its main developer, Luis Pedro Coelho, about the benefits of domain-specific languages, pros and cons of Haskell in bioinformatics, reproducibility, and of course NGLess itself.

Links:

• NGLess on GitHub
• NG-meta-profiler: fast processing of metagenomes using NGLess, a domain-specific language (Luis Pedro Coelho, Renato Alves, Paulo Monteiro, Jaime Huerta-Cepas, Ana Teresa Freitas, Peer Bork)

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

In this episode, I continue to talk (but mostly listen) to Sergey Koren and Sergey Nurk. If you missed the previous episode, you should probably start there. Otherwise, join us to learn about HiFi reads, the tradeoff between read length and quality, and what tricks HiCanu employs to resolve highly similar repeats.

Links:

• HiCanu: accurate assembly of segmental duplications, satellites, and allelic variants from high-fidelity long reads (Sergey Nurk, Brian P. Walenz, Arang Rhie, Mitchell R. Vollger, Glennis A. Logsdon, Robert Grothe, Karen H. Miga, Evan E. Eichler, Adam M. Phillippy, Sergey Koren)
• Canu on GitHub (includes the HiCanu mode)
• The Telomere-to-Telomere (T2T) consortium

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

In this episode, Sergey Nurk and Sergey Koren from the NIH share their thoughts on genome assembly. The two Sergeys tell the stories behind their amazing careers as well as behind some of the best known genome assemblers: Celera assembler, Canu, and SPAdes.

Links:

• Canu on GitHub
• SPAdes on GitHub

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

Porcupine is a molecular tagging system—a way to tag physical objects with pieces of DNA called molecular bits, or molbits for short. These DNA tags then can be rapidly sequenced on an Oxford Nanopore MinION device without any need for library preparation.

In this episode, Katie Doroschak explains how Porcupine works—how molbits are designed and prepared, and how they are directly recognized by the software without an intermediate basecalling step.

Links:

• Porcupine: Rapid and robust tagging of physical objects using nanopore-orthogonal DNA strands (Kathryn Doroschak, Karen Zhang, Melissa Queen, Aishwarya Mandyam, Karin Strauss, Luis Ceze, Jeff Nivala)

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

Will Townes proposes a new, simpler way to analyze scRNA-seq data with unique molecular identifiers (UMIs). Observing that such data is not zero-inflated, Will has designed a PCA-like procedure inspired by generalized linear models (GLMs) that, unlike the standard PCA, takes into account statistical properties of the data and avoids spurious correlations (such as one or more of the top principal components being correlated with the number of non-zero gene counts).

Also check out Will’s paper for a feature selection algorithm based on deviance, which we didn’t get a chance to discuss on the podcast.

Links:

• Feature selection and dimension reduction for single-cell RNA-Seq based on a multinomial model (F. William Townes, Stephanie C. Hicks, Martin J. Aryee, Rafael A. Irizarry)
• GLM-PCA for R
• GLM-PCA for Python
• scry: an R package for feature selection by deviance (alternative to highly variable genes)
• Droplet scRNA-seq is not zero-inflated (Valentine Svensson)

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

In this episode, we hear from Amatur Rahman and Karel Břinda, who independently of one another released preprints on the same concept, called simplitigs or spectrum-preserving string sets. Simplitigs offer a way to efficiently store and query large sets of k-mers—or, equivalently, large de Bruijn graphs.

Links:

• Simplitigs as an efficient and scalable representation of de Bruijn graphs (Karel Břinda, Michael Baym, Gregory Kucherov)
• Representation of k-mer sets using spectrum-preserving string sets (Amatur Rahman, Paul Medvedev)
• Open mic

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

Kris Parag is here to teach us about the mathematical modeling of infectious disease epidemics. We discuss the SIR model, the renewal models, and how insights from information theory can help us predict where an epidemic is going.

Links:

• Optimising Renewal Models for Real-Time Epidemic Prediction and Estimation (KV Parag, CA Donnelly)
• Adaptive Estimation for Epidemic Renewal and Phylogenetic Skyline Models (KV Parag, CA Donnelly)
• The listener survey

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

Does a given bacterial gene live on a plasmid or the chromosome? What other genes live on the same plasmid?

In this episode, we hear from Sergio Arredondo-Alonso and Anita Schürch, whose projects mlplasmids and gplas answer these types of questions.

Links:

• mlplasmids: a user-friendly tool to predict plasmid- and chromosome-derived sequences for single species (Sergio Arredondo-Alonso, Malbert R. C. Rogers, Johanna C. Braat, Tess D. Verschuuren, Janetta Top, Jukka Corander, Rob J. L. Willems, Anita C. Schürch)
• gplas: a comprehensive tool for plasmid analysis using short-read graphs (Sergio Arredondo-Alonso, Martin Bootsma, Yaïr Hein, Malbert R.C. Rogers, Jukka Corander, Rob JL Willems, Anita C. Schürch)

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

In this episode, Benjamin Callahan talks about some of the issues faced by microbiologists when conducting amplicon sequencing and metagenomic studies. The two main themes are:

• Why one should probably avoid using OTUs (operational taxonomic units) and use exact sequence variants (also called amplicon sequence variants, or ASVs), and how DADA2 manages to deduce the exact sequences present in the sample.
• Why abundances inferred from community sequencing data are biased, and how we can model and correct this bias.

Links:

• Exact sequence variants should replace operational taxonomic units in marker-gene data analysis (Benjamin J Callahan, Paul J McMurdie & Susan P Holmes)
• DADA2: High-resolution sample inference from Illumina amplicon data (Benjamin J Callahan, Paul J McMurdie, Michael J Rosen, Andrew W Han, Amy Jo A Johnson & Susan P Holmes)
• In Nature, There Is Only Diversity (Michael R. McLaren, Benjamin J. Callahan)
• Consistent and correctable bias in metagenomic sequencing experiments (Michael R McLaren, Amy D Willis, Benjamin J Callahan)

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

In this episode, Luke Anderson-Trocmé talks about his findings from the 1000 Genomes Project. Namely, the early sequenced genomes sometimes contain specific mutational signatures that haven’t been replicated from other sources and can be found via their association with lower base quality scores. Listen to Luke telling the story of how he stumbled upon and investigated these fake variants and what their impact is.

Links:

• Legacy Data Confounds Genomics Studies (bioRxiv, Molecular Biology and Evolution (paywall)) (Luke Anderson-Trocmé, Rick Farouni, Mathieu Bourgey, Yoichiro Kamatani, Koichiro Higasa, Jeong-Sun Seo, Changhoon Kim, Fumihiko Matsuda and Simon Gravel)

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

In this episode, I talk with Irineo Cabreros about causality. We discuss why causality matters, what does and does not imply causality, and two different mathematical formalizations of causality: potential outcomes and directed acyclic graphs (DAGs). Causal models are usually considered external to and separate from statistical models, whereas Irineo’s new paper shows how causality can be viewed as a relationship between particularly chosen random variables (potential outcomes).

Links:

• Causal models on probability spaces (Irineo Cabreros, John D. Storey)
• The Book of Why: The New Science of Cause and Effect (Judea Pearl, Dana Mackenzie)

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

In this episode, we hear from Romain Lopez and Gabriel Misrachi about scVI—Single-cell Variational Inference. scVI is a probabilistic model for single-cell gene expression data that combines a hierarchical Bayesian model with deep neural networks encoding the conditional distributions. scVI scales to over one million cells and can be used for scRNA-seq normalization and batch effect removal, dimensionality reduction, visualization, and differential expression. We also discuss the recently implemented in scVI automatic hyperparameter selection via Bayesian optimization.

Links:

• Deep generative modeling for single-cell transcriptomics (Romain Lopez, Jeffrey Regier, Michael Cole, Michael I. Jordan, Nir Yosef)
• scVI on GitHub
• Should we zero-inflate scVI?
• Hyperparameter search for scVI
• Droplet scRNA-seq is not zero inflated (Valentine Svensson)

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

Even though the double-stranded DNA has the famous regular helical shape, there are small variations in the geometry of the helix depending on what exact nucleotides its made of at that position.

In this episode of the bioinformatics chat, Hassan Samee talks about the role the DNA shape plays in recognition of the DNA by DNA-binding proteins, such as transcription factors. Hassan also explains how his algorithm, ShapeMF, can deduce the DNA shape motifs from the ChIP-seq data.

Links:

• A De Novo Shape Motif Discovery Algorithm Reveals Preferences of Transcription Factors for DNA Shape Beyond Sequence Motifs (Md. Abul Hassan Samee, Benoit G. Bruneau, Katherine Pollard)
• ShapeMF on GitHub
• A picture explaining some of the DNA shape features

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

An αβ T-cell receptor is composed of two highly variable protein chains, the α chain and the β chain. However, based only on bulk DNA or RNA sequencing it is impossible to determine which of the α chain and β chain sequences were paired in the same receptor.

In this episode, Kristina Grigaityte talks about her analysis of 200,000 paired αβ sequences, which have been obtained by targeted single-cell RNA sequencing. Kristina used the power law distribution to model the T-cell clone sizes, which led her to reject the commonly held assumptions about the independence of the α and β chains. We also talk about Bayesian inference of power law distributions and about mixtures of power laws.

Links:

• Single-cell sequencing reveals αβ chain pairing shapes the T cell repertoire. Kristina Grigaityte, Jason A. Carter, Stephen J. Goldfless, Eric W. Jeffery, Ronald J. Hause, Yue Jiang, David Koppstein, Adrian W. Briggs, George M. Church, Francois Vigneault, Gurinder S. Atwal
• Bayesian inference of power law distributions. Kristina Grigaityte, Gurinder Atwal
• Mathematics in modern immunology. Castro M, Lythe G, Molina-París C, Ribeiro RM.
• Power laws, Pareto distributions and Zipf’s law. M. E. J. Newman
• So You Think You Have a Power Law — Well Isn’t That Special?

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

Modern genome assembly projects are often based on long reads in an attempt to bridge longer repeats. However, due to the higher error rate of the current long read sequencers, assemblers based on de Bruijn graphs do not work well in this setting, and the approaches that do work are slower.

In this episode, Mikhail Kolmogorov from Pavel Pevzner’s lab joins us to talk about some of the ideas developed in the lab that made it possible to build a de Bruijn-like assembly graph from noisy reads. These ideas are now implemented in the Flye assembler, which performs much faster than the existing long read assemblers without sacrificing the quality of the assembly.

Links:

• Assembly of Long Error-Prone Reads Using Repeat Graphs (Mikhail Kolmogorov, Jeffrey Yuan, Yu Lin, Pavel. A. Pevzner. Nature Biotechnology (paywalled), bioRxiv
• Flye on GitHub

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

In this episode, we hear from Jacob Schreiber about his algorithm, Avocado.

Avocado uses deep tensor factorization to break a three-dimensional tensor of epigenomic data into three orthogonal dimensions corresponding to cell types, assay types, and genomic loci. Avocado can extract a low-dimensional, information-rich latent representation from the wealth of experimental data from projects like the Roadmap Epigenomics Consortium and ENCODE. This representation allows you to impute genome-wide epigenomics experiments that have not yet been performed.

Jacob also talks about a pitfall he discovered when trying to predict gene expression from a mix of genomic and epigenomic data. As you increase the complexity of a machine learning model, its performance may be increasing for the wrong reason: instead of learning something biologically interesting, your model may simply be memorizing the average gene expression for that gene across your training cell types using the nucleotide sequence.

Links:

• Avocado on GitHub
• Multi-scale deep tensor factorization learns a latent representation of the human epigenome (Jacob Schreiber, Timothy Durham, Jeffrey Bilmes, William Stafford Noble)
• Completing the ENCODE3 compendium yields accurate imputations across a variety of assays and human biosamples (Jacob Schreiber, Jeffrey Bilmes, William Noble)
• A pitfall for machine learning methods aiming to predict across cell types (Jacob Schreiber, Ritambhara Singh, Jeffrey Bilmes, William Stafford Noble)

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

The third Bioinformatics Contest took place in February 2019.

Alexey Sergushichev, one of the organizers of the contest, and Gennady Korotkevich, the 1st prize winner, join me to discuss this year’s problems.

Timestamps and links for the individual problems:

• Qualification round
  • 00:07:14 Bee Population
  • 00:14:12 Sequencing Errors
  • 00:30:20 Transposable Elements
• Final round
  • 00:41:35 Cancer and Chromosome Rearrangements
  • 00:56:01 Epigenomic Marks
  • 01:10:02 Bacterial Communities
  • 01:27:06 Minimal Genome
  • 01:34:56 Endangered Species

Links:

• The contest problems on Stepik
• The final scoreboard
• Episode #18: Bioinformatics Contest 2018

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

Hi-C is a sequencing-based assay that provides information about the 3-dimensional organization of the genome. In this episode, Simeon Carstens explains how he applied the Inferential Structure Determination (ISD) framework to build a 3D model of chromatin and fit that model to Hi-C data using Hamiltonian Monte Carlo and Gibbs sampling.

Links:

• Bayesian inference of chromatin structure ensembles from population Hi-C data (Simeon Carstens, Michael Nilges, Michael Habeck)
• Inferential Structure Determination of Chromosomes from Single-Cell Hi-C Data (Simeon Carstens, Michael Nilges, Michael Habeck)

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

Long read sequencing technologies, such as Oxford Nanopore and PacBio, produce reads from thousands to a million base pairs in length, at the cost of the increased error rate. Trevor Pesout describes how he and his colleagues leverage long reads for simultaneous variant calling/genotyping and phasing. This is possible thanks to a clever use of a hidden Markov model, and two different algorithms based on this model are now implemented in the MarginPhase and WhatsHap tools.

Links:

• Preprint: Haplotype-aware genotyping from noisy long reads (Jana Ebler, Marina Haukness, Trevor Pesout, Tobias Marschall, Benedict Paten)

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

This time you’ll hear from Fabio Cunial on the topic of Markov models and space-efficient data structures. First we recall what a Markov model is and why variable-order Markov models are an improvement over the standard, fixed-order models. Next we discuss the various data structures and indexes that allowed Fabio and his collaborators to represent these models in a very small space while still keeping the queries efficient. Burrows-Wheeler transform, suffix trees and arrays, tries and suffix link trees, and more!

Links:

• The preprint: A framework for space-efficient variable-order Markov models
• The book: Genome-Scale Algorithm Design
• The GitHub repo

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

In this episode, HoJoon Lee and Seung Woo Cho explain how to perform a CRISPR experiment and how to analyze its results. HoJoon and Seung Woo developed an algorithm that analyzes sequenced amplicons containing the CRISPR-induced double-strand break site and figures out what exactly happened there (e.g. a deletion, insertion, substitution etc.)

Links:

• CRISPRpic: Fast and precise analysis for CRISPR-induced mutations via prefixed index counting
• CRISPRpic on GitHub

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

Relief is a statistical method to perform feature selection. It could be used, for instance, to find genomic loci that correlate with a trait or genes whose expression correlate with a condition. Relief can also be made sensitive to interaction effects (known in genetics as epistasis).

In this episode, Trang Lê joins me to talk about Relief and her version of Relief called STIR (STatistical Inference Relief). While traditional Relief algorithms could only rank features and needed a user-supplied threshold to decide which features to select, Trang’s reformulation of Relief allowed her to compute p-values and make the selection process less arbitrary.

Links:

• Paper: STatistical Inference Relief (STIR) feature selection
• STIR on GitHub
• Relief on Wikipedia
• The original Relief paper by Kira and Rendell (1992)
• Epistasis: what it means, what it doesn’t mean, and statistical methods to detect it in humans

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

Kaushik Panda and Keith Slotkin come on the podcast to educate us about repetitive DNA and transposable elements. We talk LINEs, SINEs, LTRs, and even Sleeping Beauty transposons! Kaushik and Keith explain why repeats matter for your whole-genome analysis and answer listeners’ questions.

Links:

• Keith’s paper: The case for not masking away repetitive DNA
• Questions for this episode on Reddit

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

Antoine Limasset joins me to talk about NGS read correction. Antoine and his colleagues built the read correction tool Bcool based on the de Bruijn graph, and it corrects reads far better than any of the current methods like Bloocoo, Musket, and Lighter.

We discuss why and when read correction is needed, how Bcool works, and why it performs better but slower than k-mer spectrum methods.

Links:

• Preprint: Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs
• Bcool on GitHub

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

In this episode, I talk to Fernando Portela, a software engineer and amateur scientist who works on RNA design — the problem of composing an RNA sequence that has a specific secondary structure.

We talk about how Fernando and others compete and collaborate in designing RNA molecules in the online game EteRNA and about Fernando’s new RNA design algorithm, NEMO, which outperforms all prior published methods by a wide margin.

Links:

• The EteRNA game
• The preprint about NEMO
• NEMO project page
• Single-cell RNABIO & organoids meeting in Kiev

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

In this episode I’m joined by Chang Xu. Chang is a senior biostatistician at QIAGEN and an author of smCounter2, a low-frequency somatic variant caller. To distinguish rare somatic mutations from sequencing errors, smCounter2 relies on unique molecular identifiers, or UMIs, which help identify multiple reads resulting from the same physical DNA fragment.

Chang explains what UMIs are, why they are useful, and how smCounter2 and other tools in this space use UMIs to detect low-frequency variants.

Links:

• smCounter2 preprint
• smCounter2 github repository
• smCounter publication
• Review of somatic SNV callers

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

Linear mixed models are used to analyze GWAS data and detect QTLs. Andrey Ziyatdinov recently released an R package, lme4qtl, that can be used to formulate and fit these models. In this episode, Andrey and I discuss linear mixed models, genome-wide association studies, and strengths and weaknesses of lme4qtl.

Links:

• Paper: lme4qtl: linear mixed models with flexible covariance structure for genetic studies of related individuals
• lme4qtl on GitHub

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

In this episode Kristian Davidsen and Amrit Dhar present their project called SPURF. SPURF can predict the B cell receptor (BCR) substitution profile of a given clonal family based on a single representative sequence from that family. SPURF works by fitting a tensor regression model to publicly available Rep-seq data.

Links:

• Preprint: Predicting B Cell Receptor Substitution Profiles Using Public Repertoire Data
• Blog post about SPURF by Erick Matsen
• SPURF on GitHub

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

In this episode, Gustavo Glusman explains his method of reducing a VCF file to a small “fingerprint”, which could be then used to detect duplicate genomes, infer relatedness, map the population structure, and more.

Links:

• The genome fingerprints paper
• The genotype fingerprints preprint
• The data fingerprints preprint
• The blog post about time series visualization

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

The final round of Bioinformatics Contest 2018 was held on February 24-25th, and the qualification round took place two weeks earlier.

I invited the organizers of the contest, Alexey Sergushichev and Ekaterina Vyahhi, to discuss the problems and find out what it was like to organize the contest.

Timestamps for the problems:

• Qualification round
  • 0:41:38 Problem 1. Synthesis of ATP
  • 0:48:46 Problem 2. Restriction Sites
  • 1:06:42 Problem 3. Tandem Repeats
• Final round
  • 1:14:00 Problem 1. Recombination of Plasmids
  • 1:25:30 Problem 2. Species Recovering
  • 1:28:39 Problem 3. Haplotype Phasing
  • 1:36:34 Problem 4. Cluster the Reads
  • 1:40:25 Problem 5. Cattle Breeding

Links:

• The contest problems on Stepik
• The final scoreboard
• Bioinformatics Institute

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

In this episode, Amy Willis joins me to talk about good and bad ways to estimate taxonomic richness in microbial ecology studies.

Links:

• Rarefaction, alpha diversity, and statistics
• Estimating Diversity via Frequency Ratios
• Estimating the Number of Species in Microbial Diversity Studies
• Summer Institutes 2018 at the University of Washington
• STAMPS: Strategies and Techniques for Analyzing Microbial Population Structures
• bio2040, a new podcast by Flavio Rump

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

Javier Quilez and I discuss what it’s like to be a bioinformatician, how to improve communication between the wet and dry labs and make the research more reproducible.

Make sure to read Javier’s paper we are discussing; it’s a light and entertaining read. The last author on this paper is Guillaume Filion, whom you may remember from the episode on generating functions.

Links:

• Parallel sequencing lives, or what makes large sequencing projects successful

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

Geoffrey Schiebinger explains how reconstructing developmental trajectories from single-cell RNA-seq data can be reduced to the mathematical problem called optimal transport.

Links:

• Reconstruction of developmental landscapes by optimal-transport analysis of single-cell gene expression sheds light on cellular reprogramming.
• Talk by Geoffrey and Lénaïc Chizat

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

Guillaume Filion recently published a preprint in which he applies generating functions, a concept from analytic combinatorics, to estimating the optimal seed length for read mapping.

In this episode, Guillaume and I attempt to explain the core concepts from analytic combinatorics and why they are useful in modeling sequences.

Links:

• Guillaume’s preprint: Analytic combinatorics for bioinformatics I: seeding methods
• Once upon a BLAST
• Guillaume’s blog, «The Grand Locus»
• Dan Gusfield’s home page featuring the fast fourier transform lectures I mention in the podcast

After we recorded the podcast, Guillaume wrote to me to clarify the relationship between read mapping and BLAST:

I looked into my notes about BLAST. The problem that it solves is the following: “Given that a local alignment has score S, what is the probability that it does not contain a word of score T or greater”? The background work of Karlin and Altschul is used to give a statistical significance for S (what is the probability that a “Smith-Waterman random walk” starting at height 0 would reach height S, i.e. what is the probability that aligning two random proteins would yield a score S). The authors write in the original paper “Theory does not yet exist to calculate the probability q that such segment pair will contain a word pair with a score of at least T. However, one argument suggests that q should depend exponentially upon the score of the MSP”.

This is the part that I did not remember well. MSP stands for Maximal Segment Pair, this is the “longest fragment” with “highest score” in the alignment. I thought that Karlin and Altschul solved this part as well, but the authors just go empirical and they calibrate the relationship between T and S with simulations.

I realize a little bit better now that my work is precisely about this problem that the authors of BLAST could not solve, but as you pointed out, I am attacking only a very specific sub-case that is much easier because the models of sequencing error are much simpler than protein evolution. BLAST is concerned with local alignment, so it wants to get all the hits with an MSP score above S. Short read mapping just wants the true location of the read, which does not really have the notion of a score S. But still, mathematically, it is equivalent to the case where S is a constant that depends only on the read size and the distribution of the score T depends only on the seed length and the error rate. I have a few ideas of how to use analytic combinatorics to solve the problem for proteins, but it is mostly complicated because the variable of interest T is a fractional numbers and not an integer…

So what is different from BLAST? The right answer (I think) is that BLAST finds all the hits with an MSP above statistical background, but it says nothing of the probability that the true location contains such an MSP, so it is hard to calibrate the heuristic for that specific problem. In reality, the parallel with BLAST is just the basic strategy: make a statistical model for your problem and use it to calibrate the heuristic.

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

Jennifer Lu joins me to discuss species abundance estimation from metagenomic sequencing data.

Links:

• The Bracken paper
• The Kraken paper
• The preprint that applies Kallisto to metagenomics

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

In this episode, Filippo Castiglione and I discuss different ways to model the immune system.

Links:

• Celada’s and Seiden’s 1992 paper, “A computer model of cellular interactions in the immune system”
• Filippo’s 2001 paper, “Design and implementation of an immune system simulator”
• PLOS One paper, “Computational Immunology Meets Bioinformatics: The Use of Prediction Tools for Molecular Binding in the Simulation of the Immune System”
• A paper about modelling sea bass vaccination using C-ImmSim
• C-ImmSim homepage
• The online simulator based on C-ImmSim and the paper describing it

Special thanks to Martina Stoycheva for bringing this work to my attention.

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

In this episode, Linus Schumacher joins me to discuss mathematical models of collective cell migration and multidisciplinary research.

Links:

• Semblance of Heterogeneity in Collective Cell Migration and associated code
• Multidisciplinary approaches to understanding collective cell migration in developmental biology
• Linus’s homepage

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

Valentine Svensson explains how he analyzes spatially-annotated single cell gene expression data using Gaussian processes.

Links:

• Valentine’s preprint, “SpatialDE - Identification Of Spatially Variable Genes”
• SpatialDE code on GitHub
• Valentine’s personal page
• The Integrative Biology & Medicine conference

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

Michael Tessler and Christopher Mason join me to talk about their comparison of 16S amplicon sequencing and shotgun sequencing for quantifying microbial diversity.

Links:

• The 2017 Nature paper that we discuss: Large-scale differences in microbial biodiversity discovery between 16S amplicon and shotgun sequencing

• Michael’s et al. 2016 paper that describes their original 16S study: A Global eDNA Comparison of Freshwater Bacterioplankton Assemblages Focusing on Large-River Floodplain Lakes of Brazil

• The sequencing data for these studies is available from NCBI: PRJNA310230 (16S), PRJNA389803 (shotgun)

• Michael’s website

• Christopher’s lab website

• The Integrative Biology & Medicine conference, featuring the talk on Postmodern Synthesis by Eugene Koonin

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

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.

What is metagenomics and how is it different from phylotyping?

What is Kraken and how can it be faster than BLAST?

Let’s try to sort this out.

Sections:

• Culturing and its limitation (00:18)
• Metagenomics vs phylotyping (1:43)
• BLAST (5:53)
• The idea behind Kraken (8:14)
• How Kraken organizes its database (18:08)

Links:

• The paper about Kraken
• A freely accessible (though a bit dated) book on metagenomics

Correction: in this episode, I incorrectly state that Kraken operates on phylogenetic trees, whereas in fact it operates on taxonomic trees.

In practice this means that when Kraken cannot decide among several species, it assigns the read to their lowest common taxon (genus, family etc.), not their latest common evolutionary ancestor.

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

I talk about allele-specific expression: why it arises and how it can be reliably detected.

Sections:

• The biology of allele-specific expression (2:17)
• Detecting allele-specific expression with RNA-seq (7:46)
• Mapping and sequencing biases (16:39)
• The experiment in yeast (19:47)
• Statistical models (21:44)

Links:

• A powerful and flexible statistical framework for testing hypotheses of allele-specific gene expression from RNA-seq data
  • Supplemenal information
• Effect of read-mapping biases on detecting allele-specific expression from RNA-sequencing data
• The talk by John Marioni
• The blog post explaining the RSEM model

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

In this episode, Thom Quinn and I explore different ways to transform and analyze relative data arising in genomics.

We also discuss propr, Thom’s R package to compute various proportionality measures.

Links:

• Thom’s preprint about propr — take a look if you feel lost in all the quantities that we discuss :)
• David Lovell original paper introducing proportionality for relative data and a very detailed appendix
• Ionas Erb’s paper introducing the ρ metric
• Vignettes for propr

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

In this episode, I meet with Georg Stricker and Julien Gagneur from the Technical University of Munich to discuss ChIP-seq data analysis and their tool, GenoGAM.

Links:

• Preprint about GenoGAM
• Georg on GitHub
• Julien’s lab on Twitter
• [BC]² — The Basel Computational Biology Conference (Basel, September 2017), where you can meet Georg
• The European Human Genetics Conference (Copenhagen, May 2017), where you can meet Daniel Bader from Julien’s lab

Register for the Summer School in Bioinformatics & NGS Data Analysis (#NGSchool2017) (Poland, September 2017)

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

In this episode Antonio Marco talks about miRNA target site prediction and his tool, seedVicious.

Links:

• seedVicious preprint
• seedVicious manual

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

In this episode Aleksandra Kolodziejczyk talks about single-cell RNA sequencing.

Links:

• A review paper by Aleksandra
• Comparative analysis of single-cell RNA sequencing methods, including the cost table
• Power Analysis of Single Cell RNA‐Sequencing Experiments
• Monocle: a toolkit for analyzing single-cell gene expression experiments
• Questions from listeners on bioinformatics.chat and reddit

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

In this episode, Mingfu Shao talks about Scallop, an accurate reference-based transcript assembler.

Links:

• The preprint about Scallop
• The preprint about flow decomposition
• The video of a talk by Ben Langmead about Rail-RNA
• The preprint about Rail-RNA

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