Background: Yeast two-hybrid (Y2H) screens have been among the most powerful methods to detect and analyze protein-protein interactions. However, they suffer from a significant degree of false negatives, i.e. true interactions that are not detected, and to a certain degree from false positives, i.e. interactions that appear to take place only in the context of the Y2H assay. While the fraction of false positives remains difficult to estimate, the fraction of false negatives in typical Y2H screens is on the order of 70-90%. Here we present novel Y2H vectors that significantly decrease the number of false negatives and help to mitigate the false positive problem.Results: We have constructed two new vectors (pGBKCg and pGADCg) that allow us to make both C-terminal fusion proteins of DNA-binding and activation domains. Both vectors can be combined with existing vectors for N-terminal fusions and thus allow four different bait-prey combinations: NN, CC, NC, and CN. We have tested all ~4,900 pairwise combinations of the 70 Varicella-Zoster-Virus (VZV) proteins for interactions, using all possible combinations. About ~20,000 individual Y2H tests resulted in 182 NN, 89 NC, 149 CN, and 144 CC interactions. Overlap between screens ranged from 17% (NC-CN) to 43% (CN-CC). Performing four screens (i.e. permutations) instead of one resulted in about twice as many interactions and thus much fewer false negatives. In addition, interactions that are found in multiple combinations confirm each other and thus provide a quality score. This study is the first systematic analysis of such N- and C-terminal Y2H vectors.Conclusions: Permutations of C- and N-terminal Y2H vectors dramatically increase the coverage of interactome studies and thus significantly reduce the number of false negatives. We suggest that future interaction screens should use such vector combinations on a routine basis, not the least because they provide a built-in quality score for Y2H interactions that can provide a measure of reproducibility without additional assays. © 2010 Stellberger et al; licensee BioMed Central Ltd.