Question

Which of the following is incorrect?

(a) Smith–Waterman algorithm is the fastest

(b) Smith–Waterman algorithm is comparatively slower method

(c) To speedup up comparison, heuristic methods are used

(d) Heuristic algorithms perform faster searches

The question was posed to me during an interview.

This intriguing question originated from Heuristic Database Searching topic in portion Database Similarity Searching of Bioinformatics

Answer 1

The correct choice is (a) Smith–Waterman algorithm is the fastest

For explanation: Searching a large database using the dynamic programming methods, such as the Smith–Waterman algorithm, although accurate and reliable, is too slow and impractical when computational resources are limited. To speed up the comparison, heuristic methods have to be used. The heuristic algorithms perform faster searches because they examine only a fraction of the possible alignments examined in regular dynamic programming.