A Geometric Build-Up Algorithm for Solving the Molecular Distance Geometry Problem with Sparse Distance Data

Nuclear magnetic resonance (NMR) structure modeling usually produces a sparse set of inter-atomic distances in protein. In order to calculate the three-dimensional structure of protein, current approaches need to estimate all other missing distances to build a full set of distances. However, the estimation step is costly and prone to introducing errors. In this report, we describe a geometric build-up algorithm for solving protein structure by using only a sparse set of inter-atomic distances. Such a sparse set of distances can be obtained by combining NMR data with our knowledge on certain bond lengths and bond angles. It can also include confident estimations on some missing distances. Our algorithm utilizes a simple geometric relationship between coordinates and distances. The coordinates for each atom are calculated by using the coordinates of previously determined atoms and their distances. We have implemented the algorithm and tested it on several proteins. Our results showed that our algorithm successfully determined the protein structures with sparse sets of distances. Therefore, our algorithm reduces the need of estimating the missing distances and promises a more efficient approach to NMR structure modeling.     

A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances

We describe a linear-time algorithm for solving the molecular distance geometry problem with exact distances between all pairs of atoms. This problem needs to be solved in every iteration of general distance geometry algorithms for protein modeling such as the EMBED algorithm by Crippen and Havel (Distance Geometry and Molecular Conformation, Wiley, 1988). However, previous approaches to the problem rely on decomposing an distance matrix or minimizing an error function and require O(n²) to O(³) floating point operations. The linear-time algorithm will provide a much more efficient approach to the problem, especially in large-scale applications. It exploits the problem structure and hence is able to identify infeasible data more easily as well.     

An updated geometric build-up algorithm for solving the molecular distance geometry problems with sparse distance data

An updated geometric build-up algorithm is developed for solving the molecular distance geometry problem with a sparse set of inter-atomic distances. Different from the general geometric build-up algorithm, the updated algorithm re-computes the coordinates of the base atoms whenever necessary and possible. In this way, the errors introduced in solving the algebraic equations for the determination of the coordinates of the atoms are controlled in the intermediate computational steps. The method for re-computing the coordinates of the base atoms based on the estimation on the root-mean-square deviation (RMSD) is described. The results of applying the updated algorithm to a set of protein structure problems are presented. In many cases, the updated algorithm solves the problems with high accuracy when the results of the general algorithm are inadequate.     

A Stochastic/Perturbation Global Optimization Algorithm for Distance Geometry Problems

We present a new global optimization approach for solving exactly or inexactly constrained distance geometry problems. Distance geometry problems are concerned with determining spatial structures from measurements of internal distances. They arise in the structural interpretation of nuclear magnetic resonance data and in the prediction of protein structure. These problems can be naturally formulated as global optimization problems which generally are large and difficult. The global optimization method that we present is related to our previous stochastic/perturbation global optimization methods for finding minimum energy configurations, but has several key differences that are important to its success. Our computational results show that the method readily solves a set of artificial problems introduced by Moré and Wu that have up to 343 atoms. On a set of considerably more difficult protein fragment problems introduced by Hendrickson, the method solves all the problems with up to 377 atoms exactly, and finds nearly exact solution for all the remaining problems which have up to 777 atoms. These preliminary results indicate that this approach has very good promise for helping to solve distance geometry problems.     

A least-squares approach for discretizable distance geometry problems with inexact distances

A branch-and-prune (BP) algorithm is presented for the discretizable distance geometry problem in $$\mathbb {R}^K$$ with inexact distances. The algorithm consists in a sequential buildup procedure where possible positions for each new point to be localized are computed by using distances to at least K previously placed reference points and solving a system of quadratic equations. Such a system is solved in a least-squares sense, by finding the best positive semidefinite rank K approximation for an induced Gram matrix. When only K references are available, a second candidate position is obtained by reflecting the least-squares solution through the hyperplane defined by the reference points. This leads to a search tree which is explored by BP, where infeasible branches are pruned on the basis of Schoenberg’s theorem. In order to study the influence of the noise level, numerical results on some instances with distances perturbed by a small additive noise are presented.     

Calculating particle-to-wall distances in unstructured computational fluid dynamic models

Knowledge of particle deposition is relevant in biomedical engineering situations such as computational modeling of aerosols in the lungs and blood particles in diseased arteries. To determine particle deposition distributions, one must track particles through the flow field, and compute each particle's distance to the wall as it approaches the geometric surface. For complex geometries, unstructured tetrahedral grids are a powerful tool for discretizing the model, but they complicate the particle-to-wall distance calculation, especially when non-linear mesh elements are used. In this paper, a general algorithm for finding minimum particle-to-wall distances in complex geometries constructed from unstructured tetrahedral grids will be presented. The algorithm is validated with a three-dimensional 90° bend geometry, and a comparison in accuracy is made between the use of linear and quadratic tetrahedral elements to calculate the minimum particle-to-wall distance.     

Derivatives with respect to metrics and applications: subgradient marching algorithm

This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N ² log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.     

Recent advances on the interval distance geometry problem

We discuss a discretization-based solution approach for a classic problem in global optimization, namely the distance geometry problem (DGP). We focus our attention on a particular class of the DGP which is concerned with the identification of the conformation of biological molecules. Among the many relevant ideas for the discretization of the DGP in the literature, we identify the most promising ones and address their inherent limitations to application to this class of problems. The result is an improved method for estimating 3D structures of small proteins based only on the knowledge of some distance restraints between pairs of atoms. We present computational results showcasing the usefulness of the new proposed approach. Proteins act on living cells according to their geometric and chemical properties: finding protein conformations can be very useful within the pharmaceutical industry in order to synthesize new drugs.     

Global optimization for sum of geometric fractional functions

This paper presents an efficient branch and bound algorithm for globally solving sum of geometric fractional functions under geometric constraints, which arise in various practical problems. By using an equivalent transformation and a new linear relaxation technique, a linear relaxation programming problem of the equivalent problem is obtained. The proposed algorithm is convergent to the global optimal solution by means of the subsequent solutions of a series of linear programming problems. Numerical results are reported to show the feasibility of our algorithm.     

Low-Dimensional Embedding with Extra Information

A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry (e.g., distances, angles, and/or orientations), and the goal is to reconstruct the global geometry from this partial information. More precisely, we are given a graph, the approximate lengths of the edges, and possibly extra information, and our goal is to assign two-dimensional coordinates to the vertices such that the (multiplicative or additive) error on the resulting distances and other information is within a constant factor of the best possible. We obtain the first pseudo-quasipolynomial-time algorithm for this problem given a complete graph of Euclidean distances with additive error and no extra information. For general graphs, the analogous problem is NP-hard even with exact distances. Thus, for general graphs, we consider natural types of extra information that make the problem more tractable, including approximate angles between edges, the order type of vertices, a model of coordinate noise, or knowledge about the range of distance measurements. Our pseudo-quasipolynomial-time algorithm for no extra information can also be viewed as a polynomial-time algorithm given an "extremum oracle" as extra information. We give several approximation algorithms and contrasting hardness results for these scenarios.     

颗粒增强复合材料的几何模型数值模拟方法研究

为了在细观层次上模拟混凝土和土石混合体等颗粒增强复合材料,假设颗粒为凸多面体.首先研究由随机八面体随机变形得到任意凸多面体及其参数方程的方法,然后研究凸多面体内部与外部的判定条件、点到多面体的距离和两多面体之间距离的计算方法,从而得到了一个生成具有大量多面体随机分布区域的方法.为了提高模拟区域中多面体的含量,还给出了下降算法.实验表明:可以按二级配生成多面体含量达35%（体积比）的模拟区域,为从细观层次研究混凝土、土石混合体等颗粒增强复合材料,提供了创建几何模型的方法.     

G1 Smoothing Solid Objects by Bicubic Bezier Patches

A general and unified method is presented for generating a wide range of 3-D objects by smoothing the vertices and edges of a given polyhedron with arbitrary topology using bicubic Bezier patches. The common solution to the compatibility equations of $G^1$ geometric continuity between two Bezier patches is obtained and employed as the foundation of this new method such that this new solid and surface model is reliable and compatible with the solid modeling and surface modeling systems in the most common use. The new method has been embedded in an algorithm supported by our newly developed solid modeling system MESSAGE. The performance and implementation of this new algorithm show that it is efficient, flexible and easy to manipulate.     

Approximate Maximum Likelihood Estimation of Circle Parameters

The estimation of a circles centre and radius from a set of noisy measurements of its circumference has many applications. It is a problem of fitting a circle to the measurements and the fit can be in algebraic or geometric distances. The former gives linear equations, while the latter yields nonlinear equations. Starting from estimation theory, this paper first proves that the maximum likelihood (ML), i.e., the optimal estimation of the circle parameters, is equivalent to the minimization of the geometric distances. It then derives a pseudolinear set of ML equations whose coefficients are functions of the unknowns. An approximate ML algorithm updates the coefficients from the previous solution and selects the solution that gives the minimum cost. Simulation results show that the ML algorithm attains the Cramer-Rao lower bound (CRLB) for arc sizes as small as 90°. For arc sizes of 15° and 5° the ML algorithm errors are slightly above the CRLB, but lower than those of other linear estimators.Communicated by L. C. W. Dixon     

可视球面多分辨率网格建模与求解

针对任意视点下的球面多分辨率网格建模与求解困难的情况,提出了屏幕细分自适应算法.该算法将计算限制在与视点相关的可视球面区域,求解得到视点相关的可视球面多分辨率网格,并在PC机上实现了可视球面多分辨率网格的三维表现.     

A strictly improving linear programming Phase I algorithm

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called basic) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs.When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.     

An Attractor-Repeller approach to floorplanning

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying height and width) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard combinatorial optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distances that arise in this derivation. Computational results demonstrating the potential of our approach are presented.     

A branch and bound algorithm for locating input and output points of departments on the block layout

We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems.     

薄体结构温度场的高阶边界元分析

分析了二维问题边界元法3节点二次单元的几何特征,区分和定义了源点相对高阶单元的Ⅰ型和Ⅱ型接近度.针对二维位势问题高阶边界元中奇异积分核,构造出具有相同Ⅱ型几乎奇异性的近似核函数,在几乎奇异积分单元上分离出积分核中主导的奇异函数部分.原积分核扣除其近似核函数后消除几乎奇异性,成为正则积分核函数,并采用常规Gauss数值方法计算该正则积分;对奇异核函数的积分推导出解析公式,从而建立了一种新的边界元法高阶单元几乎奇异积分半解析算法.应用该算法计算了二维薄体结构温度场算例,计算结果表明高阶单元半解析算法能充分发挥边界元法优势,显著提高计算精度.     

On Steiner trees and minimum spanning trees in hypergraphs

The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.     

Classification Trees With Bivariate Linear Discriminant Node Models

This article introduces a classification tree algorithm that can simultaneously reduce tree size, improve class prediction, and enhance data visualization. We accomplish this by fitting a bivariate linear discriminant model to the data in each node. Standard algorithms can produce fairly large tree structures because they employ a very simple node model, wherein the entire partition associated with a node is assigned to one class. We reduce the size of our trees by letting the discriminant models share part of the data complexity. Being themselves classifiers, the discriminant models can also help to improve prediction accuracy. Finally, because the discriminant models use only two predictor variables at a time, their effects are easily visualized by means of two-dimensional plots. Our algorithm does not simply fit discriminant models to the terminal nodes of a pruned tree, as this does not reduce the size of the tree. Instead, discriminant modeling is carried out in all phases of tree growth and the misclassification costs of the node models are explicitly used to prune the tree. Our algorithm is also distinct from the “linear combination split” algorithms that partition the data space with arbitrarily oriented hyperplanes. We use axis-orthogonal splits to preserve the interpretability of the tree structures. An extensive empirical study with real datasets shows that, in general, our algorithm has better prediction power than many other tree or nontree algorithms.