Abstract Motivation: Currently, the best RNA–RNA interaction prediction tools are based on approaches that consider both the inter- and intramolecular interactions of hybridizing RNAs. While accurate, these methods are too slow and memory-hungry to be employed in genome-wide RNA target scans. Alternative methods neglecting intramolecular structures are fast enough for genome-wide applications, but are too inaccurate to be of much practical use. Results: A new approach for RNA–RNA interaction was developed, with a prediction accuracy that is similar to that of algorithms that explicitly consider intramolecular structures, but running at least three orders of magnitude faster than RNAup. This is achieved by using a combination of precomputed accessibility profiles with an approximate energy model. This approach is implemented in the new version of RNAplex. The software also provides a variant using multiple sequences alignments as input, resulting in a further increase in specificity. Availability: RNAplex is available at www.bioinf.uni-leipzig.de/Software/RNAplex. Contact: htafer@bioinf.uni-leipzig.de; ivo@tbi.univie.ac.at Supplementary information: Supplementary data are available at Bioinformatics Online.