2
$\begingroup$

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.

SETUP

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.

For example:

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.

THE PROBLEM

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]

or

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.

FURTHER COMPLICATIONS

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.

For example:

  • 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.

OUR TASK

We would like to use dynamic programming to interleave m and n to form k such that the total collision penalty is minimised.

EXTENSION

Complete the task with minimal space and time complexity.

$\endgroup$
4
  • $\begingroup$ All I see here is a statement of an exercise style problem. We are a question-and-answer site, so we require you to articulate a specific question, not just copy the text of whatever exercise you happen to be looking at and hope someone will solve it for you. $\endgroup$
    – D.W.
    Apr 17 '19 at 1:29
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Also we have some general resources on dynamic programming here: cs.stackexchange.com/tags/dynamic-programming/info. $\endgroup$
    – D.W.
    Apr 17 '19 at 1:30
  • $\begingroup$ @D.W., this is question is, apparently, the follow-up question to this one as I requested. $\endgroup$
    – John L.
    Apr 17 '19 at 2:18
  • $\begingroup$ @Apass.Jack, if you can understand what their question is, might you have any interest in editing the question to state an explicit technical question? (I don't think "here's a problem, does anyone know of any resources that might be relevant" is a good question -- it's too vague about what the requirements are, what level those resources need to be -- if I gave an introduction to dynamic programming, that would be relevant, but I don't know if it would be useful to the poster). $\endgroup$
    – D.W.
    Apr 17 '19 at 6:35