This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be helpful.
You are working in a lab as a microbiologist and would like to formulate an algorithm to interleave two DNA sequences m and n to form a larger DNA sequence k.
m and n are comprised of the elements a, b, and c.
m = [a, b, c, c, a]
n = [b, a, c, c, a]
The italic elements represent members of m, and bold elements represent members of n.
As stated above, we would like to use dynamic programming to interleave the elements of m and n to form a larger sequence k. Some examples of k could be:
k = [a, b, a, c, b, c, a, c, c, a]
k = [b, a, c, c, a, a, b, c, c, a]
Note that the elements of m must appear in k in the same order that they appeared in m, the same applies to the elements of n.
A collision occurs if >= 2 elements of the same type are contiguous in k. Three examples are if k contains the sub-array [a, a] or [b, b, b] or [c, c].
If there is a collision of a's a penalty of u is applied for every consecutive a.
If there is a collision of b's a penalty of o is applied for every consecutive b.
If there is a collisions of c's a penalty of p is applied for every consecutive c.
A subarray of [a, a, a] in k will incur a penalty of u*3.
A subarray of [b, b] in k will incur a penalty of o*2.
A subarray of [c, c, c, c] in k will incur a penalty of p*4.
We would like to use dynamic programming to interleave m and n to form k such that the total collision penalty is minimised.
Complete the task with minimal space and time complexity.