Computer-assisted sequencing,interval graphs,and molecular evolution

In 1945, Fox developed the strategy for sequencing long proteins by using overlapping fragments. We show how the formal mathematical technique for the construction of interval graphs (Gilmore and Hoffman, 1964) is useful both pedagogically for understanding the underlying logic of sequencing linear molecules and is more amenable to automation because of its algorithmic nature. We also present a computer program, that employs the interval graph algorithm, which can be used to sequence proteins when given digest data. An example is given to illustrate all the steps involved in the algorithmic processing of the data. The need for such developments with respect to molecular evolution is discussed.     

A hierarchical method for molecular docking using cloud computing

Discovering small molecules that interact with protein targets will be a key part of future drug discovery efforts. Molecular docking of drug-like molecules is likely to be valuable in this field; however, the great number of such molecules makes the potential size of this task enormous. In this paper, a method to screen small molecular databases using cloud computing is proposed. This method is called the hierarchical method for molecular docking and can be completed in a relatively short period of time. In this method, the optimization of molecular docking is divided into two subproblems based on the different effects on the protein–ligand interaction energy. An adaptive genetic algorithm is developed to solve the optimization problem and a new docking program (FlexGAsDock) based on the hierarchical docking method has been developed. The implementation of docking on a cloud computing platform is then discussed. The docking results show that this method can be conveniently used for the efficient molecular design of drugs.     

A general approach to surface modelling applied to molecular graphics

A program is described that produces realistic representations of surfaces on a raster graphics terminal. The program uses a spatial subdivision algorithm similar to that of Woodwork and Quinlan. Simple geometric primitives, such as spheres, cones, cylinders and cuboids, are combined to build more complex pictures. This paper describes the program and how it is applied to molecular graphics. Examples of several applications are given.     

Optimization by simulating molecular evolution

Based on the analogy between mathematical optimization and molecular evolution and on Eigen's quasi-species model of molecular evolution, an evolutionary algorithm for combinatorial optimization has been developed. This algorithm consists of a versatile variation scheme and an innovative decision rule, the essence of which lies in a radical revision of the conventional philosophy of optimization: A number of configurations of variables with better values, instead of only a single best configuration, are selected as starting points for the next iteration. As a result the search proceeds in parallel along a number of routes and is unlikely to get trapped in local optima. An important innovation of the algorithm is introduction of a constraint to let the starting points always keep a certain distance from each other so that the search is able to cover a larger region of space effectively. The main advantage of the algorithm is that it has more chances to find the global optimum and as many local optima as possible in a single run. This has been demonstrated in preliminary computational experiments.     

Sequential and parallel molecular mechanics calculations

This article describes a gradient algorithm for the computational optimization of model molecular structures, and discusses the various compromises inherent in the practical expression of the algorithm in a Fortran computer program (VULCAN) for both sequential and parallel computers. Details are given of some previously undiscussed properties of gradient algorithms; various acceleration techniques are compared: and some traps for the unwary are highlighted.     

Fast algorithm for exact rendering of space-filling molecular models with shadows

An algorithm for accurate rendering of space-filling molecular models with shadows is presented. The intensity of light and cast shadows are computed to generate realistic pictures. Arbitrary numbers of light sources, which may be at infinite or finite distances can be applied. Hidden-surface removal, lighting, and shadowing are presented in detail.     

Chem-Ray: A molecular graphics program featuring an umbra and penumbra shadowing routine

Chem-Ray, new molecular graphics program, utilizes a combination of standard algorithms developed for molecular systems as well as various ray casting techniques to produce highly realistic images on inexpensive raster terminals. The program produces images of space-filling, ball and stick or stick models derived from a user-supplied co-ordinate list. The most notable new feature of Chem-Ray is a simple, yet effective, algorithm for the improved treatment of shadows within a molecule. This new algorithm is based upon a calculation of a light pyramid at each point under examination. Intersections of various objects with this light pyramid will decrease the percentage of the light that can reach the point. If the entire cross-section is blocked, the point will be in the umbra of the shadow; if only a portion of the light is blocked, the point will be in the penumbra of the shadow.     

Identification of tunnels in proteins, nucleic acids, inorganic materials and molecular ensembles

The knowledge of the access paths connecting interior of molecular systems with surrounding environment is important for the understanding of structurefunction relationships and engineering of molecules for biotechnological applications. CAVER is a computer program developed for calculations of tunnels, channels or pores in the biomolecules, inorganic materials and molecular ensembles. The algorithm performs a skeleton search based on a reciprocal distance function grid. The algorithm is implemented in the stand-alone version, web version and as plug-in for PyMol. CAVER is available from the website http://loschmidt.chemi.muni.cz/caver.     

Computational complexity of a problem in molecular structure prediction.

The computational task of protein structure prediction is believed to require exponential time, but previous arguments as to its intractability have taken into account only the size of a protein's conformational space. Such arguments do not rule out the possible existence of an algorithm, more selective than exhaustive search, that is efficient and exact. (An efficient algorithm is one that is guaranteed, for all possible inputs, to run in time bounded by a function polynomial in the problem size. An intractable problem is one for which no efficient algorithm exists.) Questions regarding the possible intractability of problems are often best answered using the theory of NP-completeness. In this treatment we show the NP-hardness of two typical mathematical statements of empirical potential energy function minimization of macromolecules. Unless all NP-complete problems can be solved efficiently, these results imply that a function minimization algorithm can be efficient for protein structure prediction only if it exploits protein-specific properties that prohibit the simple geometric constructions that we use in our proofs. Analysis of further mathematical statements of molecular structure prediction could constitute a systematic methodology for identifying sources of complexity in protein folding, and for guiding development of predictive algorithms.     

Targeting imidazoline site on monoamine oxidase B through molecular docking simulations

Monoamine oxidase (MAO) is an enzyme of major importance in neurochemistry, because it catalyzes the inactivation pathway for the catecholamine neurotransmitters, noradrenaline, adrenaline and dopamine. In the last decade it was demonstrated that imidazoline derivatives were able to inhibit MAO activity. Furthermore, crystallographic studies identified the imidazoline-binding domain on monoamine oxidase B (MAO-B), which opens the possibility of molecular docking studies focused on this binding site. The goal of the present study is to identify new potential inhibitors for MAO-B. In addition, we are also interested in establishing a fast and reliable computation methodology to pave the way for future molecular docking simulations focused on the imidazoline-binding site of this enzyme. We used the program 'molegro virtual docker' (MVD) in all simulations described here. All results indicate that simplex evolution algorithm is able to succesfully simulate the protein-ligand interactions for MAO-B. In addition, a scoring function implemented in the program MVD presents high correlation coefficient with experimental activity of MAO-B inhibitors. Taken together, our results identified a new family of potential MAO-B inhibitors and mapped important residues for intermolecular interactions between this enzyme and ligands.     

Interactive molecular biology computing

It is clear that the selection of the best possible algorithm for a computer program is essential for the creation of a useful tool. After this first step is taken, however, the usefulness of such a program may be greatly enhanced or impeded by the way it is implemented. We illustrate this point by describing our implementation of the well known FASTP/FASTIN algorithm in an interactive software environment.     

SIMS: computation of a smooth invariant molecular surface.

SIMS, a new method of calculating a smooth invariant molecular dot surface, is presented. The SIMS method generates the smooth molecular surface by rolling two probe spheres. A solvent probe sphere is rolled over the molecule and produces a Richards-Connolly molecular surface (MS), which envelops the solvent-excluded volume of the molecule. In deep crevices, Connolly's method of calculating the MS has two deficiencies. First, it produces self-intersecting parts of the molecular surface, which must be removed to obtain the correct MS. Second, the correct MS is not smooth, i.e., the direction of the normal vector of the MS is not continuous, and some points of the MS are singular. We present an exact method for removing self-intersecting parts and smoothing the singular regions of the MS. The singular MS is smoothed by rolling a smoothing probe sphere over the inward side of the singular MS. The MS in the vicinity of singularities is replaced with the reentrant surface of the smoothing probe sphere. The smoothing method does not disturb the topology of a singular MS, and the smooth MS is a better approximation of the dielectric border between high dielectric solvent and the low dielectric molecular interior. The SIMS method generates a smooth molecular dot surface, which has a quasi-uniform dot distribution in two orthogonal directions on the molecular surface, which is invariant with molecular rotation and stable under changes in the molecular conformation, and which can be used in a variety of implicit methods of modeling solvent effects. The SIMS program is faster than the Connolly MS program, and in a matter of seconds generates a smooth dot MS of a 200-residue protein. The program is available from the authors on request (see http:@femto.med.unc.edu/SIMS).     

Quantitative analysis and molecular species fingerprinting of triacylglyceride molecular species directly from lipid extracts of biological samples by electrospray ionization tandem mass spectrometry

Herein we describe a rapid, simple, and reliable method for the quantitative analysis and molecular species fingerprinting of triacylglycerides (TAG) directly from chloroform extracts of biological samples. Previous attempts at direct TAG quantitation by positive-ion electrospray ionization mass spectrometry (ESI/MS) were confounded by the presence of overlapping peaks from choline glycerophospholipids requiring chromatographic separation of lipid extracts prior to ESI/MS analyses. By exploiting the rapid loss of phosphocholine from choline glycerophospholipids, in conjunction with neutral-loss scanning for individual fatty acids, overlapping peaks in the ESI mass spectrum were deconvoluted generating a detailed molecular species fingerprint of individual TAG molecular species directly from chloroform extracts of biological samples. This method readily detects as little as 0.1 pmol of each TAG molecular species from chloroform extracts and is linear over a 1000-fold dynamic range. The sensitivity of individual TAG molecular species to ESI/MS/MS analyses correlated with the unsaturation index and inversely correlated with total aliphatic chain length of TAG. An algorithm was developed which identifies sensitivity factors, thereby allowing the rapid quantitation and molecular species fingerprinting of TAG molecular species directly from chloroform extracts of biological samples.     

A simple method to display molecular orbitals with computer graphics

A computer program named LOBE was developed to draw molecular orbitals as lobes on a graphic display. With this program, any molecular orbital of large molecules can be displayed quickly. This program is suitable not only for general-purpose computers but also for microcomputers. A sample application is used to illustrate the program.     

An efficient algorithm for identifying matches with errors in multiple long molecular sequences

An efficient algorithm is described for finding matches, repeats and other word relations, allowing for errors, in large data sets of long molecular sequences. The algorithm entails hashing on fixed-size words in conjunction with the use of a linked list connecting all occurrences of the same word. The average memory and run time requirement both increase almost linearly with the total sequence length. Some results of the program's performance on a database of Escherichia coli DNA sequences are presented.     

CORGEN: A FORTRAN-77 generator of standard and non-standard DNA helices from the sequence

An analytical procedure CORGEN generates a variety of DNA double-strandedstructures from user-supplied sequence using a nucleic aciddatabase incorporated into a standard FORTRAN-77 program. Alternatively,the cylindrical polar coordinates of DNA components may be suppliedfrom the external table. An algorithm that performs intercalationsites in DNA is described. This procedure can be used to generatecomplexes of antibiotics with DNA. Non-standard DNA structurescan be built by alternating the global helical twist and globalhelical rise in the regular DNA helix. The procedures describedcan be used for computer generation of a variety of non-standardDNA structures which can be subjected to molecular mechanicsand dynamics simulations. Received on February 20, 1989; accepted on June 27, 1989     

Information processing in molecular systems

Information processing, or selective dissipation, is mediated by switching elements in classical systems and by enzyme catalysis in biochemical systems. There are important differences in the character of this dissipation (from the standpoint of energy and control) in self-reproducing systems based on molecular interactions and those based on conventional computers. Conventional computers process information in a single level mode, i.e., the state of each unit of the system is accessed independently. This includes the manipulable memory units which store the computer program. In contrast, molecular self-reproducing systems process information in a hierarchical mode, based on the fact of hierarchy in molecular structure. In particular, the enzyme is described genetically at the primary level of structure (amino acid sequence) but functions at the higher, tertiary level on the basis of the interactions of many manipulable units. As a consequence it is not possible to program a biochemical system in any conventional sense. However, this is compensated by an increased capacity for accumulating appropriate information through evolution by variation and natural selection. This is possible because systems operating in the hierarchical mode are amenable to gradual modification of function. The degree of gradualness is itself an evolved property of biological molecules.