4 ms·
Google is using graph learning for representations of stuff where obtaining a huge, representative, "labeled" corpus is hard. As many in the field can tell you
by apathy 10y ago
Google is using graph learning for representations of stuff where obtaining a huge, representative, "labeled" corpus is hard.
As many in the field can tell you, "labeling" genomes is hard, too. You can stick labels like "died at 39 of AVCR" or "had 5 primary tumors by age 28" or "insane multi-substance abuser with extra toes" on a person, but that doesn't really encapsulate all their traits. I claim that genome analysis is a great candidate for semi-supervised learning. Looks like Ben Paten already had that thought...
Haussler, Paten, McVean, and the usual suspects are working on a tractable graph representation to replace (say) hg39, i.e. instead of a new "reference genome", there should be thousands. This makes more sense when you look at how common structural variants (say, inversions) are, and then when you do something like ask Haussler at ASHG "how do we represent inversions in this thing?" you realize how fcking hard it really is to get it right.
McVean & co. made it work for the major histocompatibility complex, which immunologists can explain better than I can, but that's perhaps the most diverse bit of genome there is. It's riddled with ancient repeat element insertions and generally fascinating. It's also a source of Little Problems like organ transplant rejections, graft vs. host disease in stem cell transplants, maybe bits of schizophrenia and neurodegenerative disease... in short, if it can be done for the MHC, it's probably doable for the whole enchilada. It's not easy, though. In fact it's so difficult to get right that a sub-field of accurate HLA typing and immunotyping evolved in parallel to large-scale genome analysis, because it's really, really important not to fuck this up. So that's a note of caution from historical precedent.
Nonetheless, it turns out that your pals at Google spearheaded the effort to have a Hadoop-like "data lake" for genomes (sign up for the GA4GH mailing lists if you like to watch professors bikeshed an API, and occasionally produce incredible insights by accident). Maybe this is going to converge in an interesting way. It won't happen overnight, but it will happen, and the mathematicians will be vindicated.
* Seven Bridges is a little genomics company with a funny name. Unless you're familiar with Eulerian paths and the Seven Bridges of Konigsberg, in which case it's sort of obvious why they chose their name. Nice people, other than the patent, which infuriated most everyone else.
- niels_olson 10y agoHi, I'm a pathology resident and I would like to present a journal club on this. My undergrad is in physics and I have taught myself some bioinformatics, like Durbin's use of Markov models, Ukkonen's suffix tree, BWT, BLAST, but clearly I'm no informatics expert. Two questions: 1) in the absence of a reference genome, does Burrows-Wheeler not apply? 2) Could you recommend any good articles to start from?
- apathy 10y agoThere's probably, in spirit, a graph version of the BWT, but I'm not familiar enough to know it. The approach is less straightforward because you're not just modifying BWT to allow for indels/errors, but rather a graph compression algorithm to allow for fragment searching along vertices of a sequence graph. That said, it has to happen eventually. It's been a while since I took comp bio (sequences & graphs) but what you mentioned is what I learned (and I took it from Waterman, so what I'm saying is that I think you've got it). You can look at Pall's work to see how the current approaches may evolve into something compressible: https://github.com/GFA-spec/GFA-spec https://github.com/GFA-spec/GFA-spec As far as articles? McVean's, without a doubt! http://www.nature.com/ng/journal/v47/n6/full/ng.3257.html http://www.nature.com/ng/journal/v47/n6/full/ng.3257.html An implementation paper for graph assembly HLA typing is at: http://biorxiv.org/content/early/2015/12/24/035253 http://biorxiv.org/content/early/2015/12/24/035253 Interesting times ahead, with people recognizing that GxE and GxExE matters far more than G alone.
- volodia 10y agoHere is a paper that presents a graph version of the BWT: http://bioinformatics.oxfordjournals.org/content/29/13/i361.full http://bioinformatics.oxfordjournals.org/content/29/13/i361....
- apathy 10y agoIt's not 100% clear to me that this is directly compatible with the graph reference, but if it isn't, that seems like a simple matter for Batzoglou & co. Those guys are really, really good, and the multi-reference target is a type of graph anyways, so I imagine it's just a bit more generalization (if any) to make BWBBLE work on a graph-structured reference assembly as implemented (there seem to be certain inconsistencies about how to represent structural variants that differ between implementations). The other thing that would be neat is that then you'd have a direct tie-in to ancestral recombination graphs and could, in principle, get IBS/IBD for the same cost as high-confidence genotyping for any two individuals. Come to think of it, there's probably a way to recast this as shortest paths and get all admissible traversals between a population of genotyped individuals (given an ARG) for the same price as any two. Hmmm. This is a little disturbing.