1
$\begingroup$

I'm a freshman in Computer Science and I'm studying bioinformatics sequence alignment algorithms.
My understanding of a greedy algorithm is one that takes the best decision for a particular instance in order to find a general best decision. By that definition, would the basic dynamic programming pairwise alignment algorithm be considered greedy?

$\endgroup$
2
$\begingroup$

No. Rather, the DP algorithm for pairwise sequence alignment1 is an instance of backtracking. What makes it superior to naïve exhaustive search is that

  1. it abandons potential solutions as soon as it can prove that it is going to be sub-optimal (each field in the DP matrix considers only the optimal previous sub-alignment), and
  2. it computes partial results only once and reuses them — that’s the “dynamic programming” aspect of it.

There are other, greedy algorithms for pairwise sequence alignment. These will first find so-called perfect “seed matches” between a query and a database, and then extend those outwards using one of several strategies. They thus explore locally optimal solutions but aren’t (in general) guaranteed to find a global optimum. This is for instance what the BLAST algorithm is doing.


1 By which I’m assuming you mean the Needleman–Wunsch or Smith–Waterman algorithm or some minor variation.

$\endgroup$
  • $\begingroup$ I think it's pretty misleading to call quadratic-time DP alignment algorithms "exhaustive search" or "brute force" -- if they are considered to be brute force, then what exact algorithm would not be? The underlying exponential-time recursion, OTOH, I would call brute force. $\endgroup$ – j_random_hacker Aug 2 '17 at 19:38
  • $\begingroup$ @j_random_hacker But I didn't call it “brute force”. And it is enumerating all possible solutions (they're all in the DP matrix). So that's pretty much by definition exhaustive. $\endgroup$ – Konrad Rudolph Aug 2 '17 at 20:44
  • $\begingroup$ Wait, no, I think I agree. Damn. I'm gonna correct this tomorrow. $\endgroup$ – Konrad Rudolph Aug 2 '17 at 21:00
  • $\begingroup$ Your "exhaustive search" link is to a Wikipedia page called "Brute-force search". DP doesn't enumerate all possible solutions, rather just a subset that is known (by cleverly exploiting properties of the problem) to contain all optimal solutions; specifically, DP will never consider a solution that begins with a suboptimal solution to a subproblem (here defined by a pair of prefixes of the 2 input strings). Maybe there's no 100% satisfying definition, since to me, branch and bound could be called exhaustive search, despite similarly avoiding enumerating some solutions.) $\endgroup$ – j_random_hacker Aug 2 '17 at 21:09
  • $\begingroup$ @j_random_hacker Take a look. I think the more correct classification would be “backtracking”, which is a modification of exhaustive search. Branch & bound would also fall under this category, as far as I’m concerned. $\endgroup$ – Konrad Rudolph Aug 3 '17 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.