Small regulatory non-coding RNAs (sRNAs) have emerged as an important class of regulators across all kingdoms of life. In prokaryotes, the majority of the known sRNAs bring about regulation by base pairing with their target mRNAs, resulting in either increased or decreased stability of the target transcripts. Based on their mode of action, these sRNAs are further sub-categorized into two categories: cis-acting and trans-acting. While cis-acting sRNAs are encoded on the antisense strand of their targets, trans-acting sRNAs bear no identifiable relationship with the loci of their targets. The lack of complementarity between trans-acting sRNAs and their target mRNA sequences; along with the added complexity that each sRNA can have multiple targets and some mRNAs are targets for multiple sRNAs, makes the discovery of such interactions a formidable challenge. The research presented in this thesis describes a knowledge-based machine-learning model based on the popular random forest algorithm developed for the prediction of novel interactions in bacteria. The model was trained on a high quality dataset of experimentally verified sRNA-target interactions obtained from the literature. The prediction model is shown to be applicable on a genome-wide scale. The algorithm is further extended to filter predictions using random forests intrinsic similarity measure. Finally, the selected predictions were validated experimentally in Escherichia coli for several known trans-encoded sRNAs, leading to the identification of novel regulatory interactions.