3 ms·

It seems to me as though the authors are unfamiliar with bioinformatics standard practice - it's not like this is an unsolved problem, and the existing solution

It seems to me as though the authors are unfamiliar with bioinformatics standard practice - it's not like this is an unsolved problem, and the existing solutions are faster, more computationally elegant, and more flexible. Actually computing and searching for all strings with an edit distance of X away from the query is an incredibly poor way (Guess how long their strategy takes when you increase the edit distance to 5?) of of solving the alignment problem that throws out 40+ years of research on the problem of sequence alignment. The actual solutions to this problem solve it in tenths of a second in vastly superior ways. BLAT[0] is the most obvious and preferred solution designed for alignment against a reference sequence- a 20 BP search against the human genome should essentially be instantaneous. BLAST [1] is more versatile and a bit slower than BLAT, but would also align these sequence sizes against the human genome in ~1-2 seconds, and is a traditional solution to the alignment problem, and has no license restrictions. BWA [2] and Bowtie [3] default settings could also be modified for the task (they're optimized for performing this task with larger strings on the order of thousands of times per second). More generally, it would not be difficult to re-implement any of the algorithms behind these software implementations if the authors really wanted to. It's weird, this is the second post I've seen recently when software folks who are now working in the bioinformatics space have seemed completely unaware of both the basic algorithms we use in computational biology and their common implementations, like Smith-Waterman and Burrows–Wheeler. These are complicated problems with 40+ years of research behind them, and the actual solutions are elegant and fast algorithms which solve the problem in a far superior way within reasonable computational time. [0] http://genome.ucsc.edu/cgi-bin/hgBlat http://genome.ucsc.edu/cgi-bin/hgBlat [1] http://blast.ncbi.nlm.nih.gov/ http://blast.ncbi.nlm.nih.gov/ [2] http://bio-bwa.sourceforge.net/ http://bio-bwa.sourceforge.net/ [3] http://bowtie-bio.sourceforge.net/index.shtml http://bowtie-bio.sourceforge.net/index.shtml

eggie 11y ago
> they're optimized for performing this task with larger strings on the order of thousands of times per second Bingo. And they use on the order of the genome size in RAM to do so. The FM-index is a helluva sequence search machine.
vineetg 11y ago
Thanks for bringing up all of these alternatives. We definitely would have preferred to use an existing solution to building our own. Unfortunately, a lot of the existing software is not intended for the search we're trying to do, or does not perform well under these conditions. We did in fact experiment with some of them before building our own. Bowtie, for example, doesn't allow more than 3 mismatches, and is also intended for alignments where there are very few matches (close to 1). Since we need to be able to support multiple genomes (see Josh's comment), the amount of RAM we need to run a particular set of alignments is relatively important. Things like BLAT (which seems also intended for > 25 bases) need to keep the entire genome index in memory. This means that we would need to spin up a lot more servers to handle parallel requests, especially with different genomes. FWIW our search is only a couple hundred lines of C++, and does the search with very little memory requirements.
- tstactplsignore 11y ago
  Fair points about both the memory requirement and Bowtie - also, 20 BP is really small, so while BLAT seems to find 20 BP hits correctly, it doesn't find 20 BP hits with mismatches. Why be so memory stringent? This is genomics, after all... If you're adverse to rolling your own, I'd look into BWA-MEM as a solution (which has more adjustable mismatch scoring than Bowtie), or figure out how Primer-BLAST seems to do specificity checks for small sequences so well.
  - joshma 11y ago
    We care about reducing memory usage because it gives us greater flexibility in our infrastructure. We're offering this to hundreds of scientists a day - not huge numbers in the grand scheme of things, but usage is bursty and by paying customers. This means we can mix in CRISPR work with our other processing infrastructure, and we can choose between many servers with low memory vs a few servers with high memory. Maybe genomics doesn't have to be so memory hungry. 8)
j-pb 11y ago
How is a fast approximative algorithm better than a slightly slower exact one? Most software done by bio"informaticians" seems sub-par, both in implementation and in theoretical properties. I'd suspect this is caused by the fact that a lot of people actually don't come from CS, but biology or other fields.
- tstactplsignore 11y ago
  We are talking about a brute force, exhaustive search method versus algorithms which have significantly better time complexities. I don't understand how the word "approximate" applies to these algorithms which are largely or entirely deterministic, but sequence alignment is an inherently approximate question. You want your answer to be approximate, because mismatches and gaps are real things. In fact, finding the "approximate" answers are what the OP is after - places in the genome that look like, but aren't exactly, the query sequence. And as soon as you expand your query length or edit distance even a little, finding that becomes completely infeasible. In fact, the OP lucked out because this is a very special circumstance (this method is completely computationally infeasible for 99/100 applications of this problem).
  - ticking 11y ago
    The method they accidentally found is not as bad as you make it to be. https://en.wikipedia.org/wiki/Rabin–Karp_algorithm https://en.wikipedia.org/wiki/Rabin–Karp_algorithm Rabin karp with rolling hashes is actually (not exactly but almost) what tools like rsync, or bittorent use to find chunks and differences in files. So it scales really well. The algorithms you cite come from a time when computers looked rather different in their architectures. Linearly scanning the entire genome from ram for example, could be significantly better than performing multiple index lookups from disk. Many problems of bioinformatics (the text processing) aren't that hard or special anymore, a genome is tiny compared to the amount of data we have lying around elsewhere.

eggie 11y ago

> they're optimized for performing this task with larger strings on the order of thousands of times per second Bingo. And they use on the order of the genome size in RAM to do so. The FM-index is a helluva sequence search machine.

vineetg 11y ago

Thanks for bringing up all of these alternatives. We definitely would have preferred to use an existing solution to building our own. Unfortunately, a lot of the existing software is not intended for the search we're trying to do, or does not perform well under these conditions. We did in fact experiment with some of them before building our own. Bowtie, for example, doesn't allow more than 3 mismatches, and is also intended for alignments where there are very few matches (close to 1). Since we need to be able to support multiple genomes (see Josh's comment), the amount of RAM we need to run a particular set of alignments is relatively important. Things like BLAT (which seems also intended for > 25 bases) need to keep the entire genome index in memory. This means that we would need to spin up a lot more servers to handle parallel requests, especially with different genomes. FWIW our search is only a couple hundred lines of C++, and does the search with very little memory requirements.

tstactplsignore 11y ago
Fair points about both the memory requirement and Bowtie - also, 20 BP is really small, so while BLAT seems to find 20 BP hits correctly, it doesn't find 20 BP hits with mismatches. Why be so memory stringent? This is genomics, after all... If you're adverse to rolling your own, I'd look into BWA-MEM as a solution (which has more adjustable mismatch scoring than Bowtie), or figure out how Primer-BLAST seems to do specificity checks for small sequences so well.
- joshma 11y ago
  We care about reducing memory usage because it gives us greater flexibility in our infrastructure. We're offering this to hundreds of scientists a day - not huge numbers in the grand scheme of things, but usage is bursty and by paying customers. This means we can mix in CRISPR work with our other processing infrastructure, and we can choose between many servers with low memory vs a few servers with high memory. Maybe genomics doesn't have to be so memory hungry. 8)

j-pb 11y ago

How is a fast approximative algorithm better than a slightly slower exact one? Most software done by bio"informaticians" seems sub-par, both in implementation and in theoretical properties. I'd suspect this is caused by the fact that a lot of people actually don't come from CS, but biology or other fields.

tstactplsignore 11y ago
We are talking about a brute force, exhaustive search method versus algorithms which have significantly better time complexities. I don't understand how the word "approximate" applies to these algorithms which are largely or entirely deterministic, but sequence alignment is an inherently approximate question. You want your answer to be approximate, because mismatches and gaps are real things. In fact, finding the "approximate" answers are what the OP is after - places in the genome that look like, but aren't exactly, the query sequence. And as soon as you expand your query length or edit distance even a little, finding that becomes completely infeasible. In fact, the OP lucked out because this is a very special circumstance (this method is completely computationally infeasible for 99/100 applications of this problem).
- ticking 11y ago
  The method they accidentally found is not as bad as you make it to be. https://en.wikipedia.org/wiki/Rabin–Karp_algorithm https://en.wikipedia.org/wiki/Rabin–Karp_algorithm Rabin karp with rolling hashes is actually (not exactly but almost) what tools like rsync, or bittorent use to find chunks and differences in files. So it scales really well. The algorithms you cite come from a time when computers looked rather different in their architectures. Linearly scanning the entire genome from ram for example, could be significantly better than performing multiple index lookups from disk. Many problems of bioinformatics (the text processing) aren't that hard or special anymore, a genome is tiny compared to the amount of data we have lying around elsewhere.