4 ms·

> Going from an unordered set of 100-character reads (with 10% error rate) to a list of somatic variants (mutations, insertions and deletions that have a biolog

by maga 10y ago

> Going from an unordered set of 100-character reads (with 10% error rate) to a list of somatic variants (mutations, insertions and deletions that have a biological effect) is the difficult and costly part Isn't it a software/data science problem? And if so, what makes if difficult? Computational complexity or the availability of reference data, or both?

dekhn 10y ago
If you assume the hardware is fixed, then yes, it's a data problem. What makes it difficult is several things: the genome itself has many repetitive regions whose lengths are greater than 100 characters. If your sequencing technology produces reads less than 100 characters, you don't have enough information to place those reads within their proper location in the genome. Next: There are regions that aren't exact duplicates of each other, but are very similar. If you have a 100 character read, and you know it probably contains errors (a necessary consequence of the sequencing technology), it can be hard to assign it precisely to a single region, as the read will match numerous regions equally well. A huge amount of effort is currently put into mapping these reads to the most appropriate location. Next, because of the high cost of doing the assembly properly, heuristics are used. Often, the heuristics will be based on greedy algorithms, that try to tile overlapping reads to extend the reads into longer segments. However, due to the read error rate, you might accidentally tile two unrelated reads; this wil prevent you from finding the true, optimal solution. To correct for this ambiguity, you typically have to sample a large combinatorial set of possible solutions to find the best ranking one. This is a major area of research. Mapping reads to reference data is often done (instead of wholesale assembly) but it suffers from the same problems. The reference is highly biased, it was based on a small number of individuals; when you try to map reads from an individual who is genetically distinct from the reference nindividual, there will be large regions that don't map (for example, I believe the reference was a European-American, if you try to map African genomes to that reference, you'll find there are entire regions missing from one that are in the other. I don't know a lot of CS, but there is probably a term for taking a bunch of reads and mapping them in a way that maximizes the probability of the mapped reads representing the true solution (IE what is actually in the person's genome). Most people come up with heuristics that (IMHO) have serious deficiencies. When I ran Exacycle at Google we used it to do a "real" assembly (full n2 comparison of all read pairs) and we found it was far more accurate than previously assembled genomes. Subsequent to that, Gene Myers (who designed shotgun assemblers) used these reults to find a heuristic that produced assemblies that were nearly as good but at a much lower cost. I'm personally still skeptical. If sequencers produced 10KB reads with 0.01% error rate, I'd be happy.
- dekhn 10y ago
  Here's the reference from Myers regarding Exacycle and the subsequent DALIGNER: https://dazzlerblog.files.wordpress.com/2015/11/daligner.pdf https://dazzlerblog.files.wordpress.com/2015/11/daligner.pdf It took exacycle 404,000 CPU-hours to do the full n2 comparison (it's an embarassingly parallel problem), but since Exacycle supplied over 600,000 CPU-hours per hour, it took less than one hour to compute. However, that wasn't "scalable" if you wanted to do full de novo assembly on every human (2.8e15 CPU hours) so Myers came up with a heuristic.
- maga 10y ago
  Thanks for detailed reply! This really puts things into perspective. From the NLP side of the data munching isle, it sounds like a lot more complicated variations on language processing problems. Comparing reads to each other is like approximate string matching (or fuzzy matching) we use to account for spelling errors in words, but genome chunks are longer and you don't have dictionaries to check against. And finding the best arrangement of those reads is akin to language modeling where we assign probabilities to word sequences which later can be used to predict the most likely sequence. In case of genomes, though, with so little data, no standard "words", and the error rates in reads, it's like trying to put back a shredded book of in illiterate author only having few other books of illiterate authors as reference.
  - dekhn 10y ago
    my introduction to DNA sequence analysis was "the linguistics of DNA" by David Searlers: https://www.jstor.org/stable/29774782?seq=1#page_scan_tab_contents https://www.jstor.org/stable/29774782?seq=1#page_scan_tab_co... it applies the chomsky hierarchy to sequence analysis, there is in fact a ton of interesting literature around graphical models like HMMs, see https://www.amazon.com/Biological-Sequence-Analysis-Probabilistic-Proteins/dp/0521629713 https://www.amazon.com/Biological-Sequence-Analysis-Probabil... for more details.

by maga 10y ago

dekhn 10y ago

If you assume the hardware is fixed, then yes, it's a data problem. What makes it difficult is several things: the genome itself has many repetitive regions whose lengths are greater than 100 characters. If your sequencing technology produces reads less than 100 characters, you don't have enough information to place those reads within their proper location in the genome. Next: There are regions that aren't exact duplicates of each other, but are very similar. If you have a 100 character read, and you know it probably contains errors (a necessary consequence of the sequencing technology), it can be hard to assign it precisely to a single region, as the read will match numerous regions equally well. A huge amount of effort is currently put into mapping these reads to the most appropriate location. Next, because of the high cost of doing the assembly properly, heuristics are used. Often, the heuristics will be based on greedy algorithms, that try to tile overlapping reads to extend the reads into longer segments. However, due to the read error rate, you might accidentally tile two unrelated reads; this wil prevent you from finding the true, optimal solution. To correct for this ambiguity, you typically have to sample a large combinatorial set of possible solutions to find the best ranking one. This is a major area of research. Mapping reads to reference data is often done (instead of wholesale assembly) but it suffers from the same problems. The reference is highly biased, it was based on a small number of individuals; when you try to map reads from an individual who is genetically distinct from the reference nindividual, there will be large regions that don't map (for example, I believe the reference was a European-American, if you try to map African genomes to that reference, you'll find there are entire regions missing from one that are in the other. I don't know a lot of CS, but there is probably a term for taking a bunch of reads and mapping them in a way that maximizes the probability of the mapped reads representing the true solution (IE what is actually in the person's genome). Most people come up with heuristics that (IMHO) have serious deficiencies. When I ran Exacycle at Google we used it to do a "real" assembly (full n2 comparison of all read pairs) and we found it was far more accurate than previously assembled genomes. Subsequent to that, Gene Myers (who designed shotgun assemblers) used these reults to find a heuristic that produced assemblies that were nearly as good but at a much lower cost. I'm personally still skeptical. If sequencers produced 10KB reads with 0.01% error rate, I'd be happy.

dekhn 10y ago
Here's the reference from Myers regarding Exacycle and the subsequent DALIGNER: https://dazzlerblog.files.wordpress.com/2015/11/daligner.pdf https://dazzlerblog.files.wordpress.com/2015/11/daligner.pdf It took exacycle 404,000 CPU-hours to do the full n2 comparison (it's an embarassingly parallel problem), but since Exacycle supplied over 600,000 CPU-hours per hour, it took less than one hour to compute. However, that wasn't "scalable" if you wanted to do full de novo assembly on every human (2.8e15 CPU hours) so Myers came up with a heuristic.
maga 10y ago
Thanks for detailed reply! This really puts things into perspective. From the NLP side of the data munching isle, it sounds like a lot more complicated variations on language processing problems. Comparing reads to each other is like approximate string matching (or fuzzy matching) we use to account for spelling errors in words, but genome chunks are longer and you don't have dictionaries to check against. And finding the best arrangement of those reads is akin to language modeling where we assign probabilities to word sequences which later can be used to predict the most likely sequence. In case of genomes, though, with so little data, no standard "words", and the error rates in reads, it's like trying to put back a shredded book of in illiterate author only having few other books of illiterate authors as reference.
- dekhn 10y ago
  my introduction to DNA sequence analysis was "the linguistics of DNA" by David Searlers: https://www.jstor.org/stable/29774782?seq=1#page_scan_tab_contents https://www.jstor.org/stable/29774782?seq=1#page_scan_tab_co... it applies the chomsky hierarchy to sequence analysis, there is in fact a ton of interesting literature around graphical models like HMMs, see https://www.amazon.com/Biological-Sequence-Analysis-Probabilistic-Proteins/dp/0521629713 https://www.amazon.com/Biological-Sequence-Analysis-Probabil... for more details.