On the bioinformatics or: computer science's pillars

One of the most interesting facets of bioinformatics is that pushes computer science towards its limit. When you deal with huge data sets, a poorly implemented algorithm or the choice of the wrong data structure leads to inevitable failure.

Screenshot above shows some information about the costs of a piece of software I'm developing for prof. Besozzi, that executes a slight variation of Aho-Corasick on saccharomyces cerevisiae's genome, looking for a bunch of relevant nucleotides sequences. The data-set isn't impressive, just 36MB, and loading it into main memory takes about 10MB. The remaining 128 megabytes are due to the tables produced by algorithm and the huge vectors that store the results (>7 million of matches).

This being the ratio, one can easily foresee that bigger data sets (eg.: the human genome) could easily get out of hand, requiring more resources than one can afford! I'm more than satisfied in terms of time complexity (it's a linear algorithm, therefore optimal), but some further optimization could (has) to be done on the spatial side.

Fascinating complexity

Here we go, another little step towards Master Degree! "Complex systems" is achieved and with full score, thanks to a crowd simulation based on Craig Reynolds' BOIDS and rendered by my own 3D engine "PLT".

I love emerging models - as one can easily foresee by reading the name of this blog - and BOIDS is no exception. A few rules and parameters, two constraints and a bit of randomness and we have a hell of algorithm, almost chaotic and showing a lot of unexpected and non-designed behaviours: formation of queues, spontaneous groups, and so on. Michele and I did a validation study, basing on the previous works of Crystals' Project, a joint effort in crowds simulation. Our model worked well, mathing the expected timings and behaviours, at least with reasonable agents' density; being BOIDS a simple reactive multi-agent system, our pedestrian do not embedded sufficient "intelligence" and can easily fall in many subtle cul-de-sac. It's a good result, anyway, and leaves a lot of space for further investigation.

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.

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.

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.