Guillaume Filion's guest appearances

Guillaume Filion

the bioinformatics chat

David Kelley

Irineo Cabreros

Romain Lopez

Gabriel Misrachi

Hassan Samee

Kristina Grigaityte

Jacob Schreiber

Simeon Carstens

Trevor Pesout

HoJoon Lee

Seung Woo Cho

Kaushik Panda

Keith Slotkin

Fernando Portela

Chang Xu

OwlTail

Guillaume Filion recently published a preprint in which he appliesgenerating 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 fromanalytic 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 therelationship 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!

<a href="http://blog.thegrandlocus.com/" rel="nofollow" target="_blank">Guillaume Filion</a> recently published a <a href="https://www.biorxiv.org/content/early/2017/10/18/205427" rel="nofollow" target="_blank">preprint</a> 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: <ul> <li><a href="https://www.biorxiv.org/content/early/2017/10/18/205427" rel="nofollow" target="_blank">Guillaume’s preprint: Analytic combinatorics for bioinformatics I: seeding methods</a></li> <li><a href="http://blog.thegrandlocus.com/2014/06/once-upon-a-blast" rel="nofollow" target="_blank">Once upon a BLAST</a></li> <li><a href="http://blog.thegrandlocus.com/" rel="nofollow" target="_blank">Guillaume’s blog, «The Grand Locus»</a></li> <li><a href="http://csiflabs.cs.ucdavis.edu/~gusfield/" rel="nofollow" target="_blank">Dan Gusfield’s home page</a> featuring the fast fourier transform lectures I mention in the podcast</li> </ul> After we recorded the podcast, Guillaume wrote to me to clarify the relationship between read mapping and BLAST: <blockquote> 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”. </blockquote> <blockquote> 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. </blockquote> <blockquote> 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… </blockquote> <blockquote> 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. </blockquote> If you enjoyed this episode, please consider supporting the podcast on <a href="https://www.patreon.com/bioinfochat" rel="nofollow" target="_blank">Patreon</a>!

#14 Generating functions for read mapping with Guillaume Filion