Tools

RNA Structure Prediction
RNA Structural Alignment
Constrained Sequence Alignment
RNA Structural Search
microRNA

Useful scripts

microRNA Bi-Targeting

FRUUT

RNA secondary structures are often represented as trees, motivating the application of tree comparison tools to the detection of structural similarities and common motifs. We generalize some current approaches for RNA tree alignment, which are traditionally confined to ordered rooted mappings, to also consider unordered unrooted mappings.

Our algorithm generalizes previous algorithms that either solved the problem in an asymmetric manner, or were restricted to the rooted and/or ordered cases. Focusing here on the most general unrooted unordered case, we show that our algorithm has an O(nTnS min(dT, dS)) time complexity, where nT and nS are the number of nodes and dT and dS are the maximum node degrees in the input trees T and S, respectively. This maintains (and slightly improves) the time complexity of previous, less general algorithms for the problem.

STRMS

Context Fold

A machine learning based RNA secondary structure prediction tool. It allows flexible scoring model design, feature weight learning, and fast folding prediction.

cAlign

A tool for pairwise sequence alignment with regular expression path constrained. The tool gets as input two sequences and a regular expression constraint and return the optimal alignment in which the path is accepted by the regular expression.

The tool is written in Java by Nimrod Milo and Tamar Pinhas at the Computer Science Department of Ben-Gurion University of the Negev, Israel.

RL-CSA

A tool for regular-language constrained pairwise global sequence alignment, which implements the following algorithms:
  1. Arslan's algorithm appearing in "A.N. Arslan, Regular expression constrained sequence alignment, in: A. Apostolico, M. Crochemore, K. Park (Eds.), Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM 2005), Lecture Notes in Computer Science, vol. 3537, Springer, Berlin, 2005, pp. 322-333".
  2. The algorithm of Chung, Lu and Tang, appearing in "Chung, Y., Lu, C., Tang, C.: Efficient algorithms for regular expression constrained sequence alignment. Information Processing Letters 103(6) (2007) 240-246".
  3. Our Steiner tree based algorithm, to appear in "Kucherov, G., Pinhas, T., Ziv-Ukelson, M.: Regular Language Constrained Sequence Alignment Revisited, Proceedings of the IWOCA 2010 conference".
  4. Our Straight-Line Program based algorithm, to appear in "Kucherov, G., Pinhas, T., Ziv-Ukelson, M.: Regular Language Constrained Sequence Alignment Revisited, Proceedings of the IWOCA 2010 conference".
The tool is written in Java by Tamar Pinhas and Uri Goldenberg at the Computer Science Department of Ben-Gurion University of the Negev, Israel, and is available for download as an eclipse project.

StemSearch

We extend BLAST approach to an efficient search for sequence RNA queries in large nucleotide databases, taking into account both sequence and structure features. Our tool is based on a structural representation of an RNA sequence by its potential stems. Potential stems in a genomic database are identified, annotated and indexed in a preprocessing stage.