Question

In SW algorithm, to align two sequences of lengths of m and n _________ time is required.

(a) O(mn)

(b) O(m^2n)

(c) O(m^2n^3)

(d) O(mn^2)

The question was posed to me by my college professor while I was bunking the class.

I would like to ask this question from Database Searching with the Smith in portion Database Similarity Searching of Bioinformatics

Answer 1

Right option is (b) O(m^2n)

Explanation: The Smith–Waterman algorithm is quite demanding of time. Hence if two sequences of lengths of m and n  have to be aligned, the required time is O(m^2n). It requires O(mn) calculation steps.