microRNAs (miRNAs) are short non-coding RNAs with regulatory functions in various biological processes including cell differentiation, development and oncogenic transformation. They can bind to mRNA transcripts of protein-coding genes and repress their translation or lead to mRNA degradation. Conversely, the transcription of miRNAs is regulated by proteins including transcription factors, co-factors, and messenger molecules in signaling pathways, yielding a bidirectional regulatory network of gene and miRNA expression. We describe here a least angle regression approach for uncovering the functional interplay of gene and miRNA regulation based on paired gene and miRNA expression profiles. First, we show that gene expression profiles can indeed be reconstructed from the expression profiles of miRNAs predicted to be regulating the specific gene. Second, we propose a two-step model where in the first step, sequence information is used to constrain the possible set of regulating miRNAs and in the second step, this constraint is relaxed to find regulating miRNAs that do not rely on perfect seed binding. Finally, a bidirectional network comprised of miRNAs regulating genes and genes regulating miRNAs is built from our previous regulatory predictions. After applying the method to a human cancer cell line data set, an analysis of the underlying network reveals miRNAs known to be associated with cancer when dysregulated are predictors of genes with functions in apoptosis. Among the predicted and newly identified targets that lack a classical miRNA seed binding site of a specific oncomir, miR-19b-1, we found an over-representation of genes with functions in apoptosis, which is in accordance with the previous finding that this miRNA is the key oncogenic factor in the mir-17-92 cluster. In addition, we found genes involved in DNA recombination and repair that underline its importance in maintaining the integrity of the cell.