Deciphering the interactions within and between the three major components of living organisms, DNA, RNA and Protein, is at the heart of biological research. New large-scale experimental methods have dramatically advanced genome-wide detection of protein-protein, protein-DNA, protein-RNA and protein-mediated RNA-RNA interactions. However, at present there is no large-scale method that could detect all RNA-RNA interactions independent of a mediator protein, or when the mediator protein is unknown. Attaining such a method is of utmost importance and is very timely, as it is now evident that RNA-RNA interactions play central roles in cellular life. In particular, hundreds of expressed small RNA (sRNA) molecules were discovered in both pro- and eukaryotes, many of which act as posttranscriptional regulators of gene expression by base-pairing with their mRNA targets. It seems that in many organisms the layer of posttranscriptional regulation is as widespread as transcription regulation, presenting a major challenge towards achieving functional and mechanistic understanding of this regulation level. Here we propose to develop an innovative methodology for genome-wide detection of the sRNA targetome, all mRNA targets of cellular sRNAs. This new methodology combines in vivo structural probing with deep sequencing and is independent of protein considerations. We will apply this method to deciper the sRNA targetome of the model organism Escherichia coli, which encodes over 100 sRNAs. We will use the sRNA targetome data as the foundation for a systematic ‘bottom-up’ computational analysis of multifaceted aspects of sRNA-mediated posttranscriptional regulation, encompassing the basic underlying rules of sRNA-mRNA target recognition, the design principles of the posttranscriptional regulatory network and its integration with the transcriptional and metabolic networks, and the evolution of posttranscriptional regulation.