We employed an approach using oligonucleotide scanning arrays and computational analysis to conduct a systematic analysis of the interaction between catalytic nucleic acids (DNA enzymes or DNAzymes) and long RNA targets. A radio-labelled transcript representing mRNA of Xenopus cyclin B5 was hybridised to an array of oligonucleotides scanning the first 120 nucleotides of the coding region to assess the ability of the immobilised oligonucleotides to form heteroduplexes with the target. The hybridisation revealed oligonucleotides showing varying levels of signal intensities along the length of the array, reflecting on the variable accessibility of the corresponding complementary regions in the target RNA. Deoxyribozymes targeting a number of these regions were selected and tested for their ability to cleave the target RNA. The mRNA cleavage observed indicates that indeed target accessibility was an important component in the activity of deoxyribozymes and that it was important that at least one of the two binding arms was complementary to an accessible site. Computational analysis suggested that intra-molecular folding of deoxyribozymes into stable structures may also negatively contribute to their activity. 10-23 type deoxyribozymes generally appeared more active than 8-17 type and it was possible to predict deoxyribozymes with high cleavage efficiency using scanning array hybridization and computational analysis as guides. The data presented here therefore have implications on designing effective DNA enzymes.