Regulatory RNAs often unfold their action via RNA-RNA interaction. Transcriptional gene silencing by means of siRNAs and miRNA as well as snoRNA directed RNA editing rely on this mechanism. ncRNA regulation in bacteria is mainly based upon RNA duplex formation. Finding putative target sites for newly discovered ncR- NAs is a lengthy task as tools for cofolding RNA molecules like RNAcofold and RNAup have a run time proportional to O((n + m)3) which makes them unpractical for whole genome search. We present a new program, RNAplex, especially designed to quickly find possible hybridization sites for a query RNA in large RNA databases. In contrast to earlier approaches, RNAplex uses a slightly different energy model which reduces the computational time by a factor 65 compared to RNAhybrid without loss of sensitivity.