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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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
- 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
- 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.
-
$\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$ Commented Aug 2, 2017 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$ Commented Aug 2, 2017 at 20:44
-
$\begingroup$ Wait, no, I think I agree. Damn. I'm gonna correct this tomorrow. $\endgroup$ Commented Aug 2, 2017 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$ Commented Aug 2, 2017 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$ Commented Aug 3, 2017 at 9:47