Reading this gives me an idea.
http://www.ncbi.nlm.nih.gov/pmc/artic…
Could we write a script that looked at each separate state of a switch, found the MFE for that state and a sub optimal population near that energy for that state, then compared the two sets of potential solutions by simple string matching for a match between them?
This might be a very fast way of finding good switch solutions.
It’s rather easy to find suboptimal structures for a given sequence : simply take any structure that yields a negative free energy and is not the MFE structure of that specific sequence.
Now, I do not know how to define optimal and/or suboptimal sequences for a given structure… Any sequence that solves the puzzle will have that structure as MFE, but that doesn’t tell us which is optimal or not.
Leaving aside the problem of optimality, one could imagine a solving software good enough to produce long lists of solutions for both shapes, separately and independently. Then it would just be a matter of matching, as you said. But it seems easier to me to have one shape being scanned for solutions, and just doing a verification on the second shape while the search algorithm is running on the first one.
Even so, it looks computationally expensive to me. There ought to be better ways…
Forgot to mention : fascinating paper, thanks 