4 ms·

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 D

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.

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.