We study the problem of selecting control clones in DNA array hybridization experiments. The problem arises in the OFRG method for analyzing microbial communities. The OFRG method performs classification of rRNA gene clones using binary fingerprints created from a series of hybridization experiments, where each experiment consists of hybridizing a collection of arrayed clones with a single oligonucleotide probe. This experiment produces analog signals, one for each clone, which then need to be classified, that is, converted into binary values 1 and 0 that represent hybridization and non-hybridization events. In addition to the sample rRNA gene clones, the array contains a number of control clones needed to calibrate the classification procedure of the hybridization signals. These control clones must be selected with care to optimize the classification process. We formulate this as a combinatorial optimization problem called Balanced Covering. We prove that the problem is NP-hard, and we show some results on hardness of approximation. We propose approximation algorithms based on randomized rounding, and we show that, with high probability, our algorithms approximate well the optimum solution. The experimental results confirm that the algorithms find high quality control clones. The algorithms have been implemented and are publicly available as part of the software package called CloneTools.

Fungi influence nutrient cycling in terrestrial ecosystems, as they are major regulators of decomposition and soil respiration. However, little is known about the substrate preferences of individual fungal species outside of laboratory culture studies. If active fungi differ in their substrate preferences in situ, then changes in fungal diversity due to global change may dramatically influence nutrient cycling in ecosystems. To test the responses of individual fungal taxa to specific substrates, we used a nucleotide-analogue procedure in the boreal forest of Alaska (USA). Specifically, we added four organic N compounds commonly found in plant litter (arginine, glutamate, lignocellulose, and tannin-protein) to litterbags filled with decomposed leaf litter (black spruce and aspen) and assessed the responses of active fungal species using qPCR (quantitative polymerase chain reaction), oligonucleotide fingerprinting of rRNA genes, and sequencing. We also compared the sequences from our experiment with a concurrent warming experiment to see if active fungi that targeted more recalcitrant compounds would respond more positively to soil warming. We found that individual fungal taxa responded differently to substrate additions and that active fungal communities were different across litter types (spruce vs. aspen). Active fungi that targeted lignocellulose also responded positively to experimental warming. Additionally, resource-use patterns in different fungal taxa were genetically correlated, suggesting that it may be possible to predict the ecological function of active fungal communities based on genetic information. Together, these results imply that fungi are functionally diverse and that reductions in fungal diversity may have consequences for ecosystem functioning.