Solving the DNA Splicer
In Challenge 5 of the 2018 Tuenti Challenge, we are given DNA strands (strings containing a mix of
aAcCgGtT), and asked to find how we can recombine the strands into two matching sequences. Not all of the strands need to be in the final identical sequences. For example, given the input
aacc GgTTC aaccG gTTC aaaa cccc gttc, we need to discover that the sequence
aaccGgTTC can be built twice:
aaccG+gTTC. We then return the positions of the parts we used to create the two identical sequences, in this case 1, 2, 3 and 4.
This is an interesting problem, and I encourage you to take a few minutes to think about how you would solve this before reading on.
The maximum number of parts (18) combined with the time constraints rule out the option of enumerating all the possible combinations of parts. We need to find a slightly more efficient algorihtm.
Let’s start by assuming a...
Continue reading →