Single-atom catalysts (SACs), containing under-coordinated single metal atoms bound to the surface of supports, are promising heterogeneous catalysts due to their intrinsic catalytic properties and efficient utilization of noble metal atoms. However, SAC stability under catalytic operation is questioned due to the tendency of metals to sinter (aggregation). Herein, we perform density functional theory (DFT) calculations to investigate the metal-support interactions (MSIs) of a series of transition-metal atoms supported on three common oxide supports (gamma-Al2O3, MgO, and MgAl2O4). Moreover, utilizing the DFT results and genetic programming, we develop a predictive model for the strength of MSIs using simple properties of both the SACs and supports. Finally, we introduce criteria for the synthetic accessibility of SACs based on thermodynamic arguments. Our computational work can guide experiments by identifying combinations of metals and oxides that can potentially lead to highly stable (and catalytically durable) SACs.