Speeding up dynamic programming code
3 views (last 30 days)
Show older comments
Is there a way to speed up this piece of code implementing a dynamic programming algorithm?
% sample input
v = repmat('CGACAGCTACTCACTCAGTAGCCGCAGCGAGTGTCTTGACAATTCGGAGGGG', 1, 20);
w = repmat('TATACACATTCATGAATGAAAATTGACCTCCTACAGTTGTAGTGGTAGT', 1, 20);
n = numel(v);
m = numel(w);
s = zeros(n+1, m+1);
back = zeros(n, m);
for i = 1:n
temp = s(i, 1:end-1)+(v(i)==w);
for j = 1:m
[s(i+1, j+1), back(i, j)] = max([s(i, j+1) s(i+1, j) temp(j)]);
end
end
(Memory is also an issue when scaling up, due to the size of arrays "s" and "back", but I have found a way to reduce "s" to just two lines, and "back" could be expressed as uint8)
0 Comments
Answers (0)
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!