Microarray DNA Selection - simple solution -
- Target DNA sequence
TCCATCTCTAGAGTCCGTCTCACACGGCTCTCGCACACGGAGATAGCTC
- Strands (max length 7, 15 strands)
TCGCACA
GTCCGTC
TCTAGAG
ACGGAGA
TCCATCT
CGGCTCT
CTCACAC
ATCTCTA
AGAGTCC
CGTCTCA
ACACGGC
CTCTCGC
CACACGG
GAGATAG
ATAGCTC
- Concept
Actually, I cannot say my algorithm of this time is so
clever.
The idea is very similar with what Ravi talked yesterday in the
class.
(Find a minimum unique sinqunce from the leftmost of the target DNA,
and define it as a same length size of the window. Then slide it over the
target DNA as slicing the DNA into strands by every n - 1 steps, where n is
the size of the window.)
My way additionally takes care of how those
strands would chain with each other.
I was supposed to make the program
dealing with this chaining correctly as figuring out the over-lapping strings
between a suffix and a prefix like Word Snake problem.
But I could not
implement this correctly by the last night.
So, on the bug-fixed
version I just slided the window that I can figure out as an unique strands as
moving over the provided DNA with half length of the window.
Then check
again if they are unique or not.
- the
problem page