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.
