Wednesday 30 March 2011

E anche bioinformatica è archiviata

Nucleotides bonanza
Materia assai affascinante la bioinformatica; mi sono scoperto attratto dalla biologia computazionale e da quello strato di meccanismi e processi naturali che regolano il funzionamento degli esseri viventi. In termini astratti funzioniamo esattamente nella stessa maniera in cui lavorano i computer: il DNA è un linguaggio formale, ed è ammaliante il pensiero che questo codice da interpretare contenga anche il programma stesso dell'interprete: gli enzimi che regolano la sintesi proteica sono a loro volta proteine. Uno "strano anello", per dirla alla Hofstadter.

Certo, dal punto di vista pratico si è risolto tutto in una grande abboffata di programmazione dinamica, perverse strutture dati per indicizzazione (ma con interessanti applicazioni per il web) e algoritmica di ricostruzione di alberi, ma questo è l'aspetto meno rilevante del corso.

Ben più interessante è stato studiare come a partire da quattro basi azotate si dipani un universo di specie; come la natura trovi escamotage perversi per specializzarsi e migliorarsi (per esempio, la bizzarra questione dello splicing alternativo); quante e quali siano le differenze tra i genomi delle specie, spesso assai poche!, e quali tipi di ricombinazione assurdi siano avvenuti nel corso dei millenni (il pensiero di avere codice genetico "fossile" di virus al nostro interno toglie il fiato).

Subunità "grande" di un ribosoma... bel casino!
Ma è anche straordinario vedere come le cellule armonizzino processi mostruosamente complessi, custodendo il codice genetico in modo molto geloso e protettivo, mandando in pasto a quei bestioni dei ribosomi solo delle copie sacrificabili di RNA. In particolare, il processo di traduzione cui sono delegati ha uno smaccatissimo sapore informatico: prendono in input una sequenza di RNA e la analizzano, a mo' di automa, alla ricerca di una sequenza di inizio (il codone di start); da lì in poi avviene un lookup di sotto-sequenze, per collegare tra loro gli amminoacidi corrispondenti, fino al raggiungimento del codone di stop. Tutto molto meccanico ed elementare. Non ricorda vagamente la macchina di Turing? In effetti sì, e c'è chi ha già teorizzato di exploitare il DNA per risolvere problemi di classe NP: Adlemann nel 1994 ha implementato il problema del cammino Hamiltoniano proprio su queste basi, aprendo la strada all'interessantissimo fronte del DNA computing. Chissà se tra qualche decennio i super-computer basati su filamenti saranno all'ordine del giorno.

Friday 25 March 2011

Tecnologia e controlli, tredici anni dopo

Quest'oggi ho verbalizzato l'esame di Progettazione Logica-Digitale, il fratello maggiore della materia che alle superiori veniva chiamata Controlli.

I diagrammi dei segnali, so long..

A parte VHDL, che ai "miei tempi" non si faceva, è stato un po' un tuffo nei ricordi, una sorta di ripassone. Ed è esattamente questa la parte interessante: è trascorsa più di una dozzina d'anni ma ho ancora perfettamente chiaro il funzionamento dell'elettronica digitale. La cosa non è stata vera per molti altri corsi delle superiori, il che dimostra, come ho sempre pensato, che il prof. Sforza è un insegnante davvero in gamba e le sue lezioni rappresentavano un ottimo equilibrio tra chiarezza espositiva, solidità degli argomenti e trasmissione di passione.

Impossibile che si ricordi ancora di me dopo tutti questi anni, ma mi piacerebbe tornare all'ITSOS a stringergli la mano. In ogni caso, questo 30 è dedicato a lui.

Wednesday 16 March 2011

Radiations in Tokyo, real-time

Japan is going through a wide spectrum of catastrophes: an impressive earthquake was followed by a terrible tsunami that killed thousands of people, swept away whole villages and destroyed the emergency power generators of Fukushima's cooling system, causing radiation to spread out, even to northern America. Moreover, a vulcano erupted and... there's even a bird flu warning in Chiba. Because of the laws of statistic  they will be the luckiest nation in the world for an hundred years, at the least.

Going back to radiations fear, what about the biggest town, Tokyo? Well, it seems that there's less radioacticity than in Rome, and thanks to a guy named Shinji Hiroshi we can have a proof: 



Free TV Show from Ustream

A count per minute value below 40 is perfectly normal; we read about 25, so there's nothing's wrong in Tokyo's air at the moment. Instead, Rome counts 0.25 microsievert per hour, 6 times Tokyo's actual radioactivity. Unbelieveable.

Anyway, I do consider this live stream a stunning fact: we live in a world that allow us to get (and send) any kind of information, even the most complex one, in a snap and throughout the planet. One can install an actual Geiger device, put a camera on it and broadcast its own video stream to say "everyboy calm down, we're okay". This is more than being connected. It's having mature technologies available and using them with ease, reaching any corner of the world, allowing communications that go beyond cultural differences.

Apart from all this... hang on in there Japan people. We are with you.

Friday 4 March 2011

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.