The past decades have witnessed advances in genomic technology; and this has allowed laboratories to generate vast amount of biological data, including microarray gene expression data. Effective analysis of the data helps in better understanding the mechanisms behind the complex behavior of the cell. Actually, a huge body of research focuses on the role of gene regulatory networks (GRNs) in controlling the cell. However, studying the heterogeneous interactions between mRNA and miRNA has received less attention. Fortunately, revealing the targets of miRNAs started to gain some consideration from the research community. Further, integrating mRNA gene expression and miRNA expression data is receiving more attention; the target is to understand the role of miRNA in regulating mRNA in different cell contexts; this could lead to predicting miRNA targets and constructing miRNA-mRNA interaction networks. On the other hand, we have already demonstrated the power of constraint-based learning as a promising technique to learn the structure of GRN, which are homogeneous in the sense that they contain one type of nodes, namely, genes. In this study, we extend our previous work to show how constraint-based learning can be effectively applied to tackle a more challenging problem, namely, to learn the structure of heterogeneous networks, like mRNA-miRNA network. In other words, to build the whole picture of the heterogeneous interactions, we used constraint-based learning algorithms which usually perform well on sparse graphs to predict the interactions within heterogeneous networks, namely, miRNA-mRNA interactions. We are able to achieve this by extending our PCPDPr algorithm, which works on homogeneous networks. The extended version named htrPCPDPr is capable of handling networks connecting two heterogeneous sets of nodes into a bipartite graph. This way, we propose a new learning mechanism to predict miRNA targets from expression profiles of both mRNA and miRNA, in addition to sequence-based prior knowledge about the interactions. The method has been applied to different set of genes related to the Alzheimer disease; the results reported in this paper demonstrate the novelty, applicability, and effectiveness of the proposed approach.