| The goal of this dissertation is to generate large libraries of non-crosshybridizing DNA oligonucleotides that can be used in DNA computing, DNA microarray design, and DNA nanotechnology fabrication. These libraries are an enabling resource for these technologies, and allow more reliable and controlled DNA-based applications.; The first accomplishment was to develop a thermodynamic model of DNA oligonucleotides consisting of three criteria for sequences in the libraries. The hybridization reaction temperature is a critical parameter for defining a non-crosshybridizing library. The simulation results indicate that the size of non-crosshybridizing libraries is influenced by the reaction temperature. There is a maximum size of the non-crosshybridizing libraries when the reaction temperature is lower than the average melting point of sequences with a specific length. The second contribution was to develop an exhaustive algorithm to search the large DNA sequence space for non-crosshybridizing sequences. The exhaustive algorithm was a feasible algorithm for solving the problem. The third contribution was to develop a filtering method to improve computational efficiency. The simulation results indicate that the filtering method does improve the computational efficiency. The fourth accomplishment was to design a multi-processor algorithm for a Linux cluster system using MPI and pthread threads. This algorithm was used to search for libraries with long sequence length. The multi-processor algorithm was both highly efficient and practical.; Finally, a series of large libraries of non-crosshybridizing DNA oligonucleotides were generated for 25°C. For the lengths of 8-mer, 10-mer, 12-mer, 14-mer and 16-mer, the sizes of the libraries are 704, 6505, 7136, 5084, and 4300 respectively. Also, the base composition in the non-crosshybridizing libraries was analyzed, and some patterns of change in base composition were discovered for changes in the reaction temperature and the length of the library. |
