6 ms·

The Wagner-Fischer (1970) algorithm they mention (AKA Needleman-Wunsch, Lowrance-Wagner, etc) is quadratic in time and space. It might never get any better than

The Wagner-Fischer (1970) algorithm they mention (AKA Needleman-Wunsch, Lowrance-Wagner, etc) is quadratic in time and space. It might never get any better than that in time - an improved version with linear space complexity was presented by Hirschberg in 75 - but that doesn't mean execution times can't be improved. Today there are various variations of the same family of algorithms with ever improving execution times. Some adapt the algorithm to massively parallel setups with hundreds of GPUs, others use speculative execution, some use approximations, and so forth.

throwaway12357 11y ago
> that’s disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. I did a quick googling [1] and > Our algorithm divides the problem into independent `quadrants' ... > Our results show that our GPU implementation is up to 8x faster when operating on a large number of sequences. It's still soul crushing. Why did our genome have to be that long :( BTW, do you have numbers for setups with hundreds of GPUs? I'm also left wondering about results using stochastic solutions. On how accuracy and problem size relate. [1] http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6339593 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=tru...
- daveloyall 11y ago
  I'm confused by this. 1,000 years seems a bit steep to me. Suppose you have two files, `bob.genome` and `mary.genome`. Let's say they are 1gb each [1]. I think I can diff two 1gb files in less than 1,000 years. diff(1) shows "deletions, insertions, and substitutions". Therefor, I don't believe it. Yet. What did I miss? 1. http://stackoverflow.com/questions/8954571/how-much-memory-would-be-required-to-store-human-dna http://stackoverflow.com/questions/8954571/how-much-memory-w... (Rounded up because Fermi estimation [2].) 2. https://what-if.xkcd.com/84/ https://what-if.xkcd.com/84/
  - mmarx 11y ago
    > diff(1) shows "deletions, insertions, and substitutions". diff(1) doesn't give you a _minimal_ set of edits to apply to go from one file to the other, just _a_ set of edits.
    - darkmighty 11y ago
      Also, I think he's picturing two almost-equal files. In that case the average running time should be way lower, no? (I believe the quadratic time is worst case)
      - daveloyall 11y ago
        1,000 years? Really? Isn't it more likely that somebody misquoted "slow, like a half an hour" as "slow, like a THOUSAND YEARS"?
        mmarx 11y ago
        >>> 1000 / ((1024. ** 6) / 3e9 / 86400 / 365) 82.0593593076069 The algorithm is quadratic in the input size. For a Gigabyte of data, that's 1024^6 operations. Dividing that by 3 * 10^9 operations/second (assuming a 3GHz CPU), 86400 (the number of seconds in a day), and 365 (the number of days in a year), we obtain the runtime (in years) assuming that comparing a single byte takes exactly one operation. Dividing 1000 by that number, we get ~82 operations to compare a single byte, and that doesn't look unreasonable.
        mathattack 11y ago
        They're quoting exponential (2^N), not quadratic (N^2) time. If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 elements, an exponential-time algorithm would take about 100 quintillion years.
        mmarx 11y ago
        That is yet another section of the article, the thousand years clearly reference the edit distance, which is quadratic.
- necessity 11y ago
  >BTW, do you have numbers for setups with hundreds of GPUs? I saw a talk on it a while ago, I can only remember they were using CUDAlign and Smith-Waterman (the basic idea is the same). Doing some googling too this seems to be a reasonably recent work with GPUs and CUDAlign (DOI 10.1109/CCGrid.2014.18). >I'm also left wondering about results using stochastic solutions. Another talk, I think they were running Smith-Waterman too. The speculative part was during the traversal of the matrix to get the edit distance. It's not the most time consuming part of the algorithm. I got in late for the talk and I didn't get to hear what they did about filling the matrix in the first place, but I imagine they might have done something similar. I'm not very familiar with Smith-Waterman so I can't go into details.
joe_the_user 11y ago
Also, This is a result about the worst case expected time for an abstract algorithm for finding the edit distance between any two sequences of less than a given length. It's possible an algorithm which usually takes much less time exists. And more to the point, an algorithm knowing something about the structure of genomes might wind-up with even less time. Matching broad areas of different genomes together first seems like an obvious speed-up in this case and I'm sure there are a number of others.

throwaway12357 11y ago

> that’s disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. I did a quick googling [1] and > Our algorithm divides the problem into independent `quadrants' ... > Our results show that our GPU implementation is up to 8x faster when operating on a large number of sequences. It's still soul crushing. Why did our genome have to be that long :( BTW, do you have numbers for setups with hundreds of GPUs? I'm also left wondering about results using stochastic solutions. On how accuracy and problem size relate. [1] http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=6339593 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=tru...

daveloyall 11y ago
I'm confused by this. 1,000 years seems a bit steep to me. Suppose you have two files, `bob.genome` and `mary.genome`. Let's say they are 1gb each [1]. I think I can diff two 1gb files in less than 1,000 years. diff(1) shows "deletions, insertions, and substitutions". Therefor, I don't believe it. Yet. What did I miss? 1. http://stackoverflow.com/questions/8954571/how-much-memory-would-be-required-to-store-human-dna http://stackoverflow.com/questions/8954571/how-much-memory-w... (Rounded up because Fermi estimation [2].) 2. https://what-if.xkcd.com/84/ https://what-if.xkcd.com/84/
- mmarx 11y ago
  > diff(1) shows "deletions, insertions, and substitutions". diff(1) doesn't give you a _minimal_ set of edits to apply to go from one file to the other, just _a_ set of edits.
  - darkmighty 11y ago
    Also, I think he's picturing two almost-equal files. In that case the average running time should be way lower, no? (I believe the quadratic time is worst case)
    - daveloyall 11y ago
      1,000 years? Really? Isn't it more likely that somebody misquoted "slow, like a half an hour" as "slow, like a THOUSAND YEARS"?
      - mmarx 11y ago
        >>> 1000 / ((1024. ** 6) / 3e9 / 86400 / 365) 82.0593593076069 The algorithm is quadratic in the input size. For a Gigabyte of data, that's 1024^6 operations. Dividing that by 3 * 10^9 operations/second (assuming a 3GHz CPU), 86400 (the number of seconds in a day), and 365 (the number of days in a year), we obtain the runtime (in years) assuming that comparing a single byte takes exactly one operation. Dividing 1000 by that number, we get ~82 operations to compare a single byte, and that doesn't look unreasonable.
      - mathattack 11y ago
        They're quoting exponential (2^N), not quadratic (N^2) time. If on some machine a quadratic-time algorithm took, say, a hundredth of a second to process 100 elements, an exponential-time algorithm would take about 100 quintillion years.
        mmarx 11y ago
        That is yet another section of the article, the thousand years clearly reference the edit distance, which is quadratic.
necessity 11y ago
>BTW, do you have numbers for setups with hundreds of GPUs? I saw a talk on it a while ago, I can only remember they were using CUDAlign and Smith-Waterman (the basic idea is the same). Doing some googling too this seems to be a reasonably recent work with GPUs and CUDAlign (DOI 10.1109/CCGrid.2014.18). >I'm also left wondering about results using stochastic solutions. Another talk, I think they were running Smith-Waterman too. The speculative part was during the traversal of the matrix to get the edit distance. It's not the most time consuming part of the algorithm. I got in late for the talk and I didn't get to hear what they did about filling the matrix in the first place, but I imagine they might have done something similar. I'm not very familiar with Smith-Waterman so I can't go into details.

joe_the_user 11y ago

Also, This is a result about the worst case expected time for an abstract algorithm for finding the edit distance between any two sequences of less than a given length. It's possible an algorithm which usually takes much less time exists. And more to the point, an algorithm knowing something about the structure of genomes might wind-up with even less time. Matching broad areas of different genomes together first seems like an obvious speed-up in this case and I'm sure there are a number of others.