Protein-protein interactions (PPIs) are essential in understanding numerous aspects of protein function. Here, we significantly scaled and modified analyses of the recently developed all-vs-all sequencing (AVA-Seq) approach using a gold-standard human protein interaction set (hsPRS-v2) containing 98 proteins. Binary interaction analyses recovered 20 of 47 (43%) binary PPIs from this positive reference set (PRS), comparing favorably with other methods. However, the increase of 20× in the interaction search space for AVA-Seq analysis in this manuscript resulted in numerous changes to the method required for future use in genome-wide interaction studies. We show that standard sequencing analysis methods must be modified to consider the possible recovery of thousands of positives among millions of tested interactions in a single sequencing run. The PRS data were used to optimize data scaling, auto-activator removal, rank interaction features (such as orientation and unique fragment pairs), and statistical cutoffs. Using these modifications to the method, AVA-Seq recovered >500 known and novel PPIs, including interactions between wild-type fragments of tumor protein p53 and minichromosome maintenance complex proteins 2 and 5 (MCM2 and MCM5) that could be of interest in human disease.