Estimation of individual phases from the four-phase structure invariants in the single isomorphous replacement case

The probability distribution of the four-phase invariants in the case of single isomorphous replacement has been developed to estimate some individual phases. An example of its application to obtain the phases having special values of 0, pi or +/-pi /2 is given for a known protein structure in space group P2(1)2(1)2(1). The phasing procedure includes the determination of starting phases and an iterative calculation. The initial values of starting phases, which are required by the formula, can be obtained from the estimate of one-phase seminvariants and by specifying the origin and enantiomorph. In addition, the calculations lead to two sets of possible phases for each type of reflection by assigning arbitrarily an initial phase value. The present method provides a possibility for the multisolution technique to increase greatly the number of known phases while keeping the number of the trials quite small.

Probability distribution of the four-phase structure invariants of isomorphously related structure factors and its applications

The probability distribution of the four-phase structure invariants (4PSIs) involving four pairs of structure factors is derived by integrating the direct methods with isomorphous replacement (IR). A simple expression of the reliability parameter for 16 types of invariant is given in the case of a native protein and a heavy-atom derivative. Test calculations on a protein and its heavy-atom derivative using experimental diffraction data show that the reliability for 4PSI estimates is comparable with that for the three-phase structure invariants (3PSIs), and that a large-modulus invariants method can be used to improve the accuracy.

General expression for probabilistic estimation of multiphase structure invariants in the case of a native protein and multiple derivatives. Application to estimates of the three-phase structure invariants

Concise probabilistic formulae with definite crystallographic implications are obtained from the distribution for eight three-phase structure invariants (3PSIs) in the case of a native protein and a heavy-atom derivative [Hauptman (1982). Acta Cryst. A38, 289-294] and from the distribution for 27 3PSIs in the case of a native and two derivatives [Fortier, Weeks & Hauptman (1984). Acta Cryst. A40, 646-651]. The main results of the probabilistic formulae for the four-phase structure invariants are presented and compared with those for the 3PSIs. The analysis directly leads to a general formula of probabilistic estimation for the n-phase structure invariants in the case of a native and m derivatives. The factors affecting the estimated accuracy of the 3PSIs are examined using the diffraction data from a moderate-sized protein. A method to estimate a set of the large-modulus invariants, each corresponding to one of the eight 3PSIs, that has the largest \Delta\ values and relatively large structure-factor moduli between the native and derivative is suggested, which remarkably improves the accuracy, and thus a phasing procedure making full use of all eight 3PSIs is proposed.

LEAST-SQUARES POLYNOMIAL SMOOTHING FOR INDUCTIVELY COUPLED PLASMA ATOMIC EMISSION-SPECTRA

The use of least-squres polynomial smoothing in ICP-AES is discussed and a method of points insertion into spectral scanning intervals is proposed in the present paper. Optimal FWHM/SR ratio can be obtained, and distortion of smoothed spectra can be avoided by use of the recommended method.

Direct Computation of 3D Shape Invariants and the Focus of Expansion

Structure from motion often refers to the computation of 3D structure from a matched sequence of images. However, a depth map of a surface is difficult to compute and may not be a good representation for storage and recognition. Given matched images, I will first show that the sign of the normal curvature in a given direction at a given point in the image can be computed from a simple difference of slopes of line-segments in one image. Using this result, local surface patches can be classified as convex, concave, parabolic (cylindrical), hyperbolic (saddle point) or planar. At the same time the translational component of the optical flow is obtained, from which the focus of expansion can be computed.

Recognition of Topological Invariants by Iterative Arrays

A study is made of the recognition and transformation of figures by iterative arrays of finite state automata. A figure is a finite rectangular two-dimensional array of symbols. The iterative arrays considered are also finite, rectangular, and two-dimensional. The automata comprising any given array are called cells and are assumed to be isomorphic and to operate synchronously with the state of a cell at time t+1 being a function of the states of it and its four nearest neighbors at time t. At time t=0 each cell is placed in one of a fixed number of initial states. The pattern of initial states thus introduced represents the figure to be processed. The resulting sequence of array states represents a computation based on the input figure. If one waits for a specially designated cell to indicate acceptance or rejection of the figure, the array is said to be working on a recognition problem. If one waits for the array to come to a stable configuration representing an output figure, the array is said to be working on a transformation problem.

On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to the counting class coC=P.

Deciding Isomorphisms of Simple Types in Polynomial Time

The isomorphisms holding in all models of the simply typed lambda calculus with surjective and terminal objects are well studied - these models are exactly the Cartesian closed categories. Isomorphism of two simple types in such a model is decidable by reduction to a normal form and comparison under a finite number of permutations (Bruce, Di Cosmo, and Longo 1992). Unfortunately, these normal forms may be exponentially larger than the original types so this construction decides isomorphism in exponential time. We show how using space-sharing/hash-consing techniques and memoization can be used to decide isomorphism in practical polynomial time (low degree, small hidden constant). Other researchers have investigated simple type isomorphism in relation to, among other potential applications, type-based retrieval of software modules from libraries and automatic generation of bridge code for multi-language systems. Our result makes such potential applications practically feasible.

A polynomial algorithm for the three-machine open shop with a bottleneck machine

The paper considers the three‐machine open shop scheduling problem to minimize themakespan. It is assumed that each job consists of at most two operations, one of which is tobe processed on the bottleneck machine, the same for all jobs. A new lower bound on theoptimal makespan is derived, and a linear‐time algorithm for finding an optimalnon‐preemptive schedule is presented.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.

The conjugacy problem for two-by-two matrices over polynomial rings

We give an effective solution of the conjugacy problem for two-by-two matrices over the polynomial ring in one variable over a finite field.