TIME COMPLEXITY OF SELF-ASSEMBLY PROCESS WITH MISBEHAVING PARTS

Programmable self-assembly is the process by which autonomous parts are separately programmed to coalesce into a functional system. Self-assembly is of great importance in the natural world, molecular reactions, and robotic systems. We are interested in computing the time complexity of such process when an unknown number of particles are malfunctioning. We study a specific programming employed in the self-assembly of DNA strands. We created a simulation in Matlab with conditional programming which assimilates the natural self-assembling of monomers into a three-arm junction. A pre-specified number of parts, that each represents a specific portion of theDNA strand, are allowed to freely move within a rectangular environment. These parts then collide and follow the conditional programming mentioned above, dictating whether to attach to the colliding body or not. The result of their collision is governed by a probability constraint analogous to the varying catalyst in the real experiment. During the first trial, we found that one of Matlab’s toolboxes, Simulink, could not simulate this problem due to the lack of collision detecting. Hence, we switched over to Matlab and were able to overcome this problem. We then graphed the time complexity of the system with different densities of misbehaving parts, and noticed the number of connections decreased throughout. The use of simulations in this area could benefit the researchers greatly, since the simulations happen in a matter of seconds and no materials or supplies are needed.