MicroRNAs (miRNAs) are small non-coding RNAs that post-transcriptionally regulate gene expression by altering the translation efficiency and/or stability of targeted mRNAs. In vertebrates, more than 50% of all protein-coding RNAs are assumed to be subject to miRNA-mediated control, but current high-throughput methods that reliably measure miRNA-mRNA interactions either require prior knowledge of target mRNAs or elaborate preparation procedures. Consequently, experimentally validated interactions are relatively rare. Furthermore, in silico prediction based on sequence complementarity of miRNAs and their corresponding target sites suffers from extremely high false positive rates. Apparently, sequence complementarity alone is often insufficient to reflect the complex post-transcriptional regulation of mRNAs by miRNAs, which is especially true for animals. Therefore, combined analysis of small non-coding and protein-coding RNAs is indispensable to better understand and predict the complex dynamics of miRNA-regulated gene expression. Single-nucleotide polymorphisms (SNPs) and alternative polyadenylation (APA) can affect miRNA binding of a given transcript from different individuals and tissues, and especially APA is currently emerging as a major factor that contributes to variations in miRNA-mRNA interplay in animals. In this review, we focus on the influence of APA and SNPs on miRNA-mediated gene regulation and discuss the computational approaches that take these mechanisms into account.