4 ms·

If anyone is interested in DNA sequencing, I think the WENGAN paper [0] that came out the other day is pretty interesting too. They are using a hybrid input [1

If anyone is interested in DNA sequencing, I think the WENGAN paper [0] that came out the other day is pretty interesting too. They are using a hybrid input [1] in combination with their software package to reconstruct higher fidelity reference genomes. The big impact from that paper is really summarized by this: > WENGAN assembly of the haploid CHM13 sample achieved a contig NG50 of 80.64 Mb (NGA50: 59.59 Mb), which surpasses the contiguity of the current human reference genome (GRCh38 contig NG50: 57.88 Mb) [0] https://www.nature.com/articles/s41587-020-00747-w https://www.nature.com/articles/s41587-020-00747-w [1] Long and short reads, for example from Nanopore and Illumina, respectively

wiz21c 6y ago
until with have AlphaGenome (they'just beaten some protein folding problem by a laarge margin). (I didn't look in the specifics of the problem so it may be completely wrong, but, you know, these days ...)
- xyhopguy 6y ago
  theyre not really similar problem, genome assembly is a problem that is most effectively solved in the lab and with traditional graph algorithms. protein folding fits very nicely into structured prediction and has a very quantitative way of measuring performance. Genome assembly is more qualitative, to say the least. given a bunch of reads of short(50-300bp) or long (1000-100,000 bp) lengths (we use different algorithms for each) you need to resolve a 1D sequence that holds all of those continguous subsequences for each chromosome. Genome assembly is often described as finding a hamiltonian cycle among the data. For short reads, we use debrujin graphs to avoid the hardness of a complete hamiltonian. for long reads, MinHash has become a popular heuristic. But this can be tricky, for instance, in species that isn't haploid -- you actually have two possible genomes that you need to correctly assemble. Sometimes the difference is a base or two, but sometimes its much longer stretches that can appear as large 'bubbles' in the assembly graph. The assembly problem can be harder or easier depending on the organism, for instance, Wheat is notoriously hard to assemble due to the fact that it has 3 mostly (but not completely) distinct genomes. The Norway Spruce is composed of ~80B basepairs, which will put strain on even the biggest machines. Oh and its mostly repeats. Repeats are _everywhere_, and they can be really long (sometimes on the order of millions of nucleotides). Also -- depending on the species youre assembling, the repeat content and the kind of repeats can change. You also can get different errors from the library preparation, again related to the species of origin. Using lab techniques is particularly helpful, as we can leverage molecular and genetic information. BACs (baceterial artificial choromosomes) can be used to break the genome into smaller continguous chunks and to act as 'anchors' for the larger assembly problem. Recombination rates of different SNPs can be used to infer spatially local segments of DNA, and optical tags can be added and imaged to provide physical anchors for certain sequences. Some organisms can be bred into pure lines, with limited heterozygosity. Expressed RNA transcripts can be used in a similar manner, as they are the concatenation of ordered exons. Combining these methods is typically the best way to get a good genome assembly. Some of the bubble resolution heuristics could probably be improved with deep learning, but getting the right data for that is probably more effective with traditional graph algorithms. Also -- you really only need a good genome assembly once, and sometimes it doesnt even need to be all that good. Genome assembly is a _really_ fascinating area of research, and honestly, the right direction is probably to represent genomes as something other than 1D sequence that more accurately reflects biology. Deep learning is still looking to make its mark on genomics, and unfortunately its not well suited for much of the discovery efforts such as genome assembly.
  - acmj 6y ago
    No practical assemblers take assembly as a Hamiltonian problem.
    - xyhopguy 6y ago
      many long read assemblers (good ones, at that) treat it as a hamiltonian problem.
      - acmj 6y ago
        No, not even a single one of them. Read Gene Myers paper in 1995 or 2005. Modern OLC assemblers all follow that route which has nothing to do with the Hamilton problem. Equating overlap based assembly to a Hamilton problem is the biggest lie in the field of sequence assembly. Please stop spreading that.
  - jakobnissen 6y ago
    What a great write-up. I used to work in metagenomics, where we would assemble environments with hundreds of bacterial genomes. We developed a deep-learning approach to binning the assembly, Vamb, which worked really well. In hindsight, our approach to deep learning was quite naive, so I can easily see more skilled application of DL completely outclass all existing approaches to binning. So while DL indeed would have a hard time with assembly, I'm not sure that's the case for genomics as such.
acmj 6y ago
HiCanu achieved that a year ago. WENGAN is a worse assembler with clearly more misassemblies. It amazes me that this level of paper can be published in Nature Biotech.
- deleted 6y ago
  [deleted]
- alextheparrot 6y ago
  They even call it out in the paper, I hadn’t given it a thorough enough reading. Damn, they must’ve been a bit miffed. I think the novelty they're pitching is the lower resources, but I wonder how much of a problem that is in practice.
  - acmj 6y ago
    Several recent assemblers are faster than WENGAN. For nanopore, there are shasta and wtdbg2 (both published). For HiFi, there are Peregrine and hifiasm (both unpublished but with preprints). I also found their phrasing here misleading: "The run time of WENGAN was at least 183 times faster than that of CANU (UL), while at the same time using less memory than other assemblers such as FLYE and SHASTA". Why not say the other way around (which is also a fact): The run time of WENGAN was at least several times slower than that of shasta, while at the same time using more memory than CANU. Come on, this is not the right way to do comparisons!

wiz21c 6y ago

until with have AlphaGenome (they'just beaten some protein folding problem by a laarge margin). (I didn't look in the specifics of the problem so it may be completely wrong, but, you know, these days ...)

xyhopguy 6y ago
theyre not really similar problem, genome assembly is a problem that is most effectively solved in the lab and with traditional graph algorithms. protein folding fits very nicely into structured prediction and has a very quantitative way of measuring performance. Genome assembly is more qualitative, to say the least. given a bunch of reads of short(50-300bp) or long (1000-100,000 bp) lengths (we use different algorithms for each) you need to resolve a 1D sequence that holds all of those continguous subsequences for each chromosome. Genome assembly is often described as finding a hamiltonian cycle among the data. For short reads, we use debrujin graphs to avoid the hardness of a complete hamiltonian. for long reads, MinHash has become a popular heuristic. But this can be tricky, for instance, in species that isn't haploid -- you actually have two possible genomes that you need to correctly assemble. Sometimes the difference is a base or two, but sometimes its much longer stretches that can appear as large 'bubbles' in the assembly graph. The assembly problem can be harder or easier depending on the organism, for instance, Wheat is notoriously hard to assemble due to the fact that it has 3 mostly (but not completely) distinct genomes. The Norway Spruce is composed of ~80B basepairs, which will put strain on even the biggest machines. Oh and its mostly repeats. Repeats are _everywhere_, and they can be really long (sometimes on the order of millions of nucleotides). Also -- depending on the species youre assembling, the repeat content and the kind of repeats can change. You also can get different errors from the library preparation, again related to the species of origin. Using lab techniques is particularly helpful, as we can leverage molecular and genetic information. BACs (baceterial artificial choromosomes) can be used to break the genome into smaller continguous chunks and to act as 'anchors' for the larger assembly problem. Recombination rates of different SNPs can be used to infer spatially local segments of DNA, and optical tags can be added and imaged to provide physical anchors for certain sequences. Some organisms can be bred into pure lines, with limited heterozygosity. Expressed RNA transcripts can be used in a similar manner, as they are the concatenation of ordered exons. Combining these methods is typically the best way to get a good genome assembly. Some of the bubble resolution heuristics could probably be improved with deep learning, but getting the right data for that is probably more effective with traditional graph algorithms. Also -- you really only need a good genome assembly once, and sometimes it doesnt even need to be all that good. Genome assembly is a _really_ fascinating area of research, and honestly, the right direction is probably to represent genomes as something other than 1D sequence that more accurately reflects biology. Deep learning is still looking to make its mark on genomics, and unfortunately its not well suited for much of the discovery efforts such as genome assembly.
- acmj 6y ago
  No practical assemblers take assembly as a Hamiltonian problem.
  - xyhopguy 6y ago
    many long read assemblers (good ones, at that) treat it as a hamiltonian problem.
    - acmj 6y ago
      No, not even a single one of them. Read Gene Myers paper in 1995 or 2005. Modern OLC assemblers all follow that route which has nothing to do with the Hamilton problem. Equating overlap based assembly to a Hamilton problem is the biggest lie in the field of sequence assembly. Please stop spreading that.
- jakobnissen 6y ago
  What a great write-up. I used to work in metagenomics, where we would assemble environments with hundreds of bacterial genomes. We developed a deep-learning approach to binning the assembly, Vamb, which worked really well. In hindsight, our approach to deep learning was quite naive, so I can easily see more skilled application of DL completely outclass all existing approaches to binning. So while DL indeed would have a hard time with assembly, I'm not sure that's the case for genomics as such.

acmj 6y ago

HiCanu achieved that a year ago. WENGAN is a worse assembler with clearly more misassemblies. It amazes me that this level of paper can be published in Nature Biotech.

deleted 6y ago
[deleted]
alextheparrot 6y ago
They even call it out in the paper, I hadn’t given it a thorough enough reading. Damn, they must’ve been a bit miffed. I think the novelty they're pitching is the lower resources, but I wonder how much of a problem that is in practice.
- acmj 6y ago
  Several recent assemblers are faster than WENGAN. For nanopore, there are shasta and wtdbg2 (both published). For HiFi, there are Peregrine and hifiasm (both unpublished but with preprints). I also found their phrasing here misleading: "The run time of WENGAN was at least 183 times faster than that of CANU (UL), while at the same time using less memory than other assemblers such as FLYE and SHASTA". Why not say the other way around (which is also a fact): The run time of WENGAN was at least several times slower than that of shasta, while at the same time using more memory than CANU. Come on, this is not the right way to do comparisons!