Protein ubiquitination is a highly prevalent post-translational modification that regulates a wide range of cellular processes. The degree of protein ubiquitination is determined by the delicate balance between specific ubiquitin ligase (E3)-mediated ubiquitination and deubiquitinase (DUB)-mediated deubiquitination. These two types of interactions have been elegantly leveraged for drug development in the forms of PROTAC and DUBTAC technology. However, in comparison to the well-studied E3-substrate interactions, the DUB-substrate interactions (DSIs) remain insufficiently investigated. To address this challenge, we introduce a protein sequence-based ab initio method, TransDSI, which transfers proteome-scale evolutionary information to predict unknown DSIs based on insufficient training datasets. An explainable module is integrated to suggest the critical protein regions for DSIs while predicting DSIs. The performance of TransDSI outperforms multiple machine learning strategies against both cross-validation and independent test. Two predicted DUBs (USP11 and USP20) for FOXP3, along with two predicted substrates (AR and TP53) for USP22, are validated by our "wet lab" experiments, laying the groundwork for future investigations into the discovery of drug targets related to tumor immune evasion and the precise application of anti-tumor agents, respectively. TransDSI also provides a new perspective for disease omics data analysis by identifying regulatory DUBs for significantly dysregulated proteins. To facilitate the usage of TransDSI, we made the predicted human proteome-wide DSI dataset and the corresponding program codes available on github (https://github.com/LiDlab/TransDSI).