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.     

Conformational searches for the global minimum of protein models

The conformational space of two protein structures has been examined using a stochastic search method in an effort to locate the global minimum conformation. In order to reduce this optimization problem to a tractable level, we have implemented a simplified force field representation of the protein structure that drastically reduces the degrees of freedom. The model replaces each ammo acid (containing many atoms) with a single sphere centered on the C position. These spheres are connected by virtual bonds, producing a string of beads model of the peptide chain. This model has been coupled with our stochastic search method to globally optimize the conformation of two common structural motifs found in proteins, a 22-residue -helical hairpin and a 46-residue -barrel. The search method described further reduces the optimization problem by taking advantage of the rotational isomerisms associated with molecular conformations and stochastically explores the energy surface using internal, torsional degrees of freedom. The approach proved to be highly efficient for globally optimizing the conformation of the -helical hairpin and -barrel structure on a moderately powered workstation. The results were further verified by applying variations in the search strategy that probed the low energy regions of conformational space near the suspected global minimum. Since this method also provides information regarding the low energy conformers, we have presented an analysis of the structures populated, and brief comparisons with other work. Finally, we applied the method to globally optimize the conformation of a 9-residue peptide fragment using a popular all-atom representation and successfully located the global minimum consistent with results from previous work.     

From -spaces to algebraic theories

The paper examines semi-theories, that is, formalisms of the type of the -spaces of Segal which describe homotopy structures on topological spaces. It is shown that for any semi-theory one can find an algebraic theory describing the same structure on spaces as the original semi-theory. As a consequence one obtains a criterion for establishing when two semi-theories describe equivalent homotopy structures.

     

Protein folding in the HP model on grid lattices with diagonals

The protein folding problem, i.e., the computational prediction of the three-dimensional structure of a protein from its amino acid sequence, is one of the most important and challenging problems in computational biology. Since a complete simulation of the folding process of a protein is far too complex to handle, one tries to find an approximate solution by using a simplified, abstract model. One of the most popular models is the so-called HP model, where the hydrophobic interactions between the amino acids are considered to be the main force in the folding process, and furthermore the folding space is modeled by a two- or three-dimensional grid lattice.In this paper, we will present some approximation algorithms for the protein folding problem in the HP model on an extended grid lattice with plane diagonals. The choice of this kind of lattice removes one of the major drawbacks of the original HP model, namely the bipartiteness of the grid which severely restricts the set of possible foldings. Our algorithms achieve an approximation ratio of for the two-dimensional and of for the three-dimensional lattice. This improves significantly over the best previously known approximation ratios for the protein folding problem in the HP model on any lattice.     

Ab initio Tertiary Structure Prediction of Proteins

A daunting challenge in the area of computational biology has been to develop a method to theoretically predict the correct three-dimensional structure of a protein given its linear amino acid sequence. The ability to surmount this challenge, which is known as the protein folding problem, has tremendous implications. We introduce a novel ab initio approach for the protein folding problem. The accurate prediction of the three-dimensional structure of a protein relies on both the mathematical model used to mimic the protein system and the technique used to identify the correct structure. The models employed are based solely on first principles, as opposed to the myriad of techniques relying on information from statistical databases. The framework integrates our recently proposed methods for the prediction of secondary structural features including helices and strands, as well as -sheet and disulfide bridge formation. The final stage of the approach, which culminates in the tertiary structure prediction of a protein, utilizes search techniques grounded on the foundations of deterministic global optimization, powerful methods which can potentially guarantee the correct identification of a protein's structure. The performance of the approach is illustrated with bovine pancreatic trypsin inhibitor protein and the immunoglobulin binding domain of protein G.     

D ∞-Differentials and A ∞-Structures in Spectral Sequences

We introduce the notion of D -differential and use this notion for studying the structure of differential A -algebra on multiplicative spectral sequences. We review basic notions, constructions, and results of our previous papers, where the homotopy invariance of D -differentials was proved, D -differentials and differential perturbations of chain complexes were compared, and the connection between D -differentials and differentials of multiplicative spectral sequences was established. As a consequence of this connection, we describe a method of construction of the structure of A -coalgebra on the Milnor coalgebra dual to the Steenrod algebra immediately by the differentials of the Adams spectral sequence. We describe the method of construction of the structure of A -comodule over a Milnor A -coalgebra on homologies of an arbitrary spectrum.     

Wavelets in Banach Spaces

We describe a construction of wavelets (coherent states) in Banach spaces generated by admissible group representations. Our main targets are applications in pure mathematics while connections with quantum mechanics are mentioned. As an example, we consider operator-valued Segal–Bargmann-type spaces and the Weyl functional calculus.     

Entropy and Arithmetic Quotients for Simple Automorphism Groups of Geometric Manifolds

Let G be a connected simple Lie group, and suppose G acts on a compact real analytic manifold M. Assume that G preserves a unimodular rigid geometric structure, for example a connection and a volume form. The aim of this paper is to describe the measure theoretic structure of such actions, when -rank(G)2.     

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization

A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

Design of Civil Engineering Frame Structures Using a Monomial/Newton Hybrid Method

This paper presents an application of a monomial approximation method for solving systems of nonlinear equations to the design of civil engineering frame structures. This is accomplished by solving a set of equations representing the state known as fully-stressed design, where each member of the structure is stressed to the maximum safe allowable level under at least one of the loading conditions acting on it. The monomial approximation method is based on the process of condensation, which has its origin in geometric programming theory. A monomial/Newton hybrid method is presented which permits some of the design variables to be free in sign, while others are strictly positive. This hybrid method is well suited to the structural design application since some variables are naturally positive and others are naturally free. The proposed method is compared to the most commonly used fully-stressed design method in practice. The hybrid method is shown to find solutions that the conventional method cannot find, while doing so with less computational effort. The impact of this approach on the activity of structural design is discussed.     

Solving staircase linear programs by the simplex method, 1: Inversion

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or staircase, structure. The present paper looks at inversion routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines pricing routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.     

The chloroplast thylakoid membrane system is a molecular conveyor belt

Light drives photosynthesis, but paradoxically light is also the most variable environmental factor influencing photosynthesis both qualitatively and quantitatively. The photosynthetic apparatus of higher plants is adaptable in the extreme, as exemplified by its capacity for acclimation to very bright sunny or deeply shaded conditions. It can also respond to rapid changes in light such as sunflecks. In this paper I offer a model that i) explains the thylakoid membrane organisation into grana stacks and stroma lamellae, ii) proposes a role for rapid D1 protein turnover and LHCII phosphorylation, and iii) suggests a mechanism for photoinhibition. I argue that the photosynthetic membrane system is dynamic in three dimensions, so much so that, in the light, it is in constant motion and operates in a manner somewhat analogous to a conveyor belt. D1 protein degradation is proposed to be the motor that drives this system. Photoinhibition is suggested to be due to the arrest of D1 protein turnover.Abbreviations D1 protein photosystem II reaction centre protein - 32 kDa rapidly turning over, herbicide, Q_B binding protein - LHCII light-harvesting chlorophylla/b binding protein of PS II - PS II centres PS II complete with LHCII located in grana stacks - Pre-PS II PS II complexes consisting only of the 47, 43 kDa and D2 proteins - D2 diffusely staining, reaction centre polypeptide, 34 kDa, of PS II - CP43 chlorophylla binding protein, 43 kDa, of PSII - CP47 chlorophylla binding protein, 47 kDa, of PSII - PS II centres PS II complex with newly inserted D1 protein but devoid of LHCII     

Kronecker webs, bihamiltonian structures, and the method of argument translation

We show that manifolds which parameterize values of first integrals of integrable finite-dimensional bihamiltonian systems carry a geometric structure which we call aKronecker web. We describe two opposite direction functors between Kronecker webs and integrable bihamiltonian structures: one is left inverse to the other. Conjecturally, these two functors are mutually inverse (for small open subsets of the manifolds in question).The conjecture above is proven here when the bihamiltonian structure allows an anti-involution of a particular form. This implies the conjecture of [15] that on a dense open subset the bihamiltonian structure on is flat if is semisimple.     

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs , we describe the critical group structure completely. For Cartesian products of complete graphs , we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003     

The model theory of the field of reals with a subgroup of the unit circle

We describe definable sets in the field of reals augmented bya predicate for a finite rank multiplicative group of complexnumbers contained in the unit circle . This structure interpretsthe quotient-space / which, for infinite cyclic, is relatedto the quantum torus. Every definable set is proved to be aBoolean combination of existentially definable sets. We givea complete set of axioms for the theory of such a structure.     

Groups with π-Minimal and π-Layer Minimal Conditions. II

For an arbitrary set of prime numbers we study the properties and structure of groups satisfying the -minimal and -layer minimal conditions. In particular, we describe the structure of the almost RN-groups (and thereby that of the locally solvable groups) with these conditions. Under the assumption 2, we describe the structure of locally graded groups (and thereby that of locally finite groups) with these conditions.     

Multivariate rational data fitting: general data structure,maximal accuracy and object orientation

Sections 1 and 2 discuss the advantages of an object-oriented implementation combined with higher floating-point arithmetic, of the algorithms available for multivariate data fitting using rational functions. Section 1 will in particular explain what we mean by higher arithmetic. Section 2 will concentrate on the concepts of object orientation. In sections 3 and 4 we shall describe the generality of the data structure that can be dealt with: due to some new results virtually every data set is acceptable right now, with possible coalescence of coordinates or points. In order to solve the multivariate rational interpolation problem the data sets are fed to different algorithms depending on the structure of the interpolation points in then-variate space.This text is a preparatory publication for the development of a scientific expert system for multivariate rational interpolation. The issues addressed are relevant to the implementation of such a system.     

Parallel continuation-based global optimization for molecular conformation and protein folding

This paper presents our recent work on developing parallel algorithms and software for solving the global minimization problem for molecular conformation, especially protein folding. Global minimization problems are difficult to solve when the objective functions have many local minimizers, such as the energy functions for protein folding. In our approach, to avoid directly minimizing a difficult function, a special integral transformation is introduced to transform the function into a class of gradually deformed, but smoother or easier functions. An optimization procedure is then applied to the new functions successively, to trace their solutions back to the original function. The method can be applied to a large class of nonlinear partially separable functions including energy functions for molecular conformation and protein folding. Mathematical theory for the method, as a special continuation approach to global optimization, is established. Algorithms with different solution tracing strategies are developed. Different levels of parallelism are exploited for the implementation of the algorithms on massively parallel architectures.