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

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.