Abstract: Abstract Protein interactions and complexes are important components of biological systems. Recently, two genome-wide applications of tandem affinity purification (TAP) in yeast have increased significantly the available information on interactions in complexes. Several approaches have been developed to predict protein complexes from these measurements, which generally depend heavily on additional training data in the form of known complexes. In this article, we present an unsupervised algorithm for the identification of protein complexes which is independent of the availability of such additional complex information. Based on a Bootstrap approach, we calculate intuitive confidence scores for interactions more accurate than all other published scoring methods and predict complexes with the same quality as the best supervised predictions. Although there are considerable differences between the Bootstrap and the best published predictions, the set of consistently identified complexes is more than four times as large as for complexes derived from one data set only. Our results illustrate that meaningful and reliable complexes can be determined from the purification experiments alone. As a consequence, the approach presented in this article is easily applicable to large-scale TAP experiments for any species even if few complexes are already known.