Europhysics Letters 94, 20005 (2011).
The instantaneous normal modes corresponding to radial hydrogen bonds
vibrations, torsion and axial compression fluctuations of a DNA
molecule model at ambient temperature are theoretically investigated.
Due to thermal disorder, normal modes are not plane waves with a
single wave number q but have a finite and frequency dependent
damping width. The density of modes rho(nu), the average
dispersion relation nu(q) as well as the coherence length xi(nu)
are analytically calculated. The Gibbs averaged resolvent is
computed using a replicated transfer matrix formalism and variational
wave functions for the ground and first excited state. Our results for
the density of modes are compared to Raman spectroscopy measurements
of the collective modes for DNA in solution and show a good agreement
with experimental data in the low frequency regime nu < 150 cm^(-1).
Radial optical modes extend over frequencies ranging
from 50 cm^(-1) to 100 cm^(-1). Torsional and compressional
acoustic modes are limited to nu < 25 cm^(-1). Normal modes are
highly disordered and coherent over a few base pairs only (xi < 15
A) in good agreement with neutron scattering experiments.
A unifying theory of the denaturation transition of DNA, driven by
temperature T or induced by an external mechanical torque Gamma
is presented. Our model couples the hydrogen-bond opening and the
untwisting of the helicoidal molecular structure. We describe
denaturation as a first order transition from B-DNA to d-DNA
phases. The coexistence region is naturally parametrized by the degree
of supercoiling sigma. The denaturation free energy, the
temperature dependence of the twist angle, the phase diagram in the
T, Gamma plane and isotherms in the sigma, Gamma plane are
calculated and show a good agreement with experimental data.
We review statistical-mechanical theories
of single-molecule micromanipulation experiments on nucleic acids.
First, models for describing polymer elasticity are
introduced. We then review how these models are used to interpret
single-molecule force-extension experiments on single-stranded
and double-stranded DNA. Depending on the force and the molecules
used, both smooth elastic behaviors and abrupt structural transitions
are observed. Third, we show how combining the elasticity
of two single nucleic acid strands with a description of the base-pairing
interactions between them explains much of the phenomenology and kinetics of
RNA and DNA `unzipping' experiments.
Advances in manipulating single DNA molecules are opening up new ways
to study the micromachines that read, replicate and repair the double helix.
The computational complexity of solving random 3-Satisfiability
(3-SAT) problems is investigated using statistical phsyics concepts
and techniques related to phase transitions, growth processes and
(real--space) renormalization flows. 3-SAT is a representative example
of hard computational tasks; it consists in knowing whether a set of
alpha N randomly drawn logical constraints involving N Boolean
variables can be satisfied altogether or not. Widely used solving
procedures, as the Davis-Putnam-Loveland-Logeman (DPLL) algorithm,
perform a systematic search for a solution, through a sequence of
trials and errors represented by a search tree. The size of the search
tree accounts for the computational complexity, i.e. the amount
of computational efforts, required to achieve resolution. In the
present study, we identify, using theory and numerical experiments,
easy (size of the search tree scaling polynomially with N) and hard
(exponential scaling) regimes as a function of the ratio alpha of
constraints per variable. The typical complexity is explicitly
calculated in the different regimes, in very good agreement with
numerical simulations. Our theoretical approach is based on the
analysis of the growth of the branches in the search tree under the
operation of DPLL. On each branch, the initial 3-SAT problem is
dynamically turned into a more generic 2+p-SAT problem, where p and
1-p are the fractions of constraints involving three and two
variables respectively. The growth of each branch is monitored by the
dynamical evolution of alpha and p and is represented by a
trajectory in the static phase diagram of the random 2+p-SAT problem.
Depending on whether or not the trajectories cross the boundary
between satisfiable and unsatisfiable phases, single branches or full
trees are generated by DPLL, resulting in easy or hard resolutions.
Our picture for the origin of complexity can be applied to other
computational problems solved by branch and bound algorithms.
Decision and optimization problems typically fall
into one of two categories for any particular solving
method or algorithm. The problem is either solved quickly (easy) or
demands an impractically long computational effort (hard).
Here we show that some
characteristic parameters of problems, such as the ratio between the
constraints to be satisfied and the adjustable variables,
can be tracked during a run of the algorithm defining a trajectory
through the parameter space. Focusing on 3-Satisfiability, a
recognized representative of hard problems, we analyze trajectories
generated by search algorithms.
These trajectories can cross well defined phases,
corresponding to domains of easy or hard instances, and allow one to
successfully predict the times of resolution.
The analysis of the solving complexity of random 3-SAT instances using
the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold
is presented. While finding a solution for such instances demands
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. We compute
analytically this exponentially small probability of easy resolutions
from a large deviation analysis of DPLL with the Generalized
Unit Clause search heuristic,
and show that the corresponding exponent is smaller
(in absolute value) than the growth exponent of the typical
resolution time. Our study therefore gives some quantitative
basis to heuristic restart solving procedures, and suggests a natural
cut-off cost (the size of the instance) for the restart.
An overview of some methods of statistical physics applied to the
analysis of algorithms for optimization problems (satisfiability of
Boolean constraints,vertex cover of graphs, decoding, ...) with
distributions of random inputs is proposed.
Two types of algorithms are analyzed: complete procedures with
backtracking (Davis-Putnam-Loveland-Logeman algorithm) and
incomplete, local search procedures (gradient descent, random
walksat, ...). The study of complete algorithms makes use of physical
concepts such as phase transitions, dynamical renormalization flow,
growth processes, ... As for local search procedures, the
connection between computational complexity and the structure of the
cost function landscape is questioned, with emphasis on the notion of
metastability.
Phase transitions, ubiquitous in condensed matter physics,
are encountered in computer science too.
The existence of critical phenomena has deep consequences
on computational complexity, that is the resolution times of
various optimization or decision problems. Concepts and methods
borrowed from the statistical physics of disordered and
out-of-equilibrium systems shed new light on the dynamical operation
of solving algorithms.
A constructive scheme for determining pure states (clusters) at very
low temperature in the 3-spins glass model on a random lattice is
provided, in full agreement with Parisi's one step replica symmetry
breaking (RSB) scheme. Proof is based on the analysis of an exact
decimation procedure. When the number c of couplings per spin is
smaller than some critical value c_d, all spins are eliminated
at the end of decimation (RS phase). In the range [c_d;c_s], a
reduced Hamiltonian is left; each ground state (GS) of the latter is a
"seed" from which a cluster of GS of the original Hamiltonian can
be reconstructed. Above c_s, GS are frustrated
with an energy per spin larger than -c.
The number of GS in each cluster, the
number of clusters, the distances between GS are calculated and
correspond to RSB predictions.
We study the weight space structure of the parity machine with binary weights
by deriving the distribution of volumes associated to the
internal representations of the learning examples. The learning behaviour
and the symmetry breaking transition are analyzed and the results
are found to be in very good agreement with extended numerical simulations.
Les transitions de phase, omnipresentes en physique de la
matiere condensee, se rencontrent aussi, de maniere
suprenante, en informatique. L'existence de phenomenes critiques a
des consequences dramatiques sur la complexite, c'est-a-dire le
temps de resolution, de nombreux problemes d'optimisation ou de
decision. Les methodes et concepts de la physique statistique des
systemes desordonnes et hors-equilibre apportent un
eclairage nouveau sur le fonctionnement dynamique des algorithmes.
Les changements brusques de comportement, bien connus en physique,
se rencontrent aussi en informatique. La transposition de l'analyse et
des concepts physiques aux problemes d'optimisation aide les mathematiciens
a etudier la complexite de resolution de ces problemes.
Biophysics: Inverse Problems
Biophysics: single molecule modelling
Biophysical review papers
Optimisation: analysis of algorithms
Optimisation review papers
Disordered systems
Neural networks
Articles en francais
Biophysics: Infotaxis
Biophysics: Inverse Problems
Biophysics: Single Molecule Modelling
Biophysical review papers
Optimisation: analysis of algorithms
Optimisation review papers
Disordered systems
Phys. Rev. Lett. 90, 047205 (2003).
Neural networks
Articles en francais
Return to home page.