4,247 research outputs found
Slow nucleic acid unzipping kinetics from sequence-defined barriers
Full text linkRecent experiments on unzipping of RNA helix-loop structures by force have
shown that about 40-base molecules can undergo kinetic transitions between two
well-defined `open' and `closed' states, on a timescale = 1 sec [Liphardt et
al., Science 297, 733-737 (2001)]. Using a simple dynamical model, we show that
these phenomena result from the slow kinetics of crossing large free energy
barriers which separate the open and closed conformations. The dependence of
barriers on sequence along the helix, and on the size of the loop(s) is
analyzed. Some DNAs and RNAs sequences that could show dynamics on different
time scales, or three(or more)-state unzipping, are proposed.Comment: 8 pages Revtex, including 4 figure
Adaptive Cluster Expansion for Inferring Boltzmann Machines with Noisy Data
Get PDFWe introduce a procedure to infer the interactions among a set of binary
variables, based on their sampled frequencies and pairwise correlations. The
algorithm builds the clusters of variables contributing most to the entropy of
the inferred Ising model, and rejects the small contributions due to the
sampling noise. Our procedure successfully recovers benchmark Ising models even
at criticality and in the low temperature phase, and is applied to
neurobiological data.Comment: Accepted for publication in Physical Review Letters (2011
Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
Full text linkA large deviation analysis of the solving complexity of random
3-Satisfiability instances slightly below threshold is presented. While finding
a solution for such instances demands an exponential effort with high
probability, we show that an exponentially small fraction of resolutions
require a computation scaling linearly in the size of the instance only. This
exponentially small probability of easy resolutions is analytically calculated,
and the corresponding exponent shown to be smaller (in absolute value) than the
growth exponent of the typical resolution time. Our study therefore gives some
theoretical basis to heuristic stop-and-restart solving procedures, and
suggests a natural cut-off (the size of the instance) for the restart.Comment: Revtex file, 4 figure
On Safe Folding
Get PDFIn [3] a general fold operation has been introduced for definite programs wrt computed answer substitution semantics. It differs from the fold operation defined by Tamaki and Sato in [26,25] because its application does not depend on the transformation history. This paper extends the results in [3] by giving a more powerful sufficient condition for the preservation of computed answer substitutions. Such a condition is meant to deal with the critical case when the atom introduced by folding depends on the clause to which the fold applies. The condition compares the dependency degree between the fonding atom and the folded clause, with the semantic delay between the folding atom and the ones to be folded. The result is also extended to a more general replacement operation, by showing that it can be decomposed into a sequence of definition, general folding and unfolding operations
Large Pseudo-Counts and -Norm Penalties Are Necessary for the Mean-Field Inference of Ising and Potts Models
Full text linkMean field (MF) approximation offers a simple, fast way to infer direct
interactions between elements in a network of correlated variables, a common,
computationally challenging problem with practical applications in fields
ranging from physics and biology to the social sciences. However, MF methods
achieve their best performance with strong regularization, well beyond Bayesian
expectations, an empirical fact that is poorly understood. In this work, we
study the influence of pseudo-count and -norm regularization schemes on
the quality of inferred Ising or Potts interaction networks from correlation
data within the MF approximation. We argue, based on the analysis of small
systems, that the optimal value of the regularization strength remains finite
even if the sampling noise tends to zero, in order to correct for systematic
biases introduced by the MF approximation. Our claim is corroborated by
extensive numerical studies of diverse model systems and by the analytical
study of the -component spin model, for large but finite . Additionally
we find that pseudo-count regularization is robust against sampling noise, and
often outperforms -norm regularization, particularly when the underlying
network of interactions is strongly heterogeneous. Much better performances are
generally obtained for the Ising model than for the Potts model, for which only
couplings incoming onto medium-frequency symbols are reliably inferred.Comment: 25 pages, 17 figure
Relaxation and Metastability in the RandomWalkSAT search procedure
Full text linkAn analysis of the average properties of a local search resolution procedure
for the satisfaction of random Boolean constraints is presented. Depending on
the ratio alpha of constraints per variable, resolution takes a time T_res
growing linearly (T_res \sim tau(alpha) N, alpha < alpha_d) or exponentially
(T_res \sim exp(N zeta(alpha)), alpha > alpha_d) with the size N of the
instance. The relaxation time tau(alpha) in the linear phase is calculated
through a systematic expansion scheme based on a quantum formulation of the
evolution operator. For alpha > alpha_d, the system is trapped in some
metastable state, and resolution occurs from escape from this state through
crossing of a large barrier. An annealed calculation of the height zeta(alpha)
of this barrier is proposed. The polynomial/exponentiel cross-over alpha_d is
not related to the onset of clustering among solutions.Comment: 23 pages, 11 figures. A mistake in sec. IV.B has been correcte
From Large Scale Rearrangements to Mode Coupling Phenomenology
Full text linkWe consider the equilibrium dynamics of Ising spin models with multi-spin
interactions on sparse random graphs (Bethe lattices). Such models undergo a
mean field glass transition upon increasing the graph connectivity or lowering
the temperature. Focusing on the low temperature limit, we identify the large
scale rearrangements responsible for the dynamical slowing-down near the
transition. We are able to characterize exactly the dynamics near criticality
by analyzing the statistical properties of such rearrangements. Our approach
can be generalized to a large variety of glassy models on sparse random graphs,
ranging from satisfiability to kinetically constrained models.Comment: 4 pages, 4 figures, minor corrections, accepted versio
Inferring DNA sequences from mechanical unzipping data: the large-bandwidth case
Get PDFThe complementary strands of DNA molecules can be separated when stretched
apart by a force; the unzipping signal is correlated to the base content of the
sequence but is affected by thermal and instrumental noise. We consider here
the ideal case where opening events are known to a very good time resolution
(very large bandwidth), and study how the sequence can be reconstructed from
the unzipping data. Our approach relies on the use of statistical Bayesian
inference and of Viterbi decoding algorithm. Performances are studied
numerically on Monte Carlo generated data, and analytically. We show how
multiple unzippings of the same molecule may be exploited to improve the
quality of the prediction, and calculate analytically the number of required
unzippings as a function of the bandwidth, the sequence content, the elasticity
parameters of the unzipped strands
- …
