Plant microRNAs (miRNAs) are short RNA sequences that bind to target mRNAs and
change their expression levels by redirecting their stabilities and marking them for cleavage.
In Arabidopsis thaliana, microRNAs have been shown to regulate development and are
believed to impact expression both under various conditions, such as stress and stimuli, as
well as in specific tissue types. We present a high throughput approach for associating between
microRNAs and conditions in which they act, using novel statistical and algorithmic
techniques. Our new tool, miRNAXpress, at first computes a (binary) matrix T denoting the
potential targets of microRNAs. Then, using T and an additional predefined matrix X indicating
expression of genes under various conditions, it produces a new matrix that predicts
associations between microRNAs and the conditions in which they act. Thus, the program
comprises two main modules that work in tandem to compute the desired output. The first
is an efficient target prediction engine that predicts mRNA targets of query microRNAs by
evaluating the optimal duplex that could be formed between the two: given a short query
RNA, a long target RNA, and a predefined energy cut-off threshold, the program finds and
reports all putative binding sites of the query RNA in the target RNA with hybridization
energy bounded by the predefined threshold. The second module realizes an association
operation that is computed by a method which relies on an efficient t-test to compute the
associations. The calculation of the matrix of microRNAs and their potential targets is the
computationally intensive part of the work done by miRNAXpress, and therefore an efficient
algorithm for this portion facilitates the entire process. Thus, the target prediction engine
is based on an efficient approximate hybridization search algorithm whose efficiency is the
result of utilizing the sparsity of the search space without sacrificing the optimality of the
results. The time complexity of this algorithm is almost linear in the size of a sparse set of
locations where base-pairs are stacked at a height of three or more. Thus miRNAXpress is a
novel tool for associating between microRNAs and the conditions in which they act. We employed
it to conduct a study, using the plant Arabidopsis thaliana as our model organism. By
applying miRNAXpress to 98 microRNAs and 380 conditions, some biologically interesting and statistically strong relations were discovered. For example, mir159C activity is possibly
a factor in the misresponse of nph4 mutants to phototropic stimulations.
