RNAmountAlign
is a web server for
for RNA sequence/structure pairwise alignment, that runs in
O(n
3) time and O(n
2) space. The software,
freely available, additionally returns a p-value (transformable to expect value E) based on Karlin-Altschul statistics as well as parameter fitting.
Position-specific incremental mountain height, computed over the ensemble
of secondary structures, represents the (thermodynamic) structural
information for a given RNA sequence. Absolute value of the
difference between incremental ensemble mountain heights is then
translated into an equivalent structural similarity measure STRSIM used in
the computation. RNAmountAlign then implements quadratic time local,
global and global/semiglobal (query search) alignment using a
weighted combination of sequence and structural similarity. The method
is described in the submitted paper.
RNAiFold3.0
is a web server for the design of synthetic
RNA molecules using constraint programming (with optional large neighborhood
search) to solve the inverse folding problem -- i.e. given one or more
target RNA secondary structures S
1, ..., S
k,
and temperatures T
1, ..., T
k, determine
one or more sequences whose minimum free energy (MFE) secondary structure
temperatures T
1, ..., T
k is
S
1, ..., S
k. Optionally, sequence constraints can
be stiuplated: minimum and maximum GC-content, maximum number of consecutive
occurrences of each nucleotide A,C,G,U. As well structure constraints can
be stipulated, thus requiring all structures to have a minimum [resp. maximum]
number of AU, or GC, or GU base pairs within a stipulated range. Global
or local portions of the secondary structures at various temperatures can
be required to additionally be compatible with certain user-given structures.
RNAiFold has been used to design synthetic hammerhead ribozymes and
thermo-IRES elements (temperature switches for internal translation start
site), all shown to be functional by biochemical assays of collaborators.
Some references follow.
-
Juan Antonio Garcia-Martin, Peter Clote, Ivan Dotu.
RNAiFold: A constraint programming algorithm for RNA inverse folding
and molecular design.
J Bioinform Comput Biol 11(2): 1350001, 2013.
-
Garcia-Martin JA, Dotu I, Clote P.
RNAiFold 2.0 A web server and software to design custom
and Rfam-based RNA molecules.
Nucleic Acids Research Web Server issue, 2015,
doi: 10.1093/nar/gkv460,
RNAiFold 2.0 A web server and software to design custom
and Rfam-based RNA molecules.
-
Garcia-Martin JA, Dotu I, Fernandez-Chamorro J,
Lozano G, Ramajo J, Martinez-Salas E, Clote P.
RNAiFold2T: Constraint Programming design of
thermo-IRES switches.
Bioinformatics. 2016 Jun 15;32(12):i360-i368.
doi: 10.1093/bioinformatics/btw265.
-
Dotu I, Garcia-Martin JA, Slinger BL, Mechery V, Meyer MM, Clote P.
Complete RNA inverse folding: computational design
of functional hammerhead ribozymes.
Nucleic Acids Res. 2015 Feb 1;42(18):11752-62. doi: 10.1093/nar/gku740. Epub 2014 Sep 10.
MS2distance
is a web server that computes the exact
the MS2 distance between two user-given secondary structures of
a user-given RNA sequence. In RNA folding kinetics using
kinfold, elementary-step moves use either the MS2 (default) or
MS1 move set, where MS2[resp. MS1] allows the addition or removal or
shift [resp. addition, removal] of a single base pair. The MS2 [resp. MS1 ]
distance between secondary structures s and t is defined to be the minimum
path length to refold s to t, where a move from MS2[resp. MS1 ] is applied
in each step. The MS1 distance between s and t is trivially equal to
the cardinality of the symmetric difference of s and t, i.e the number of
base pairs belonging to one structure but not the other; in contrast, the
computation of MS2 distance is highly non-trivial. We describe algorithms
to compute the shortest MS2 folding trajectory between any two given
RNA secondary structures. Some partial results suggest that computing
MS2 distance may be NP-complete, hence our method involved defining a directed
graph called "coflict digraph", and solving an Integer Linear Programmiong
(ILP) problem associated with the conflict digraph. Details of the method
are described in the following submitted paper.
RNAexpNumNbors
is a web server that computes the expected
degree of the network of RNA secondary structures of a given RNA -- i.e.
the expected number of neighbors taken over all secondary structures.
Here, we consider two move sets: MS1 and MS2. A neighbor of structure S
with respect to MS1 is a structure T obtained by adding or removing a
single base pair, whereas a neighbor of structure S with respect to MS2
is a structure T obtained by adding, removing or shifting a
single base pair. In addition to programs to compute the expected degree,
we also provide a program that implements kinetic folding with respect to
MS1 using either the Gillespie algorithm or the Monte Carlo algorithm --
two related but distinct methods to approximate the mean first passage
time (MFPT). See
-
Clote P.
Expected degree of RNA secondary structure networks.
J Comput Chem. 2015 Jan 15;36(2):103-17. doi: 10.1002/jcc.23776. Epub 2014 Nov 7
-
P. Clote, A. Bayegan.
Network properties of the ensemble of RNA structures.
PLoS One. 2015 Oct 21;10(10):e0139476. doi: 10.1371/journal.pone.0139476.
-
P. Clote, A. Bayegan.
RNA folding kinetics using Monte Carlo and Gillespie algorithms.
submitted.
RNAsc
is a web server that computes RNA
secondary structure with user-input chemical/enzymatic probing data,
especially Selective 2'-hydroxyl acylation analyzed by primer extension
(SHAPE) or inline-probing data. Unlike other methods, RNAsc computes
the partition function and minimum energy structure by applying Boltzmann
derived weights applied to every nucleotide position. See
Integrating chemical foot
printing data into RNA secondary structure prediction,
by K. Zarringhalam, M.M. Meyer, I. Dotu, J.H. Chuang, P.Clote.
PLoS One. 2012;7(10):e45160. doi: 10.1371/journal.pone.0045160.
Epub 2012 Oct 16.
Expected5to3distance
is a web server that computes
the expected distance between the 5' and 3' ends of the Boltzmann
ensemble of all secondary structures for a given RNA sequence. See
Expected distance between terminal nucleotides of RNA
secondary structures.
P. Clote, Y. Ponty, J.-M. Steyaert.
J Math Biol. 2012 Sep;65(3):581-99. Epub 2011 Oct 9.
RNApagenumber
is a web server that computes the optimal
"page number" of an RNA pseudoknotted or tertiary structure,
input as a PDB file or .ct (mfold connect) file. See
On the Page Number of Secondary Structures with Pseudoknots.
Peter Clote, Stefan Dobrev, Ivan Dotu, Evangelos Kranakis,
Danny Krizanc, Jorge Urrutia.
J Math Biol. 2012 Dec;65(6-7):1337-57. doi: 10.1007/s00285-011-0493-6.
where we show that computing the page number is NP-complete, and describe
an approximation algorithm as well as an exact solution using constraint
programming (CP). The web server is an implementation of the CP algorithm,
which can compute the optimal page number for large RNAs within seconds --
for example the 23S chain PDB file 1FFK of length 2,922 for the
Haloarcula marismortui ribosome.
RNAlocopt
is a web server that computes the partition function
and samples structures from the ensemble of
locally optimal
secondary structures of a given RNA sequence. Here, a locally optimal
secondary structure is one for which the free energy can
not
be lowered by the addition or removal of a single base pair (i.e. a
kinetic trap in unit resolution energetics).
The algorithm is described in
the paper
Computing the partition function for kinetically trapped RNA
secondary structures.
W.A. Lorenz, P. Clote.
Public Library of Science One (PLoS ONE), (2011)
PLoS ONE 6(1): e16178. doi:10.1371/journal.pone.0016178.
RNAborMEA
computes the
maximum expected accurate
δ-neighbors of a given RNA secondary structure for a given RNA
sequence. Here, a structure T is a δ-neighbor of a given structure
S, if S can be transformed into T by a minimum number δ of edit
operations, where an edit operation consists of removing or adding a single
base pair (i.e. if the base pair distance between S and T is δ).
The algorithm is described in
the paper
Peter Clote, Feng Lou, William A. Lorenz.
Maximum expected accuracy structural neighbors of an RNA secondary structure.
BMC Bioinformatics BMC Bioinformatics. 2012 Apr 12;13 Suppl 5:S.
RNA-WL
is an implementation of the Wang-Landau non-Boltzmannian
sampling algorithm to approximate the partition function for RNA secondary
structures. It is well-known that Monte-Carlo Boltzmannian sampling can be
used to compute an approximation to the minimum free energy
pseudoknotted structure for a given RNA sequence (allowing all possible
pseudoknots). Since it is also NP-complete to compute the
partition function for pseudoknotted RNA structures, Wang-Landau sampling
can be used to estimate the density of states (from which the partition
function can be computed).
The algorithm is described in the paper
"Thermodynamics of RNA structures by Wang-Landau sampling."
Feng Lou, Peter Clote.
Bioinformatics 2010 Jun 15;26(12):278-86.
RNApathfinder
is a web server to compute near-optimal folding pathways between
two given secondary structures for a given RNA sequence. Since this
problem is known to be NP-complete, our main algorithm,
RNAtabupath
uses the TABU local search heuristic. The web server
includes both downloadable source code for several algorithms, as well
as a web engine to compute pathways. Intended applications concern
folding pathways for RNA conformational switches.
RNApathfinder and the
RNAtabupath algorithm are
described in the paper
I. Dotú, W.A. Lorenz, P. Van Hentenryck, P. Clote.
Nucleic Acids Res. 2010 Mar 1;38(5):1711-22.
RNAmutants
is a web server to perform mutational analysis for a given RNA sequence.
Previous methods relied on exhaustively enumerating k-point mutant
sequences and subsequently applying mfold or RNAfold, a procedure with
run time exponential in k. In contrast, RNAmutants computes the
minimum free energy structure and Boltzmann partition function for all
k-point mutants, for 0 ≤ k ≤ K, with run time
O(K
2n
3). RNAmutants is described in the paper
Jerome Waldispühl, Srinivas Devadas, Bonnie Berger, Peter Clote.
Efficient algorithms for probing the RNA mutation landscape.
PLoS Comput Biol. 2008 Aug 8;4(8):e1000124.
LocalMove
is a web server to compute 3-dimensionals cubic and face-centered
cubic lattice fits for both RNA and protein. Various levels of granularity
are supported: backbone and several coarse grain models (CA, C1',P, etc.).
Since optimal on-lattice fit for the cubic lattice is NP-complete,
LocalMove implements the Monte-Carlo with simulated annealing, with a
variety of user-definable parameters. LocalMove web server produces
animated movies of the folding procedure, and stores job IDs for future
reference. The web server and algorithm are described in
Y. Ponty, R. Istrate, E. Porcelli, P. Clote.
LocalMove: Computing on-lattice fits for biopolymers.
Nucleic Acids Res. (Web Server Issue) (2008).
FFTbor
FFTbor
is a web server to compute the Boltzmann probability
Zk/Z, for all values of k=0,1,... where
Zk is the sum of Boltzmann factors of all
secondary structures, whose base pair distance from the user-specified
starting structure is k. The algorithm is described in
Using the Fast Fourier Transform to Accelerate the Computational Search for RNA Conformational Switches.
,
Evan Senter, Saad Sheikh, Ivan Dotu, Yann Ponty, Peter Clote,
PLoS One, December 19, 2012,
https://doi.org/10.1371/journal.pone.0050506.
Using complex roots of unity and the Fast Fourier Transform, the
new thermodynamics-based algorithm, FFTbor, computes the Boltzmann
probability that secondary structures differ by
k base pairs
from a user-specified initial structure of a given RNA sequence.
RNAbor
RNAbor
is a web server to compute secondary structural neighbors of a given RNA
structure. The algorithm is described in
Boltzmann probability of RNA structural neighbors and riboswitch detection.
,
Eva Freyhult; Vincent Moulton; Peter Clote,
Bioinformatics. 2007 Aug 15;23(16):2054-62. Epub 2007 Jun 14.
Abstract,
PDF
The web server is described in
RNAbor: A web server for RNA structural neighbors.
E. Freyhult, V. Moulton, P. Clote.
Nucleic Acids Res. 2007 Jul 1;35(Web Server issue):W305-9. Epub 2007 May 25.
DIAL
DIAL is a
web server for 3-dimensional RNA structural alignment (global and local)
and for motif detection. DIAL (DIhedral ALignment)
runs in time that is quadratic in input length by performing an alignment
which accounts for (i) pseudo-dihedral and/or dihedral angle similarity,
(ii) nucleotide sequence similarity,
(iii) nucleotide base-pairing similarity. The algorithm and web server are
described in
DIAL: a web server for the pairwise alignment of two RNA three-dimensional
structures using nucleotide, dihedral angle and base-pairing similarities
,
F. Ferre; Y. Ponty; W. A. Lorenz; Peter Clote
Nucleic Acids Res. 2007 Jul 1;35(Web Server issue):W659-68. Epub 2007 Jun 13.
Abstract ,
Full Text,
PDF.
transFold
transFold is a
web server for beta-barrel supersecondary structure prediction.
Unlike other software which employ machine learning methods,
transFold uses multi-tape S-attribute grammars to describe the
space of all possible supersecondary structures, then applies dynamic
programming to compute the global energy minimum structure.
The algorithm, due to J. Waldispühl, is described in
Predicting transmembrane beta-barrels and
interstrand residue interactions from sequence,
J. Waldispühl, B. Berger, P. Clote, J.-M. Steyaert,
Proteins 65(1):61-74 (2006).
BibTeX entry
The web server, implemented by J. Waldispühl, is described in
transFold: a Web Server for predicting the structure
and residue contacts of transmembrane beta-barrels,
J. Waldispühl, B. Berger, P. Clote, J.-M. Steyaert,
Nucleic Acids Res. 34(Web Server Issue):189-193 (2006).
BibTeX entry
Boltzmann Time Warping
Boltzmann Time Warping is software to compute the
(symmetric, pairwise, all-against-all) time warping distance for
gene expression time series values between two data sets.
The user uploads two tab-separated textfiles of gene expression time
series data, and the web server computes the time warping distance
as well as the Boltzmann pair probability in the optimal alignment.
Boltzmann pair probabilities provide a measure of potential
biological significance of aligned positions.
The new algorithms are due to P. Clote and described in
Symmetric time warping, Boltzmann pair probabilities and
functional genomics
,
P. Clote, J. Straubhaar,
J Math Biol. 53(1):135-61 (2006).
BibTeX entry
and the web server is described in
BTW: A web server for Boltzmann time warping of gene expression
time series,
F. Ferre, P. Clote,
Nucleic Acids Res. 34(Web Server issue):W482-5 (2006).
BibTeX entry
Energy of k-point mutants of RNA
RNAmutants is software to predict
the expected energy of k-point mutants of a given RNA sequence, and
as well to compute the k-superoptimal secondary
structure, or secondary structure whose free energy is a minimum over
all pointwise mutants of a given RNA involving at most k mutated sites.
The algorithms are described in
Energy landscape of k-point mutants of an RNA molecule by
P. Clote, J. Waldispuhl, B. Behzadi, J.-M. Steyaert,
Bioinformatics, Vol. 21, 4140-4147, 2005.
DiANNA: Diresidue amino acid neural network for
cysteine oxidation state and disulfide bond connectivity
DiANNA is software to predict both
cysteine oxidation state and which half-cystines partner with which
other half-cystines in disulfide bonds. The neural net design and
implementation is due to F. Ferre and P. Clote, and is described in
the papers:
Disulfide connectivity prediction using secondary
structure information and diresidue frequencies ,
F. Ferre and P. Clote,
Bioinformatics 21(10):2336-2346 (2005),
and
DiANNA: a web server for disulfide connectivity prediction ,
F. Ferre, P. Clote,
Nucleic Acids Research,
Nucleic Acids Res. 2005 Jul 1;
33(Web Server issue):W230-232.
The extension to a ternary classifier using Support Vector Machines
(SVMs), due to F. Ferre, is described in
DiANNA1.1webServer.pdf
DiANNA 1.1: An extension of the DiANNA web server
for ternary cysteine classification,
F. Ferre, P. Clote,
Nucleic Acids Res. 34(Web Server issue):W182-5 (2006).
BibTeX entry
RNA energy spectrum computation (density of states)
RNALOSS
is a web server to compute the number and relative density of states
of RNA Locally Optimal Secondary Structures. The underlying algorithm
runs in O(n
4) time and O(n
3) space, and computes
the (relative) density of states for the entire energy
spectrum for the Nussinov-Jacobson energy for RNA secondary structures
on an input RNA. The algorithm and webserver are described in
An efficient algorithm to compute the landscape of
locally optimal RNA secondary structures with respect to the
Nussinov-Jacobson energy model ,
P. Clote,
Journal of
Computational Biology 12(1) 2005 83--101, and
RNALOSS: A web server for RNA locally optimal secondary structures ,
P. Clote,
Nucleic Acids Research,
web server W1-W5 (2005).
rna dinucleotide shuffle
Dishuffle is a web
interface to a local implementation of the Altschul-Erikson
dinucleotide shuffle algorithm, described in
"Significance of nucleotide sequence alignments: A method for random
sequence permutation that preserves dinucleotide and codon usage",
S.F. Altschul and B.W. Erikson,
Mol. Biol. Evol., 2(6):526--538, 1985. This algorithm was used
in the paper,
Structural RNA has lower folding energy than random RNA of the
same dinucleotide frequency, by
P. Clote, F. Ferre, E. Kranakis, D. Krizanc in
RNA 11(5):578-591 (2005).
Refined global and local alignments
Boltzmann Alignment
performs a (local) Smith-Waterman alignment of two input proteins,
then calculates the Boltzmann probability of any two aligned residues,
or residue aligned with gap symbol. This idea was first published in
"Stochastic Pairwise Alignments",
U. Mueckstein, I. L. Hofacker, and P. F. Stadler,
Bioinformatics 18 (suppl) 2002,
though it was later independently discovered and implemented in
April 2003 by P. Clote.
See
"Biologically significant sequence alignments using
Boltzmann probabilities" by P. Clote.