To approach these questions, we modeled several standard and alternative strategies for using pairwise protein interaction experiments to determine the interactome of the fruit fly Drosophila melanogaster. Our analysis shows that completing the interactome using sequential pairwise or pooled screening is probably too costly to be practical. However, this cost can be reduced substantially using a strategy that combines pooling with prioritized testing and interaction prediction. We carry out several iterations of this strategy to efficiently map 450 new high confidence interactions in Drosophila.