The Sequence Alignment problem is one of the fundamental problems of Biological Sciences, aimed at finding the similarity of two amino-acid sequences. Comparing amino-acids is of prime importance to humans, since it gives vital information on evolution and development.
In this project we implement two sequence alignment algorithms.
basic.cpp is pure dynamic programming approach. efficient.cpp is memory efficient approach which combines Divide and conquer and dynamic programming.
-
Basic For the fundamental approach, memory grows polynomially in proportion to the problem size, which is O(nm), where m is the first word's size and n is the second word's size and DP table having size of m rows and n cols.
-
Efficient In efficient approach, memory grows O(2 * m) linearly and it includes the stack used for recursion and dp memory. A DP table has m rows and 2 cols. Therefore, the basic approach consumes more memory, O(mn), whereas the efficient solution consumes less memory, O(2m), and grows linearly.
Even though the basic and efficient approaches have the same time complexity i.e. O(m * n), where m is the size of the first word and n is the size of the second word, the efficient approach takes a little longer than the basic approach because it requires more computations, making it slightly less efficient in terms of time
