Hamiltonian path | EPFL Graph Search

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete. Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the icosian game, now also known as Hamilton's puzzle, which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structure based on roots of unity with many similarities to the quaternions (also invented by Hamilton). T

A path integral formalism of DNA looping probability

Ludovica Cotta-Ramusino

In this thesis we describe a path integral formalism to evaluate approximations to the probability density function for the location and orientation of one end of a continuum polymer chain at thermodynamic equilibrium with a heat bath. We concentrate on those systems for which the associated energy density is at most quadratic in its variables. Our main motivation is to exploit continuum elastic rod models for the approximate computation of DNA looping probabilities. We first re-derive, for a polymer chain system, an expression for the second order correction term due to quadratic fluctuations about a unique minimal energy configuration. The result, originally stated for a quantum mechanical system by G. Papadopoulos (1975), relies on an elegant algebraic argument that carries over to the real-valued path integrals of interest here. The conclusion is that the appropriate expression can be evaluated in terms of the energy of the minimizer and the inverse square root of the determinant of a matrix satisfying a certain non-linear system of differential equations. We then construct a change of variables, which establishes a mapping between the solutions of the aforementioned non-linear Papadopoulos equations and a matrix satisfying an initial value problem for the classic linear system of Jacobi equations associated with the second variation of the energy functional. This conclusion is trivial if no cross-term is present in the second variation, but ceases to be so otherwise. Cross-terms are always present in the application of rod models to DNA. We therefore can conclude that the second order fluctuation correction term to the probability density function for a chain is always given by the inverse square root of the determinant of a matrix of solutions to the Jacobi equations. We believe this conclusion to be original for the real-valued case when the second-variation involves cross-terms. Similar results are known for quantum mechanical systems, and, in this context, a connection between the so called Van-Hove-Morette determinant, which involves partial derivatives of the classical action with respect to the boundary values of the configuration variable, and the Jacobi determinant have also been established. We next apply the formula described above to the specific context of rods, for which the configuration space is that of framed curves, or curves in R3 × SO(3). An immediate application of our theory is possible if the rod model encompasses bend, twist, stretch and shear. However the constrained case, where the rod is considered to be inextensible and unshearable, is more standard in polymer physics. In this last case, our results are more delicate as the Lagrangian description breaks down, and the Hamiltonian formulation must be invoked. It is known that the unconstrained local minimizers approach constrained minimizers as the coefficients in the shear and extension terms of the energy are sent to infinity. Here we observe that the Hamiltonian form of the unconstrained Jacobi system similarly has a limit, so that the fluctuation correction in the path integral can still be expressed as the square root of the determinant of a matrix solution of a set of Jacobi equations appropriate to the constrained problem. As in reality DNA or biological macromolecules are certainly at least slightly shearable and extensible, the limit of the fluctuation correction is undoubtedly physically appropriate. The above theory provides a computationally highly tractable approach to the estimation of the appropriate probability density functions. For application to sequence-dependent models of DNA the associated systems of equations has non-constant coefficients, which is of little consequence for a numerical treatment, but precludes the possibility of finding closed form expressions. On the other hand the theory also applies to simplified homogeneous models. Accordingly, we conclude by applying our approach in a completely analytic and closed-form way to the computation of the approximate probability density function for a uniform, non-isotropic, intrinsically straight and untwisted rod to form a circular loop.

EPFL2008

Optimal control of geodesics in Riemannian manifolds

Roland Rozsnyo

The aim of this dissertation is to solve numerically the following problem, denoted by P : given a Riemannian manifold and two points a and b belonging to that manifold, find a tangent vector T at a, such that expa(T) = b, assuming that T exists. This problem is set under an optimal control formulation, which requires the definition of an objective function and a space of control, the choice of a method for the calculation of the descent direction of that function in the space of control and the use of an optimization algorithm to find its minimum, which corresponds to the solution of the original problem by construction. Several techniques are necessary to be put together, coming from the fields of geometry, numerical analysis and optimization. The first part will concern a recalling of the mathematical context in which this formulation takes place. The general principles of optimal control will also be given. In the second part, we will present an intrinsic formulation of the optimal control problem associated to P, based on Jacobi fields, which will play the role of the so called adjoint state. This derivation leads to necessary optimality conditions. We will illustrate explicitly that formulation by treating the specific case of Riemannian manifolds with constant sectional curvature. Then, we will derive the optimal control problem in coordinates, not only to check the intrinsic formulation but also to reveal how it is hidden behind the expressions in coordinates. Their use reveals some quantities whose interpretation may be given this way. Moreover, we will show that more possibilities exist to chose the cost function and the control space in coordinates. In a second step, an alternative approach will consider the Hamiltonian formulation of geodesics. This is an incursion into symplectic geometry. We will then reformulate the Riemannian optimal control problem in its Hamiltonian version. In the third part, the numerical methods used for solving P will be presented. The discretization imposes the definition of new discrete optimal control problems. The technique shows that the discrete adjoint state equation strongly depends on the numerical scheme used to solve the direct problem. We will give a collection of numerical computations in the specific case of parametric piece of surfaces, where the surface can be defined by one or several Bézier patches, each one corresponding to a chart, which is representative of a Riemannian manifold. We will compare the different numerical approaches. The last but one part will be devoted to the interesting application of wooden roof building, where the structure is made of wooden boards, with geodesic trajectories on the designed piece of surface. The Geos (Geodesic solver) software has been developed for that purpose. After having introduced some specific numerical methods used in the code, we present the Geos application interface (AI) developed as a tool for the conception of such a roof. We then show an existing wooden structure built according to that mean. Finally, we will summarize the results of our research and discuss future possible prospects.

EPFL2007

Looping probabilities of elastic chains: A path integral approach

Ludovica Cotta-Ramusino, John Maddocks

We consider an elastic chain at thermodynamic equilibrium with a heat bath, and derive an approximation to the probability density function, or pdf, governing the relative location and orientation of the two ends of the chain. Our motivation is to exploit continuum mechanics models for the computation of DNA looping probabilities, but here we focus on explaining the novel analytical aspects in the derivation of our approximation formula. Accordingly, and for simplicity, the current presentation is limited to the illustrative case of planar configurations. A path integral formalism is adopted, and, in the standard way, the first approximation to the looping pdf is obtained from a minimal energy configuration satisfying prescribed end conditions. Then we compute an additional factor in the pdf which encompasses the contributions of quadratic fluctuations about the minimum energy configuration along with a simultaneous evaluation of the partition function. The original aspects of our analysis are twofold. First, the quadratic Lagrangian describing the fluctuations has cross-terms that are linear in first derivatives. This, seemingly small, deviation from the structure of standard path integral examples complicates the necessary analysis significantly. Nevertheless, after a nonlinear change of variable of Riccati type, we show that the correction factor to the pdf can still be evaluated in terms of the solution to an initial value problem for the linear system of Jacobi ordinary differential equations associated with the second variation. The second novel aspect of our analysis is that we show that the Hamiltonian form of these linear Jacobi equations still provides the appropriate correction term in the inextensible, unshearable limit that is commonly adopted in polymer physics models of, e. g. DNA. Prior analyses of the inextensible case have had to introduce nonlinear and nonlocal integral constraints to express conditions on the relative displacement of the end points. Our approximation formula for the looping pdf is of quite general applicability as, in contrast to most prior approaches, no assumption is made of either uniformity of the elastic chain, nor of a straight intrinsic shape. If the chain is uniform the Jacobi system evaluated at certain minimum energy configurations has constant coefficients. In such cases our approximate pdf can be evaluated in an entirely explicit, closed form. We illustrate our analysis with a planar example of this type and compute an approximate probability of cyclization, i.e., of forming a closed loop, from a uniform elastic chain whose intrinsic shape is an open circular arc.

2010