Computational prediction of protein-protein interactions (PPIs) is crucial for understanding cell biology and drug development, offering a promising alternative to costly and time-consuming experimental methods. While the original GenPPi software represented an advance in ab initio PPI network prediction from bacterial genomes, its reliance on high sequence similarity limited it. In this work, we introduce the GenPPi 1.5 and enhance prediction capabilities. We incorporated a Random Forest (RF) algorithm, trained on 60 biophysical features derived from amino acid propensity indices, to overcome the previous limitation by classifying protein similarity even in low sequence identity scenarios (targeting > 65% identity). Furthermore, to address the computational complexity arising from the increased number of potential interactions generated by the RF model, especially within extensive conserved phylogenetic profiles, we developed and integrated the Reduced Interaction Sampling (RIS) algorithm. RIS stochastically samples interactions within these extensive profiles, optimizing performance for complete genome analysis. Our multifaceted methodology included integrating RF for efficient similarity classification and implementing RIS to reduce the computational burden. We evaluated the effectiveness through extensive simulations across different configurations (operational modes, Top N selected nodes, number of analyzed genomes). We rigorously assessed the network stability and structural integrity using topological metrics and statistical tests. Results demonstrate that RF integration significantly broadens GenPPi's predictive power. Application to the Buchnera aphidicola genome revealed an overlap of up to 62% with interactions documented in the STRING database, validating prediction accuracy. Analysis of the RIS algorithm showed that while introducing some randomness, critical node identification remains robust, particularly for Top N values [≥] 100, indicating that the edge reduction does not significantly compromise network integrity. In conclusion, combining Machine Learning and RIS represents a significant advancement. GenPPi 1.5 overcomes the high-similarity dependency while efficiently handling complex genomes, providing a robust and scalable alignment-free solution for PPI prediction. GenPPi is available at https://genppi.facom.ufu.br/ and on GitHub: https://github.com/santosardr/genppi and allows users to train custom models for specific genomic contexts.