Distance matrix | EPFL Graph Search

In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the distance being used to define this matrix may or may not be a metric. If there are N elements, this matrix will have size N×N. In graph-theoretic applications, the elements are more often referred to as points, nodes or vertices. In general, a distance matrix is a weighted adjacency matrix of some graph. In a network, a directed graph with weights assigned to the arcs, the distance between two nodes of the network can be defined as the minimum of the sums of the weights on the shortest paths joining the two nodes. This distance function, while well defined, is not a metric. There need be no restrictions on the weights other than the need to be able to combine and compare them, so negative weights are used in some applications. Since paths are directed, symmetry can not be guaranteed, and if cycles exist the distance matrix may not be hollow. An algebraic formulation of the above can be obtained by using the min-plus algebra. Matrix multiplication in this system is defined as follows: Given two n × n matrices A = (a_ij) and B = (b_ij), their distance product C = (c_ij) = A ⭑ B is defined as an n × n matrix such that Note that the off-diagonal elements that are not connected directly will need to be set to infinity or a suitable large value for the min-plus operations to work correctly. A zero in these locations will be incorrectly interpreted as an edge with no distance, cost, etc. If W is an n × n matrix containing the edge weights of a graph, then W^k (using this distance product) gives the distances between vertices using paths of length at most k edges, and W^n is the distance matrix of the graph. An arbitrary graph G on n vertices can be modeled as a weighted complete graph on n vertices by assigning a weight of one to each edge of the complete graph that corresponds to an edge of G and zero to all other edges.

On the statistical physics of chains and rods, with application to multi-scale sequence-dependent DNA modelling

Alexandre Emmanuel Grandchamp

The complex mechanisms involved in cellular processes have been increasingly understood this past century and the central role of the DNA molecule has been recognized. The base pair sequence along a DNA fragment is observed not only to encode the genomic information, but also to induce locally very specific physical properties, such as significantly bent or stiff regions. These variations in the molecule constitution are for instance believed to be involved in DNA-protein recognition and in nucleosomes positioning. Modelling the sequence dependent DNA mechanical properties is consequently an important step towards understanding many biological functions. However, in a cell, vastly different length scales are involved, ranging from a few base pairs to several thousands, which makes difficult the definition of \textit{one} appropriate model. A promising strategy seems then to be given by the multi-scale modeling of sequence dependent DNA mechanics. In this framework, the sequence dependent rigid base and rigid base pair models have been proposed. In these coarse grain models either each base pair or each base is described as a rigid body configuration, which leads to either a chain or a bichain representation of the DNA molecule. A sequence dependent configurational distribution has then been parametrized, either from experimental data or directly from atomistic molecular dynamic simulations, and provides an efficient and realistic description at the scale of hundreds of base pairs. Important questions that can be studied in these models are for instance the influence of the sequence on the probability of contact of two sites, which are distant along the molecule length, or on the expectation of the relative configuration of these two sites. In this thesis, we propose to approach these physical situations both from the discrete and the continuum modeling point of view, and then to discuss in which sense they actually constitute only one multi-scale point of view. In the first part, we discuss mechanical properties of heterogeneous rigid body chains and bichains, as well as continuum rod and birods, in classical statics and in equilibrium statistical physics. Equilibirum conditions, variational principles and configurational distributions are studied for single chains and rods, and then extended to bichains and birods. We have introduced in particular an original coordinate free Hamiltonian formulation in arc-length of the birod equilibrium conditions, and the notion of the persistence matrix for the configurational moment for chains and rods. We then present deterministic and stochastic exponential Cauchy-Born rules allowing to bridge the scales between the discrete and continuum representations. In the second part, we present applications of the proposed multi-scale mechanical theory for chains and rods to sequence dependent DNA modelling. We discuss the approximation using the birod model of most probable bichain configurations satisfying prescribed end conditions. Similarly, we then present the computation of the sequence dependent frame correlation matrix and the Flory persistence vector for chains using a continuum rod model. In addition, a homogenization method is proposed. These results are believed to constitute a substantial improvement in the multi-scale modeling of DNA mechanics.

EPFL2016

On the statistical physics of chains and rods, with application to multi-scale sequence-dependent DNA modelling

Alexandre Emmanuel Grandchamp

EPFL2016