←back to thread

Seam Carving (2018)

(andrewdcampbell.github.io)
70 points maxwell | 1 comments | 24 Jul 24 19:03 UTC | HN request time: 0.201s | source
Show context
Murky3515[dead post] ◴[27 Jul 24 06:27 UTC] No.41084799[source]▶
[flagged]
_a_a_a_ ◴[27 Jul 24 06:52 UTC] No.41084885[source]▶
[flagged]
replies(4): >>41085044 #>>41085141 #>>41087052 #>>41089622 #
tejtm ◴[27 Jul 24 08:04 UTC] No.41085141[source]▶
Indeed.

I would wager that over the last several decades BLAST (basic local alignment search tool) has done more to advance our knowledge of biology than any other algorithm.

https://en.wikipedia.org/wiki/BLAST_(biotechnology)

replies(1): >>41085207 #
Murky3515 ◴[27 Jul 24 08:21 UTC] No.41085207[source]▶
BLAST isn't a dynamic programming algorithm. It's not guaranteed to find an optimal solution, unlike a DP algorithm. It has some elements of DP, but that's it.
replies(1): >>41085234 #
_a_a_a_ ◴[27 Jul 24 08:27 UTC] No.41085234[source]▶
"BLAST is a heuristic method which means that it is a dynamic programming algorithm..."

https://bioinformaticsreview.com/20210503/how-blast-works-co...

"The heart of many well-known programs is a dynamic programming algorithm, or a fast approximation of one, including sequence database search programs like BLAST..."

https://www.nature.com/articles/nbt0704-909

replies(1): >>41085328 #
Murky3515 ◴[27 Jul 24 08:57 UTC] No.41085328[source]▶
All DP algorithms guarantee an optimal result. It's a defining characteristic of DP. BLAST doesn't. I'm really surprised that you're attempting to debate this.
replies(2): >>41085379 #>>41085676 #
JohnKemeny ◴[27 Jul 24 10:44 UTC] No.41085676[source]▶
That's not true. You can of course use DP for heuristic and approximation algorithms. There's an FPTAS for Knapsack using DP, for instance.
replies(1): >>41088639 #
Murky3515 ◴[27 Jul 24 19:15 UTC] No.41088639[source]▶
It is true. DP always deals with optimization. Just because my car has a radio, doesn't mean my car is a radio.
replies(2): >>41092719 #>>41114936 #
1. tejtm ◴[30 Jul 24 22:56 UTC] No.41114936[source]▶
Technically if you car is recent, it is a cell phone with wheels but I digress.

This reminds me of biologists bickering about what is or is not a gene, and endless snorefests of ontologists bickering about the semantics of a label on an edge in a graph.

It was not amusing then either.