Codon pair bias is the species-specific phenomenon that pairs of adjacent codons appear in genomes with frequencies different than would be predicted under an independence assumption, and thus is indicative of evolutionary selection. The synthetic attenuated virus engineering (SAVE) paradigm to design vaccines creates weak viruses by designing coding sequences that favor underrepresented codon pairs. Designing genes which achieve the absolute minimum codon pair bias with an arbitrary codon distribution is computationally difficult. In this paper, we develop new algorithms for constructing provably optimal codon pair designs under coding constraints of up to 186 codons in under one minute. We explore a variety of search mechanisms, lower bounds, and pruning strategies to optimize sequences. Our results make it possible for the first time to truly evaluate the performance of commonly used design methods, and quantify the potential improvement possible through better algorithms.

MOTIVATION: High-throughput microarray technology can be used to examine thousands of features, such as all the genes of an organism, and measure their expression. Two important issues of microarray bioinformatics are first, how to combine the significance values for each feature across experiments with high statistical power, and second, how to control the proportion of false positives. Existing methods address these issues separately, in spite of their linked usage. RESULTS: We present a novel method (ESP) to address the two requirements in an interdependent way. It generalizes the truncated product method of Zaykin et al. to combine only those significance values which clear their respective experiment-specific false discovery restrictive thresholds, thus allowing us to control the false discovery rate (FDR) for the final combined result. Further, we introduce several concepts that together offer FDR control, high power, quality control and speed-up in meta-analysis as done by our algorithm. Computational and statistical methods of research synthesis like the one described here will be increasingly important as additional genome-wide datasets accumulate in databases. We apply our method to combine three well-known ChIP-chip transcription factor binding datasets for budding yeast to identify significant intergenic regulatory sequences for nine cell cycle regulating transcription factors, both with high power and controlled FDR.