DNA and fractals

DNA is a very interesting molecule, not only for its peculiar role in life. It has a solid structure and the Watson-Crick complementarity allows the construction of complex structures, by exploiting the so called sticky ends, that is, non-paired single strands that urges to be coupled with their complementary ones. 

So, if we manipulate some DNA and give it a regular shape, we can "connect" multiple pieces like a nano-puzzle. Actually, we don't do anything as the DNA makes a self-annealing and spontaneously builds nano-structures, according to the shapes we defined and a starting seed, that is, an initial DNA sequence. More precisely, the process is driven by the encoding of the sticky ends, that decides which shapes can link to each other and how. 

It is very easy to develop a simulator, so tonight I did my own. As a test, I used the "pieces" and the seed that make the DNA construct a Sierpinsky fractal.  

My simulation of DNA self-assembly, using Sierpinsky tile set

I implemented it in a couple of hours, so my simulation algorithm is largely inefficient. For instance, it makes a "scanline" testing of all cells at each iteration, instead of keeping track of the free sticky ends in the assembly.   This means that the complexity grows with lattice's size and with the number of different pieces, too much for testing serious scenarios. Furthermore, it's a strategy that makes the whole process strictly deterministic, introducing a "bias" in the annealing process which proceeds in a very regular way (from bottom to top, from left to right). In order to reproduce all the various mistakes that can happen in the annealing process, a stochastic algorithm should be employed.

By the way, the result is interesting and fascinating. The overall technique resembles the cellular automata, in particular the fact that local rules lead to emergent phenomena, complex and unpredictable.

Mission accomplished

Rastrigin's benchmark function is far more photogenic than I am

I finally got my Master's Degree in computer science, by defending a strongly interdisciplinary thesis about GPGPU-powered parameter estimation in biochemical systems. The method I propose spins around my favourite bio-inspired optimization method – the Particle Swarm Optimization – whose fitness function relies on simulations produced by Gillespie's stochastic simulation algorithm. But that's just the surface: there's a lot of complex stuff "under the hood" and plenty of room for future developments.

It has been a very interesting experience, enlightening in many ways; the most important aspects came from a human standpoint: I met, and worked with, some wonderful people from whom I've learned a lot, people I'll never cease to admire and be grateful to.

It's kinda funny, anyway: I run away from chemistry at high school, and now I'm onto it again. Strange to see how different routes ultimately lead into the same place.

The BOIDS are back in town!

During the last lesson of complex systems course, prof. Vizzari showed a crowd simulation based on BOIDS, an intriguing model invented by Craig Reynolds in 1986 that simulates bird flocks, fish schools and all that kind of self-organizing masses of living stuff. The basic model is based on three simple assumptions:

1. each boid moves toward the other flockmates (cohesion)
2. each boid moves away from crowded situations (separation)
3. each boid follows the direction of the rest of the flock (alignment)

Even in its simplest formulation the model works very well, and gives a pleasant feeling of viability. I turned the model from 3D to 2D, by putting all boids on the y=0 plane, and here we go: we have a simple crowd simulator.

There exist several approaches to crowd simulation (like cellular automata or multi-agent systems) but I do think that BOIDS have many interesting capabilities.

In fact, one of the open issues in crowd simulations is the sponteneous formation of groups because of common goals, shared costumes, socio-political aspects, familiar relationships and so on. BOIDS leave a lot of space for embedding this wide spectrum of behaviours, whilst the model itself mantains the proxemic distances between people and let them gather peacefully, by the rules decribed above.

The video I embed shows my model in a simple scenario made of four groups (yellow, red, green and blue). Green people have their own goal to follow; red and blue have a shared one. Yellow people just walk around the space, with no specific purpose. In the middle of the screen there's a strong repulsor which keeps boids away. The dynamic works as I expect: there's the formation of clusters, boids belonging to the same group tend to aggregate and find their way even in overcrowded situations. What's fascinating is the emerging, unexpected behaviour of yellow ones: some of them hold still, some dodge the crowd, many other enter the moving groups and follow them wherever they go, conditioned by the first rule.Very nice.

Hajj - the annual pilgrimage to Mecca - is
one the most interesting scenario to simulate

Still, there's a lot of work to do that I'll share with my brilliant coursemate Michele. For instance, we'll try to identify the correct parameters that fit the experimental results, incorporating Elias Canetti's proxemic dynamics as well. We also could find a way to introduce different kind of non-penetrable contraints (walls, doors, and such). There's the problem of instructing complex goals (like finding a way to an exit in non-straight situations or following a leader), with an eye to stability and realism. Finally, there's lot of optimization to do: I wrote the code as general classes and new rules can be easily introduced by pushing a new function pointer to a "rules" vector. That's very flessible, allows a very rapid prototyping but it's very inefficient: the naive algorithm is O(n²), because every boid's position needs to be compared with the rest of the flock, and every rule is computed on its own, adding a costant factor. Too slow for serious business like sport events, concerts, and religious pilgrimages, just to name a few of the typical simulations that require millions of individuals at once.