New metabolic engineering techniques hold great potential for a range of bio-industrial applications. However, their practical use is hindered by the huge number of possible modifications, especially in eukaryotic organisms. To address this challenge, we present a methodology combining genome-scale metabolic modelling and machine learning to precisely predict cellular phenotypes starting from gene expression readouts. Our methodology enables the identification of candidate genetic manipulations that maximise a desired output--potentially reducing the number of in vitro experiments otherwise required. We apply and validate this methodology to a screen of 1,143 Saccharomyces cerevisiae knockout strains. Within the proposed framework, we compare different combinations of feature selection and supervised machine/deep learning approaches to identify the most effective model.