6 ms·

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

109 points by yawz 10y ago

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 ago
  Hi, 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 ago
    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 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 ago
      Here 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 ago
        It'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.
WhitneyLand 10y ago
There's got to be a lot more to the story that I don't understand. Why wouldn't it have been obvious 16 years ago that a thoughtfully designed data model was necessary, possibly using graphs, to account for variability and other attributes of the genome? Surely it was foreseeable that tooling would be crucial and that a solid software foundation would be invaluable to enable efficient and flexible processing for years to come? Who were the lead developers supporting the original public genome project and what were they thinking?
- eggie 10y ago
  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.
- j_simpson 10y ago
  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.
- epistasis 10y ago
  A lot of them are the same people that worked on the first reference genome are working on these algorithms, or have/are mentored the scientists in this article. I would say that there's a lot more to analysis of genomes than you expect; there are many different comparisons that make sense. Initially the most informative comparisons were to other species, where a genome graph makes less sense at the time with the amount of data and compute ability that was available to bioinformatics scientists. The rate of technology change for sequencing capabilities in the past 16 years makes Moore's law look like the rate of change in battery technology. 16 years ago I didn't think it would be possible to sequence individuals in the clinic before 2050 or so. Now we are building the technology to analyze the varitation in a million genomes. I guess your question is kind of like, "why didn't computer scientists build systems like Kubernetes or Mesos in the 80s?" The problems and challenges were just different 16 years ago, and there was more than enough to work on between then and now. We don't need genome graphs at this instant, but we will in the coming years. And it's likely that newer representations will come about, too, as more math and theory is invented.
veli_joza 10y ago
Is there an open source project that tries to replicate the Seven Bridges proprietary graphing technology? It seems like a logical next step.
- a_bonobo 10y ago
  There are many people working on various aspects of DNA graphs - for example, there's now the FASTG format, a replacement for the FASTA format which is essentially a graph in text form: http://fastg.sourceforge.net/ http://fastg.sourceforge.net/ Some assemblers (SPAdes?) have started to support this format, but most downstream software only uses the FASTA format (the non-graph version from a single genome/representation). Heng Li (somewhat now the godfather of bioinformatics) wrote a blog post about various implementations here: https://lh3.github.io/2014/07/25/on-the-graphical-representation-of-sequences/ https://lh3.github.io/2014/07/25/on-the-graphical-representa...
  - a_bonobo 10y ago
    Just realised that most of the above is from 2014 - here are some recent works: A novel data structure to store the whole graph: https://almob.biomedcentral.com/articles/10.1186/s13015-016-0083-7 https://almob.biomedcentral.com/articles/10.1186/s13015-016-... Software is here: https://www.uni-ulm.de/in/theo/research/seqana.html https://www.uni-ulm.de/in/theo/research/seqana.html This one maps the whole DNA space using markers: http://www.nature.com/articles/ncomms7914 http://www.nature.com/articles/ncomms7914 Here's a paper that looks at the total genetic space of several individuals, but with read mapping alone, no graphs: http://genomebiology.biomedcentral.com/articles/10.1186/s13059-015-0757-3 http://genomebiology.biomedcentral.com/articles/10.1186/s130... Most of this is based on open source or openly available software. A big company that's closed source is NRGene from Israel, I've read good things about their DeNovoMAGIC/PanMAGIC but I'm unsure how that stuff works exactly (apart from massive short read coverage).
  - roye 10y ago
    The more relevant continuation of Heng Li's posts is Pall Melsted et al's work on GFA: https://github.com/GFA-spec/GFA-spec https://github.com/GFA-spec/GFA-spec This is pretty close to my area...
nonbel 10y ago
Genetics question: How many cells do you need in a population so that there is at least one variant at each position (ie a SNP)? This can be for any species or cell line for which the info is available.
- toufka 10y ago
  Humans have two copies of ~3 Billion base pairs. A reasonable error rate of DNA replication (not under stress) is about 1 write error in 1 billion reads. Many of those errors are actually immediately corrected by post-replication error correction mechanisms. Also, as cells divide, errors that happen early will be propagated more times than errors that happen late in development. Further, mutations are not uniformly distributed though the genome. A human has > 10^14 cells, so any given human might have a few thousand different variants among its cells. The error rates of human polymerase is way less than a bacterial polymerase. And a human genome is way larger than a bacterial (or viral) genome. Viruses actually have mechanisms to increase the error rate of DNA replication. For a human, you would need a LOT more than a single human to have a variant at each position. Something like HIV can actually have a small enough genome, a high enough error rate, and a large enough population in an infected patient, that it can realistically have a unique variant at each position in its genome within a single human host.
  - nonbel 10y ago
    Thanks, I later found this paper that claims something different. Can you explain where this logic has gone wrong, they seem to start out with a similar error rate (~10^-9 per site per division): "For example, the intestinal epithelium contains approximately 10^6 independent stem cells, each of which generates transient daughter cells every week or two. Thus, the intestinal epithelium of a 60-y-old is expected to harbor >10^9 independent mutations. This implies that, not far beyond the age of 60 y, nearly every genomic site is likely to have acquired a mutation in at least one cell in this single organ." http://www.pnas.org/content/107/3/961.full http://www.pnas.org/content/107/3/961.full Edit: >"A reasonable error rate of DNA replication (not under stress) is about 1 write error in 1 billion reads" I think it is that you are using the 10^-9 value to be per genome while that reference uses it as per basepair
rdabane 10y ago
I'm highly interested in learning about genomics. What's the best way for an electrical engineer(signal processing,information theory,graph theory) to start gaining more insights in this field?
wrong_variable 10y ago
I interviewed for Seven Bridge. Very interesting company. They had a typical white board interview process. What they were doing didn't seem that technically hard, and they were more concerned about prior credential ( like most bioinformatics company ) instead of what you were able to do. They also seem to think JavaScript is not worth their time :( The problem they gave me was algorithmic and I just used the tool that was available to me. They apparently write most of it in C++ due to "Speed". The only reason I even got a face-to-face, even though I didn't even has a Masters Degree was due to having done the assignment better than their Phd candidates ( their words ). This piece seems like a submarine article for their proprietary platform.

109 points by yawz 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 ago
Hi, 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 ago
  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 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 ago
    Here 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 ago
      It'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.

WhitneyLand 10y ago

There's got to be a lot more to the story that I don't understand. Why wouldn't it have been obvious 16 years ago that a thoughtfully designed data model was necessary, possibly using graphs, to account for variability and other attributes of the genome? Surely it was foreseeable that tooling would be crucial and that a solid software foundation would be invaluable to enable efficient and flexible processing for years to come? Who were the lead developers supporting the original public genome project and what were they thinking?

eggie 10y ago
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.
j_simpson 10y ago
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.
epistasis 10y ago
A lot of them are the same people that worked on the first reference genome are working on these algorithms, or have/are mentored the scientists in this article. I would say that there's a lot more to analysis of genomes than you expect; there are many different comparisons that make sense. Initially the most informative comparisons were to other species, where a genome graph makes less sense at the time with the amount of data and compute ability that was available to bioinformatics scientists. The rate of technology change for sequencing capabilities in the past 16 years makes Moore's law look like the rate of change in battery technology. 16 years ago I didn't think it would be possible to sequence individuals in the clinic before 2050 or so. Now we are building the technology to analyze the varitation in a million genomes. I guess your question is kind of like, "why didn't computer scientists build systems like Kubernetes or Mesos in the 80s?" The problems and challenges were just different 16 years ago, and there was more than enough to work on between then and now. We don't need genome graphs at this instant, but we will in the coming years. And it's likely that newer representations will come about, too, as more math and theory is invented.

veli_joza 10y ago

Is there an open source project that tries to replicate the Seven Bridges proprietary graphing technology? It seems like a logical next step.

a_bonobo 10y ago
There are many people working on various aspects of DNA graphs - for example, there's now the FASTG format, a replacement for the FASTA format which is essentially a graph in text form: http://fastg.sourceforge.net/ http://fastg.sourceforge.net/ Some assemblers (SPAdes?) have started to support this format, but most downstream software only uses the FASTA format (the non-graph version from a single genome/representation). Heng Li (somewhat now the godfather of bioinformatics) wrote a blog post about various implementations here: https://lh3.github.io/2014/07/25/on-the-graphical-representation-of-sequences/ https://lh3.github.io/2014/07/25/on-the-graphical-representa...
- a_bonobo 10y ago
  Just realised that most of the above is from 2014 - here are some recent works: A novel data structure to store the whole graph: https://almob.biomedcentral.com/articles/10.1186/s13015-016-0083-7 https://almob.biomedcentral.com/articles/10.1186/s13015-016-... Software is here: https://www.uni-ulm.de/in/theo/research/seqana.html https://www.uni-ulm.de/in/theo/research/seqana.html This one maps the whole DNA space using markers: http://www.nature.com/articles/ncomms7914 http://www.nature.com/articles/ncomms7914 Here's a paper that looks at the total genetic space of several individuals, but with read mapping alone, no graphs: http://genomebiology.biomedcentral.com/articles/10.1186/s13059-015-0757-3 http://genomebiology.biomedcentral.com/articles/10.1186/s130... Most of this is based on open source or openly available software. A big company that's closed source is NRGene from Israel, I've read good things about their DeNovoMAGIC/PanMAGIC but I'm unsure how that stuff works exactly (apart from massive short read coverage).
- roye 10y ago
  The more relevant continuation of Heng Li's posts is Pall Melsted et al's work on GFA: https://github.com/GFA-spec/GFA-spec https://github.com/GFA-spec/GFA-spec This is pretty close to my area...

nonbel 10y ago

Genetics question: How many cells do you need in a population so that there is at least one variant at each position (ie a SNP)? This can be for any species or cell line for which the info is available.

toufka 10y ago
Humans have two copies of ~3 Billion base pairs. A reasonable error rate of DNA replication (not under stress) is about 1 write error in 1 billion reads. Many of those errors are actually immediately corrected by post-replication error correction mechanisms. Also, as cells divide, errors that happen early will be propagated more times than errors that happen late in development. Further, mutations are not uniformly distributed though the genome. A human has > 10^14 cells, so any given human might have a few thousand different variants among its cells. The error rates of human polymerase is way less than a bacterial polymerase. And a human genome is way larger than a bacterial (or viral) genome. Viruses actually have mechanisms to increase the error rate of DNA replication. For a human, you would need a LOT more than a single human to have a variant at each position. Something like HIV can actually have a small enough genome, a high enough error rate, and a large enough population in an infected patient, that it can realistically have a unique variant at each position in its genome within a single human host.
- nonbel 10y ago
  Thanks, I later found this paper that claims something different. Can you explain where this logic has gone wrong, they seem to start out with a similar error rate (~10^-9 per site per division): "For example, the intestinal epithelium contains approximately 10^6 independent stem cells, each of which generates transient daughter cells every week or two. Thus, the intestinal epithelium of a 60-y-old is expected to harbor >10^9 independent mutations. This implies that, not far beyond the age of 60 y, nearly every genomic site is likely to have acquired a mutation in at least one cell in this single organ." http://www.pnas.org/content/107/3/961.full http://www.pnas.org/content/107/3/961.full Edit: >"A reasonable error rate of DNA replication (not under stress) is about 1 write error in 1 billion reads" I think it is that you are using the 10^-9 value to be per genome while that reference uses it as per basepair

rdabane 10y ago

I'm highly interested in learning about genomics. What's the best way for an electrical engineer(signal processing,information theory,graph theory) to start gaining more insights in this field?

wrong_variable 10y ago

I interviewed for Seven Bridge. Very interesting company. They had a typical white board interview process. What they were doing didn't seem that technically hard, and they were more concerned about prior credential ( like most bioinformatics company ) instead of what you were able to do. They also seem to think JavaScript is not worth their time :( The problem they gave me was algorithmic and I just used the tool that was available to me. They apparently write most of it in C++ due to "Speed". The only reason I even got a face-to-face, even though I didn't even has a Masters Degree was due to having done the assignment better than their Phd candidates ( their words ). This piece seems like a submarine article for their proprietary platform.