A simulated annealing algorithm for finding consensus sequences

Motivation: A consensus sequence for a family of related sequences is, as the name suggests, a sequence that captures the features common to most members of the family. Consensus sequences are important in various DNA sequencing applications and are a convenient way to characterize a family of molecules. Results: This paper describes a new algorithm for finding a consensus sequence, using the popular optimization method known as simulated annealing. Unlike the conventional approach of finding a consensus sequence by first forming a multiple sequence alignment, this algorithm searches for a sequence that minimises the sum of pairwise distances to each of the input sequences. The resulting consensus sequence can then be used to induce a multiple sequence alignment. The time required by the algorithm scales linearly with the number of input sequences and quadratically with the length of the consensus sequence. We present results demonstrating the high quality of the consensus sequences and alignments produced by the new algorithm. For comparison, we also present similar results obtained using ClustalW. The new algorithm outperforms ClustalW in many cases.

Existence of a semicontinuous or continuous utility function: a unified approach and an elementary proof

In this paper, we present a new unified approach and an elementary proof of a very general theorem on the existence of a semicontinuous or continuous utility function representing a preference relation. A simple and interesting new proof of the famous Debreu Gap Lemma is given. In addition, we prove a new Gap Lemma for the rational numbers and derive some consequences. We also prove a theorem which characterizes the existence of upper semicontinuous utility functions on a preordered topological space which need not be second countable. This is a generalization of the classical theorem of Rader which only gives sufficient conditions for the existence of an upper semicontinuous utility function for second countable topological spaces. (C) 2002 Elsevier Science B.V. All rights reserved.

The non-existence of a utility function and the structure of non-representable preference relations

In this paper we investigate the structure of non-representable preference relations. While there is a vast literature on different kinds of preference relations that can be represented by a real-valued utility function, very little is known or understood about preference relations that cannot be represented by a real-valued utility function. There has been no systematic analysis of the non-representation problem. In this paper we give a complete description of non-representable preference relations which are total preorders or chains. We introduce and study the properties of four classes of non-representable chains: long chains, planar chains, Aronszajn-like chains and Souslin chains. In the main theorem of the paper we prove that a chain is non-representable if and only it is a long chain, a planar chain, an Aronszajn-like chain or a Souslin chain. (C) 2002 Published by Elsevier Science B.V.

Lexicographic decomposition of chains and the concept of a planar chain

In an earlier paper [Journal of Mathematical Economics, 37 (2002) 17-38], we proved that if a preference relation on a commodity space is non-representable by a real-valued function then that chain is necessarily a long chain, a planar chain, an Aronszajn-like chain or a Souslin chain. In this paper, we study the class of planar chains, the simplest example of which is the Debreu chain (R-2, <(l)). (C) 2002 Elsevier Science B.V. All rights reserved.

Estimating and evaluating the statistics of gapped local-alignment scores

We present a novel maximum-likelihood-based algorithm for estimating the distribution of alignment scores from the scores of unrelated sequences in a database search. Using a new method for measuring the accuracy of p-values, we show that our maximum-likelihood-based algorithm is more accurate than existing regression-based and lookup table methods. We explore a more sophisticated way of modeling and estimating the score distributions (using a two-component mixture model and expectation maximization), but conclude that this does not improve significantly over simply ignoring scores with small E-values during estimation. Finally, we measure the classification accuracy of p-values estimated in different ways and observe that inaccurate p-values can, somewhat paradoxically, lead to higher classification accuracy. We explain this paradox and argue that statistical accuracy, not classification accuracy, should be the primary criterion in comparisons of similarity search methods that return p-values that adjust for target sequence length.

Control of chaotic instability in a dual-spin spacecraft with dissipation using energy methods

Control of chaotic instability in a rotating multibody system in the form of a dual-spin spacecraft with an axial nutational damper is achieved using an algorithm derived using energy methods. The control method is implemented on two realistic spacecraft parameter configurations which have been found to exhibit chaotic instability when a sinusoidally varying torque is applied to the spacecraft for a range of forcing amplitudes and frequencies. Such a torque, in practice, may arise under malfunction of the control system or from an unbalanced rotor. Chaotic instabilities arising from these torques could introduce uncertainties and irregularities into a spacecraft's attitude and consequently impair pointing accuracy. The control method is formulated from nutational stability results derived using an energy sink approximation for a dual-spin spacecraft with an asymmetric platform and axisymmetric rotor. The effectiveness of the control method is shown numerically and the results are studied by means of time history, phase space, Poincare map, Lyapunov characteristic exponents and Bifurcation diagrams.

Improvements to peroxide oxidation methods for analysing sulfur in acid sulfate soils

Improvements to peroxide oxidation methods for analysing acid sulfate soils (ASS) are introduced. The soil solution ratio has been increased to 1 : 40, titrations are performed in suspension, and the duration of the peroxide digest stage is substantially shortened. For 9 acid sulfate soils, the peroxide oxidisable sulfur value obtained using the improved method was compared with the reduced inorganic sulfur result obtained using the chromium reducible sulfur method. Their regression was highly significant, the slope of the regression line was not significantly different (P = 0.05) from unity, and the intercept not significantly different from zero. A complete sulfur budget for the improved method showed there was no loss of sulfur as has been reported for earlier peroxide oxidation techniques. When soils were very finely ground, efficient oxidation of sulfides was achieved, despite the milder digestion conditions. Highly sulfidic and organic soils were shown to be the most difficult to analyse using either the improved method or the chromium method. No single analytical method can be universally applied to all ASS, rather a suite of methods is necessary for a thorough understanding of many ASS. The improved peroxide method, in combination with the chromium method and the 4 M HCl extraction, form a sound platform for informed decision making on the management of acid sulfate soils.

A variable stepsize implementation for stochastic differential equations

Stochastic differential equations (SDEs) arise from physical systems where the parameters describing the system can only be estimated or are subject to noise. Much work has been done recently on developing higher order Runge-Kutta methods for solving SDEs numerically. Fixed stepsize implementations of numerical methods have limitations when, for example, the SDE being solved is stiff as this forces the stepsize to be very small. This paper presents a completely general variable stepsize implementation of an embedded Runge Kutta pair for solving SDEs numerically; in this implementation, there is no restriction on the value used for the stepsize, and it is demonstrated that the integration remains on the correct Brownian path.

An atomistic simulation of solid state sintering using Monte Carlo methods

This paper presents results on the simulation of the solid state sintering of copper wires using Monte Carlo techniques based on elements of lattice theory and cellular automata. The initial structure is superimposed onto a triangular, two-dimensional lattice, where each lattice site corresponds to either an atom or vacancy. The number of vacancies varies with the simulation temperature, while a cluster of vacancies is a pore. To simulate sintering, lattice sites are picked at random and reoriented in terms of an atomistic model governing mass transport. The probability that an atom has sufficient energy to jump to a vacant lattice site is related to the jump frequency, and hence the diffusion coefficient, while the probability that an atomic jump will be accepted is related to the change in energy of the system as a result of the jump, as determined by the change in the number of nearest neighbours. The jump frequency is also used to relate model time, measured in Monte Carlo Steps, to the actual sintering time. The model incorporates bulk, grain boundary and surface diffusion terms and includes vacancy annihilation on the grain boundaries. The predictions of the model were found to be consistent with experimental data, both in terms of the microstructural evolution and in terms of the sintering time. (C) 2002 Elsevier Science B.V. All rights reserved.

A four-stage index 2 Diagonally Implicit Runge-Kutta method

High index Differential Algebraic Equations (DAEs) force standard numerical methods to lower order. Implicit Runge-Kutta methods such as RADAU5 handle high index problems but their fully implicit structure creates significant overhead costs for large problems. Singly Diagonally Implicit Runge-Kutta (SDIRK) methods offer lower costs for integration. This paper derives a four-stage, index 2 Explicit Singly Diagonally Implicit Runge-Kutta (ESDIRK) method. By introducing an explicit first stage, the method achieves second order stage calculations. After deriving and solving appropriate order conditions., numerical examples are used to test the proposed method using fixed and variable step size implementations. (C) 2001 IMACS. Published by Elsevier Science B.V. All rights reserved.