Biomolecular Computing – Combinatorial Algorithms and Laboratory Experiments (Doctoral Thesis)

Questa tesi raccoglie i risultati della ricerca dell'autrice nell'ambito del calcolo molecolare, e li presenta in un ordine che rispetta quello cronologico in cui sono stati conseguiti. La tesi presenta sia modelli teorici di computazioni molecolari che nuovi algoritmi DNA, corrispondenti a procedure di una certa rilevanza biologica. In particolare, sono stati individuati specifici metodi di estrazione DNA, di ricombinazione DNA, e di mutagenesi. Segue una lista dei principali risultati conseguiti, per la maggior parte proposti nei sei capitoli centrali. Nel contesto dei modelli teorici, e soprattutto come frutto di collaborazioni internazionali, si sono trovati i) un modello a membrana per il reclutamento selettivo dei leucociti, ii) una macchina a registri DNA, e iii) un insieme di vincoli di tipo ``forbidding-enforcing'' su grafi, che descrivono processi di self-assembly. Nel contesto delle speculazioni combinatoriche e algoritmiche su nuovi metodi di manipolazione DNA, principalmente sviluppate a Verona, sono stati proposti due nuovi algoritmi basati su XPCR, di estrazione e mutagenesi DNA. Un lavoro principalmente autonomo ha portato invece a formulare un nuovo algoritmo di ricombinazione basato su XPCR e un algoritmo di estrazione basato su operazioni enzimatiche. Infine, sono stati condotti tre tipi di esperimenti di laboratorio per testare tutti gli algoritmi basati su XPCR. Un aspetto saliente della tesi puo' essere ricercato nel lavoro di interazione, filtraggio, e traduzione, tra il lato teorico e quello sperimentale della ricerca presentata. Sebbene non la si possa considerare ricerca informatica ``ortodossa'', si direbbe un lavoro prezioso dal punto di vista scientifico, senz'altro esaltante, in quanto mette in luce una natura sperimentale delle stringhe (biologiche, modellate da quelle formali) e degli algoritmi. Il capitolo 4, centrale nella tesi, e' un semplice esempio di come speculazioni del tutto teoriche, quali dei specifici risultati di combinatorica, possano essere da un lato motivati e ispirati da, ma dall'altro anche molto utili e significativi per, un esperimento di calcolo col DNA in un laboratorio di biologia molecolare.

The idea of unconventional computing has fired many imaginations, and many researchers regard it as a revolution in information processing. In this respect, several directions are addressed in the first chapter of this thesis. An overview about molecular computing is given, in terms of state of the art and main problems faced, and conclusive notes are proposed along with bibliographical references and curiosities provoked by a few questions. The middle chapters are essentially the core of the thesis. A variant of the Polymerase Chain Reaction, called XPCR, is introduced to implement null context splicing rules on DNA strings. This was experimentally tested in different situations, as implementation basis for algorithms of generation, extraction, and mutagenesis, and the laboratory experiments are reported in a chapter of experimental results. The simple technology of this approach is interesting in itself, and it has different applications in biological contexts, beyond the DNA computing problems that have motivated it. It takes the advantages and the efficiency of an enzymatic elongation technique, and, it proves convenient with respect to the standard methods in terms of speed and feasibility. XPCR-based algorithms turned out to be easy-to-implement methods supported by interesting mathematical facts. An analysis of the PCR process is presented as well, with a novel extraction method based on XPCR procedure. This was successfully tested by experiments, and its performance has been then improved, at least at a theoretical level by a biotechnology, where a variant avoiding formations of chimers was introduced, together with the XPCR based mutagenesis algorithm.