As DNA reveals its secrets, scientists are assembling a new picture of humanity

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.

They were extremely limited in the resources they could bring to bear on the genome.

Sequencing was expensive and complicated, so even by sequencing several people the best they could do was make one composite image of the whole genome. Representing things as a graph would have provided no benefit at the time, and so people didn't do it.

Now we have thousands of public sequenced genomes. We need a new model for how we manage genomes. We are also learning how much is missed in the standard linear model of the genome, and need a way to incorporate new information into the reference. This all takes time.

Graphs are a good ways of encoding using our prior knowledge of genomes, but they are also difficult for researchers who have grown up on linear systems to understand.

It isn't just an issue of coming up with a good representation of the data. Actually doing something with the graph, like answering the query "is this string a path through the graph?", is hard to do at the necessary scale (you might make a billion such queries after sequencing a genome). The classic string indexing approaches (suffix arrays, fm-index, etc) don't easily generalize to graphs and this is a very active research topic.

There are some sophisticated answer being given, but the simplest answer is that everything is obvious once it's been explained. It's a good principle to remember.

There'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

As far as articles? McVean's, without a doubt!

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

Interesting times ahead, with people recognizing that GxE and GxExE matters far more than G alone.