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. Non-metric distance matrix 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 wei

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

Reconstruction of Large-Scale Phylogenies

Vaibhav Rajan

The evolutionary relationships between organisms or phylogenies are fundamental to biology. They are invaluable as guiding tools to mine, organize and exploit the enormous amounts of biological data in the post-genomic era. The advent of high-throughput sequencing has resulted in whole genome data of many organisms and the need for inferring larger phylogenies ; both have necessitated the development of new methods and models in the field of phylogenetic reconstruction. The work presented in this dissertation contributes to this development. Phylogenies are most often inferred from genomic sequences – DNA or amino acid sequences. A key step before using a phylogenetic reconstruction method is that of aligning the input sequences. Finding accurate multiple sequence alignments is hard because of the heterogeneity of evolutionary signal present in the sequences—a more acute problem in whole genome sequences. A new approach to refining the phylogenetic signal of alignments is presented that identifies and eliminates phylogenetically noisy parts of the alignment in order to yield better phylogenies. The more recent model of evolution based on rearrangements (large-scale structural changes in genomes) has been a major step towards reconstructing large phylogenies. The design of models and methods in this area has presented significant mathematical challenges and some of these algorithmic and statistical questions are addressed in this work. The efficacy of simple distance-based methods are demonstrated in building accurate trees with rearrangement data, using precise estimates of true evolutionary distances. Novel methods methods are designed for robustness assessment of trees inferred by such distance-based methods. These methods are the first methods for robustness assessment for trees inferred from rearrangement data that are on par with previous such measures for trees inferred from sequence data. Further, two algorithmic problems on inversions are discussed : sorting by inversions and the inversion median problem. New algorithms and theoretical insights about the structure of the problems are described.

EPFL2012

Enabling Speech Applications using Ad Hoc Microphone Arrays

Mohammadjavad Taghizadeh

Microphone arrays are central players in hands-free speech interface applications. The main duty of a microphone array is capturing distant-talking speech with high quality. A microphone array can acquire the desired speech signals selectively by leading the beampattern towards the desired speaker. The foreseen application of ubiquitous sensing motivated by the abundance of microphone-embedded devices, such as notebooks and smart phones, raises the importance of research on ad~hoc microphone arrays. The key challenges pertain to the unknown geometry of the microphones and asynchronous recordings. The goal of this PhD thesis is to address the issues of microphone and source localization to enable beamforming for higher level speech processing tasks. To that end, we exploit the prior knowledge of the acoustical and geometrical structures underlying the ad~hoc distributed nodes to devise novel algorithms for microphone array calibration and source localization, as well as beamforming techniques for distant speech applications. To address the problem of ad~hoc microphone array calibration, the analytic diffuse sound field coherence model is investigated and its fundamental properties are studied. This model enables pairwise distance estimation for calibration of a relatively compact microphone array. We derive the mathematical framework for estimation of long pairwise distances exploiting the low-rank properties of the Euclidean distance matrix and develop a novel matrix completion algorithm for ad hoc microphone array calibration along with theoretical guarantees. Furthermore, the problem of source localization using ad~hoc microphones in a reverberant enclosure is addressed. We incorporate the image model of multipath propagation for construction of a Euclidean distance matrix. The low-rank structure of the distance matrix is exploited to identify the support of the room impulse response function and its unique map to the source location. This approach enables single-channel and distributed source localization from asynchronous recordings provided by ad hoc microphones. Along this line, we address the problem of robust microphone array placement to optimize the localization performance. Finally, spatial filtering techniques relying on beamforming are investigated for high quality speech acquisition and higher level applications. We develop beamformers for joint multi-speaker localization and voice activity detection. In addition, the broadband beampattern of a microphone array is characterized and its relation to predict the speech recognition accuracy is desired.

EPFL2015