M.Sc Thesis

M.Sc StudentLipson Doron
SubjectOptimization Problems in Design of Oligonucleotides for
Hybridization Based Methods
DepartmentDepartment of Computer Science
Supervisors ASSOCIATE PROF. Zohar Yakhini
PROF. Uri Sivan


Synthetic oligonucleotides play an important role in a wide range of experimental techniques based on DNA hybridization. In this thesis I present several computational methods for optimizing the design of oligonucleotides for hybridization-based methods. In hybridization assays, such as expression profiling, oligonucleotides are used as probes for detecting and quantifying DNA/RNA in a sample. A major consideration in oligonucleotide probe design is ensuring its specificity for a single target sequence against a wide range of different sequences that appear in the background. I show that using an indexed search it is possible to efficiently map the specificity of candidate probes, taking into account knowledge of the distribution of the background sequences and different thermodynamic models. By means of this method, specificity maps for the entire S. cerevisiae transcriptome are obtained. Different optimization considerations are required when designing oligonucleotides for complex hybridization reactions, such as DNA computing or multiplex PCR. In this type of methodology a large number of oligonucleotides are used as substrates for the given reaction. The design process should take into account the interdependence between the different oligonucleotides taking part in the reaction, and prevent undesired cross-hybridization between them. A scheme for designing oligonucleotides for complex reactions is proposed, composed of exhaustive calculation of interference between subgroups of oligonucleotides based on an interference model, reduction of the problem to an interference graph and derivation of an experimental design by appropriate heuristics for the respective graph-theoretic problems. We show implementation of this scheme for two experimental scenarios - a molecular implementation of a shift register (a DNA computing problem) and multiplex PCR primer design, using genetic algorithm based heuristics for the maximum clique in a hypergraph and representative subgraph coloring problems. For both scenarios we show simulated results as well as preliminary empirical results.