3 ms·
As a quadratic algoritm, assuming 13 million base pairs can be solved in 7 seconds on a GTX275 (according to a paper on edit distance computation), is it correc
by nomercy400 11y ago
As a quadratic algoritm, assuming 13 million base pairs can be solved in 7 seconds on a GTX275 (according to a paper on edit distance computation), is it correct to assume that 3 billion base pairs can be solved in (3bil * 3bil / (13mil * 13mil/7)) in 373443 seconds, or about 103 hours. Isn't that fast enough for a quadratic algorithm that samples DNA to be useful?
- noir_lord 11y agoI wondered about that as well, 3 billion squared is a massive number but we have processors in the billions of operations per second per core and machines with hundreds of thousands of processors. I'm curious how fast we could do it on the raw 'string' in the worst case (assuming DNA is entirely random) but it's out of my scope, anyone hazard a guess?
- deleted 11y ago[deleted]
- dr_zoidberg 11y agoI think the article is talking about the "full fledged" problem, while the computation you talk about could be using a set of optimizations aimed particularly at base-pair edit distance problem. For example, I could assume that there no deletions and insertions, only changes and then the problem becomes embarrasingly paralell and extremely easy to express in assembly-like operations. So I could paralellize it on a GPU by splitting the string into fixed length substrings and get huge gains. Problem is, can it be safely assumed that there are no deletions and insertions? Wikipedia has a list with some modifications that can also be used to speedup the calculation under certain constraints: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm#Possible_modifications https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...