CME 352, Molecular algorithms, Winter 2007-08.


Project suggestions:
--------------------
These are all open problems, a complete solution to which would be
publishable in my opinion. Feel free to discuss these with me, except 4,
which I have not thought about carefully yet. Before deciding on a
problem, please check with me to make sure two project groups in the class
are not competing on very similar problems. All papers are on the class web
page.

1) Read the papers

Self-Healing Tile Sets
Erik Winfree

and

Self-Assembling Tile Systems that Heal from Small Fragments.
H. Chen, A. Goel, C. Luhrs, and E. Winfree.

Then answer the following question: Suppose you have a Chinese remainder
counter which has K columns, one corresponding to each of the first K
primes. Suppose the counter has been fully formed. How long will it take
for the counter to get split into two, assuming that tiles are falling off
at rate r and attaching at rate f, where f > r?

While the above is challenging enough, in case you solve that, the
following are natural next questions to answer: How high does the infinite
binary counter described in the second paper above grow? Or at least, does
it grow to an infinite size or does it remain finite?

2) Read the papers 

A Unidirectional DNA Walker That Moves Autonomously along a Track
Peng Yin, Hao Yan, Xiaoju G. Daniell, Andrew J. Turberfield, John H. Reif

and

Towards programmable molecular machines
H. Chen, A.De, and A. Goel

Solve any of the open problems listed at the end.

3) Read the paper 

Dimension Augmentation and Combinatorial Criteria for Efficient
Error-resistant DNA Self-Assembly
H. Chen, A. Goel, and C. Luhrs

Extend the proof of correctness for 3-D error correction to more general
settings.

4) Read the paper

The Computational Power of Benenson Automata.
David Soloveichik and Erik Winfree.

Read the last paragraph in the discussion at the end. Develop simple error
models and error-correction techniques for these error models.