| Oligonucleotide Fingerprinting of Ribosomal RNA Genes (OFRG) is a high-throughput technique for analyzing microbial communities. OFRG classifies rRNA gene clones from environmental samples into taxonomic clusters based on binary fingerprints created from hybridizations with a collection of oligonucleotide probes. In this work, we identify several computational challenges arising in the OFRG analysis and propose methods to solve them. The first problem is the prediction of probe reliability. To solve it, we use the method of nonparametric kernel density estimation. Our experimental results show that our method leads to a significant decrease in the number of unreliable probes.; Second, we study the problem of selecting control clones for hybridization experiments. We formalize it as a combinatorial optimization problem called Balanced Covering. We propose approximation algorithms based on randomized rounding and we show that, with high probability, our algorithms approximate well the optimal solution. The experimental results confirm that the algorithms find high quality control clones.; Next, we present a new systematic method to select sequence-selective PCR primers for amplifying target DNA clones used in array experiments. We introduce a software package called PRISE (PRimer SElector) to guide a user in an interactive fashion through the design process, gradually arriving at a list of primer pairs with desired properties. The experimental results show that this software package improves the quality of the resulting primers.; Finally, we study the fingerprint reconstruction problem that arises in the next generation OFRG method based on the microbead technology. We formulate it as a combinatorial optimization problem, prove the NP -hardness, and propose a heuristic to solve it. |
