Maps representing the binary interactions among proteins have become valuable tools for understanding how proteins work together to mediate biological processes. One of the most effective methods for detecting biologically important protein interactions has been the yeast two-hybrid system. Here we present an efficient two-hybrid strategy to facilitate construction of protein interaction maps on a genome-wide scale. The strategy begins with two arrays of yeast expressing known proteins fused to either a DNA binding domain (BD), or a transcription activation domain (AD). The fusion proteins are conditionally expressed using regulated promoters that can be repressed during construction and amplification of the yeast arrays. Interaction assays are conducted in two phases. In the first phase, small pools of AD strains are mated with the array of BD strains. In the second phase, individual BD strains are mated with appropriate subsets of the AD array corresponding to positive pools in the first phase. This strategy has several advantages over previously described approaches, including the ability to detect interactions with proteins that inhibit yeast growth or that activate transcription as BD fusions. Moreover, by minimizing the number of mating operations and sequencing reactions needed to test large sets of binary interactions, this strategy is more efficient than either matrix or library screening approaches. We also present a three-dimensional pooling scheme to further increase the efficiency of large-scale two-hybrid analyses.