On the Intractability of Protein Folding with a Finite Alphabet of Amino Acids

We describe a proof of NP-hardness for a lattice protein folding model whose instances contain protein sequences defined with a fixed, finite alphabet that contains 12 amino acid types. This lattice model represents a protein's conformation as a self-avoiding path that is embedded on the three-dimensional cubic lattice. A contact potential is used to determine the energy of a sequence in a given conformation; a pair of amino acids contributes to the conformational energy only if they are adjacent on the lattice. This result overcomes a significant weakness of previous intractability results, which do not examine protein folding models that have a finite alphabet of amino acids together with physically interesting conformations. Received June 1, 1997; revised March 13, 1998.     

Protein structure prediction problem: formalization using quaternions

The authors discuss the formalization of protein tertiary structure prediction problem based on Dill’s HP-model. Three-dimensional discrete lattices and different approaches to representing paths on them are the subjects of investigation. Two ways of path encoding are proposed and formalized, one of which is based on quaternions.     

Field‐Aligned and Lattice‐Guided Tetrahedral Meshing

We present a particle‐based approach to generate field‐aligned tetrahedral meshes, guided by cubic lattices, including BCC and FCC lattices. Given a volumetric domain with an input frame field and a user‐specified edge length for the cubic lattice, we optimize a set of particles to form the desired lattice pattern. A Gaussian Hole Kernel associated with each particle is constructed. Minimizing the sum of kernels of all particles encourages the particles to form a desired layout, e.g., field‐aligned BCC and FCC. The resulting set of particles can be connected to yield a high quality field‐aligned tetrahedral mesh. As demonstrated by experiments and comparisons, the field‐aligned and lattice‐guided approach can produce higher quality isotropic and anisotropic tetrahedral meshes than state‐of‐the‐art meshing methods.     

The Protein Structure Prediction Problem: A Constraint Optimization Approach using a New Lower Bound

The protein structure prediction problem is one of the most (if not the most) important problem in computational biology. This problem consists of finding the conformation of a protein with minimal energy. Because of the complexity of this problem, simplified models like Dill's HP-lattice model [15], [16] have become a major tool for investigating general properties of protein folding. Even for this simplified model, the structure prediction problem has been shown to be NP-complete [5], [7]. We describe a constraint formulation of the HP-model structure prediction problem, and present the basic constraints and search strategy. Of course, the simple formulation would not lead to an efficient algorithm. We therefore describe redundant constraints to prune the search tree. Furthermore, we need bounding function for the energy of an HP-protein. We introduce a new lower bound based on partial knowledge about the final conformation (namely the distribution of H-monomers to layers).     

Efficient LBM Visual Simulation on Face-Centered Cubic Lattices

The Lattice Boltzmann method (LBM) for visual simulation of fluid flow generally employs cubic Cartesian (CC) lattices such as the D3Q13 and D3Q19 lattices for the particle transport. However, the CC lattices lead to suboptimal representation of the simulation space. We introduce the face-centered cubic (FCC) lattice, fD3Q13, for LBM simulations. Compared to the CC lattices, the fD3Q13 lattice creates a more isotropic sampling of the simulation domain and its single lattice speed (i.e., link length) simplifies the computations and data storage. Furthermore, the fD3Q13 lattice can be decomposed into two independent interleaved lattices, one of which can be discarded, which doubles the simulation speed. The resulting LBM simulation can be efficiently mapped to the GPU, further increasing the computational performance. We show the numerical advantages of the FCC lattice on channeled flow in 2D and the flow-past-a-sphere benchmark in 3D. In both cases, the comparison is against the corresponding CC lattices using the analytical solutions for the systems as well as velocity field visualizations. We also demonstrate the performance advantages of the fD3Q13 lattice for interactive simulation and rendering of hot smoke in an urban environment using thermal LBM.     

GPU isosurface raycasting of FCC datasets

This paper presents an efficient and accurate isosurface rendering algorithm for the natural C¹ splines on the face-centered cubic (FCC) lattice. Leveraging fast and accurate evaluation of a spline field and its gradient, accompanied by efficient empty-space skipping, the approach generates high-quality isosurfaces of FCC datasets at interactive speed (20–70 fps). The pre-processing computation (quasi-interpolation and min/max cell construction) is improved 20–30-fold by OpenCL kernels. In addition, a novel indexing scheme is proposed that allows an FCC dataset to be stored as a four-channel 3D texture. When compared with other reconstruction schemes on the Cartesian and BCC (body-centered cubic) lattices, this method can be considered a practical reconstruction scheme that offers both quality and performance. The OpenCL and GLSL (OpenGL Shading Language) source codes are provided as a reference.     

Fast Fourier Transform on FCC and BCC Lattices with Outputs on FCC and BCC Lattices Respectively

In this paper, we show fast Fourier transform (FFT) algorithms for efficient, non-redundant evaluations of discrete Fourier transforms (DFTs) on face-centered cubic (FCC) and body-centered cubic (BCC) lattices such that the corresponding DFT outputs are on FCC and BCC lattices, respectively. Furthermore, for each of those FFTs, we deduce the structures of its spatial (frequency respectively) domains that are contained in the Voronoi cell centered at 0 with respect to the DFT (inverse DFT respectively) associated sublattice.     

Automatically obtaining a cellular automaton scheme for modeling protein folding using the FCC model

This paper proposes to model protein folding as an emergent process, using machine learning to infer the folding modeling only from information of known protein structures. Using the face-centered cubic lattice for protein conformation representation, the dynamic nature of protein folding is captured with an evolved neural cellular automaton that defines the amino acids moves along the protein chain and across time. The results of the final folded conformations are compared, using different protein benchmarks, with other methods used in the traditional protein structure prediction problem, highlighting the capabilities and problems found with this modeling.

     

On Near Optimal Lattice Quantization of Multi‐Dimensional Data Points

One of the most elementary application of a lattice is the quantization of real‐valued s‐dimensional vectors into finite bit precision to make them representable by a digital computer. Most often, the simple s‐dimensional regular grid is used for this task where each component of the vector is quantized individually. However, it is known that other lattices perform better regarding the average quantization error. A rank‐1 lattices is a special type of lattice, where the lattice points can be described by a single s‐dimensional generator vector. Further, the number of points inside the unit cube [0, 1)^s is arbitrary and can be directly enumerated by a single one‐dimensional integer value. By choosing a suitable generator vector the minimum distance between the lattice points can be maximized which, as we show, leads to a nearly optimal mean quantization error. We present methods for finding parameters for s‐dimensional maximized minimum distance rank‐1 lattices and further show their practical use in computer graphics applications.     

Multi-level lattice Boltzmann model on square lattice for compressible flows

A compressible lattice Boltzmann model is established on a square lattice. The model allows large variations in the mean velocity by introducing a large particle-velocity set. To maintain tractability, the support set of the equilibrium distribution is chosen to include only four directions and three particle-velocity levels in which the third level is introduced to improve the stability of the model. This simple structure of the equilibrium distribution makes the model efficient for the simulation of flows over a wide range of Mach numbers and gives it the capability of capturing shock jumps. Unlike the standard lattice Boltzmann model, the formulation eliminated the fourth-order velocity tensors, which were the source of concerns over the homogeneity of square lattices. A modified collision invariant eliminates the second-order discretization error of the fluctuation velocity in the macroscopic conservation equation from which the Navier–Stokes equation and energy equation are recovered. The model is suitable for both viscous and inviscid compressible flows with or without shocks. Two-dimensional shock-wave propagations and boundary layer flows were successfully simulated. The model can be easily extended to three-dimensional cubic lattices.     

Relating time complexity of protein folding simulation to approximations of folding time

Finkelstein and Badretdinov [A.V. Finkelstein, A.Y. Badretdinov, Rate of protein folding near the point of thermodynamic equilibrium between the coil and the most stable chain fold, Fold. Des. 2 (1997) 115-121] approximated the folding time of protein sequences of length n by exp(λ⋅n2/3±χ⋅n1/2/2)ns, where λ and χ are constants close to unity. Recently, Fu and Wang [B. Fu, W. Wang, A ²O(n1−1/d⋅logn) time algorithm for d-dimensional protein folding in the HP-model, in: J. Daz, J. Karhumäki, A. Lepistö, D. Sannella (Eds.), Proceedings of the 31st International Colloquium on Automata, Languages and Programming, in: Lecture Notes in Comput. Sci., vol. 3142, Springer-Verlag, Heidelberg, 2004, pp. 630-644] published an exp(O(n1−1/d)⋅lnn) algorithm for d-dimensional protein folding simulation in the HP-model, which is close to the folding time approximation by Finkelstein and Badretdinov and can be seen as a justification of the HP-model for investigating general complexity issues of protein folding. We propose a stochastic local search procedure that is based on logarithmic simulated annealing. We obtain that after (m/δ)^a⋅D Markov chain transitions the probability to be in a minimum energy conformation is at least 1−δ, where m?b(d)⋅n is the maximum neighbourhood size (b(d) small integer), a is a small constant, and D is the maximum value of the minimum escape height from local minima of the underlying energy landscape. We note that the time bound is instance-specific, and we conjecture D<n1−1/d as a worst case upper bound. We analyse experimentally on selected benchmark problems for the d=2 case.     

Weighted distance transforms generalized to modules and their computation on point lattices

This paper presents the generalization of weighted distances to modules and their computation through the chamfer algorithm on general point lattices. The first part is dedicated to formalization of definitions and properties (distance, metric, norm) of weighted distances on modules. It resumes tools found in literature to express the weighted distance of any point of a module and to compute optimal weights in the general case to get rotation invariant distances. The second part of this paper proves that, for any point lattice, the sequential two-scan chamfer algorithm produces correct distance maps. Finally, the definitions and computation of weighted distances are applied to the face-centered cubic (FCC) and body-centered cubic (BCC) grids.     

The three-dimensional fuzzy sets and their cut sets

In this paper, a new kind of L-fuzzy set is introduced which is called the three-dimensional fuzzy set. We first put forward four kinds of cut sets on the three-dimensional fuzzy sets which are defined by the 4-valued fuzzy sets. Then, the definitions of 4-valued order nested sets and 4-valued inverse order nested sets are given. Based on them, the decomposition theorems and representation theorems are obtained. Furthermore, the left interval-valued intuitionistic fuzzy sets and the right interval-valued intuitionistic fuzzy sets are introduced. We show that the lattices constructed by these two special L-fuzzy sets are not equivalent to sublattices of lattice constructed by the interval-valued intuitionistic fuzzy sets. Finally, we show that the three-dimensional fuzzy set is equivalent to the left interval-valued intuitionistic fuzzy set or the right interval-valued intuitionistic fuzzy set.     

Rectangular Lattice-Boltzmann Schemes with BGK-Collision Operator

The usual lattice-Boltzmann schemes for fluid flow simulations operate with square and cubic lattices. Instead of relying on square lattices it is possible to use rectangular and orthorombic lattices as well. Schemes using rectangular lattices can be constructed in several ways. Here we construct a rectangular scheme, with the BGK collision operator, by introducing 2 additional discrete velocities into the standard D2Q9 stencil and show how the same procedure can be applied in three dimensions by extending the D3Q19 stencil. The weights and scaling factors for the new stencils are found as the solutions of the well-known Hermite quadrature problem, assuring isotropy of the lattice tensors up to rank four (Philippi et al., Phys. Rev. E 73(5):056702, 2006) This isotropy is a necessary and sufficient condition for assuring the same second order accuracy of lattice-Boltzmann equation with respect to the Navier–Stokes hydrodynamic equations that is found with the standard D2Q9 and D3Q19 stencils. The numerical validation is done, in the two-dimensional case, by using the new rectangular scheme with D2R11 stencil for simulating the Taylor–Green vortex decay. The D3R23 stencil is numerically validated with three-dimensional simulations of cylindrical sound waves propagating from a point source.     

Solitons and energy transport in nonlinear lattices

The soliton, a localized wave entity, has successfully described long-wave propagation in a class of one-dimensional, nonlinear, dispersive, continuous and dicrete (lattice) systems. In this paper new evidence is presented for the existence of short wavelength or lattice solitons. First, we discuss our calculations for a one-dimensional cubic nonlinear lattice. Second, we interpret numerical calculations of the Los Alamos group for two-dimensional nonlinear lattices. In the latter case we suggest that the observed increase of the lattice thermal conductivity with an increase in the nonlinear parameter is due to the transport of energy by solitons.     

A constraint solver for discrete lattices,its parallelization,and application to protein structure prediction

This paper presents the design, implementation and application of a constraint programming framework on 3D crystal lattices. The framework provides the flexibility to express and resolve constraints dealing with structural relationships of entities placed in a 3D lattice structure in space. Both sequential and parallel implementations of the framework are described, along with experiments that highlight its superior performance with respect to the use of more traditional frameworks (e.g. constraints on finite domains and integer programming) to model lattice constraints. The framework is motivated and applied to address the problem of solving the protein folding prediction problem, i.e. predicting the 3D structure of a protein from its primary amino acid sequence. Results and comparison with performance of other constraint‐based solutions to this problem are presented. Copyright © 2007 John Wiley & Sons, Ltd.     

Incomplete information and concept lattices

We present a mathematical model of sets with incomplete information about identity of elements and the membership relation. The model is based on L-valued sets where L is a complete atomic Boolean algebra. We present general foundations of the theory with emphasis on partially ordered sets and complete lattices. As an application, we show a method for constructing structures that represent the concept lattice of an incomplete binary dataset.     

Visual comparability of 3D regular sampling and reconstruction

The Body-Centered Cubic (BCC) and Face-Centered Cubic (FCC) lattices have been analytically shown to be more efficient sampling lattices than the traditional Cartesian Cubic (CC) lattice, but there has been no estimate of their visual comparability. Two perceptual studies (each with N = 12 participants) compared the visual quality of images rendered from BCC and FCC lattices to images rendered from the CC lattice. Images were generated from two signals: the commonly used Marschner-Lobb synthetic function and a computed tomography scan of a fish tail. Observers found that BCC and FCC could produce images of comparable visual quality to CC, using 30-35 percent fewer samples. For the images used in our studies, the L(2) error metric shows high correlation with the judgement of human observers. Using the L(2) metric as a proxy, the results of the experiments appear to extend across a wide range of images and parameter choices.     

A search program for finding optimal integration lattices

In this paper we describe some of the salient features of our search program for finding good lattices. The reciprocals of these lattices are used in lattice integration rules, of which number theoretic rules form a major subset. We describe algorithms for ?(?), the Zaremba index (or figure of merit) of an integer lattice ?. We describe a search algorithm that finds ?(N), the maximum of ?(?) over lattices of orderN. One feature of our search is that it can exploit the symmetry of ? without significantly slowing down the program to list symmetric copies. We have also developed other interactions between the search algorithm and the algorithm for ?(?) that have a significant effect on the speed of the program. The paper is theoretical, providing the mathematical basis for these algorithms. However, we give a list of all the three-dimensional good lattices of order not exceedingN=4,000. This list has 68 entries, 40 of which are new.     

三角网格模型的快速树搜索算法及可设计性分析

在蛋白质折叠格子模型的可设计性特征研究中,为了克服以往方格模型具有奇偶问题这一缺点,本文利用三角网格模型来进行穷举搜索。在简化的网格模型中,序列折叠为某一结构的能量值为在结构心部疏水氨基酸的个数取负值。在蛋白质折叠模型的二维4 5 6 5 4三角网格中穷举了所有的序列和致密结构。其中序列由两类氨基酸(疏水氨基酸和亲水氨基酸)组成,排除正反对称序列共2~(12) 2~(23)=8392704种不同序列。在由24个格点组成的三角网格模型中共得到219093种简化结构串。在穷尽搜索算法中,为实现快速搜索,通过树结构将相似的结构串尽量聚类,通过计算各树结点的目标能量值以减少搜索算法中所需的计算量。经并行实验验证,利用该树结构可使快速搜索算法达到指数级加速比。最后对计算所得结果进行了统计分析。