Abstract: At least a quarter of all genes in most genomes contain putative transmembrane (TM) helices, and helical membrane protein interactions are a major component of the overall cellular interactome. However, current experimental techniques for large-scale detection of protein-protein interactions are biased against membrane proteins. Here, we define protein-protein interaction broadly as co-complexation, and develop a weighted-voting procedure to predict interactions among yeast helical membrane proteins by optimally combining evidence based on diverse genome-wide information such as sequence, function, localization, abundance, regulation, and phenotype. We use logistic regression to simultaneously optimize the weights of all evidence sources for best discrimination based on a set of known helical membrane protein interactions. The resulting integrated classifier not only significantly outperforms classifiers based on any single genomic feature, but also does better than a benchmark Naive Bayes classifier (using a simplifying assumption of conditional independence among features). Finally, we apply the optimized classifier genome-wide, and construct a comprehensive map of predicted helical membrane protein interactome in yeast. This can serve as a guide for prioritizing further experimental validation efforts.