A platform for biological sequence comparison on parallel computers

We have written two programs for searching biological sequence databases that run on Intel hypercube computers. PSCANLIB compares a single sequence against a sequence library, and PCOMPLIB compares all the entries in one sequence library against a second library. The programs provide a general framework for similarity searching; they include functions for reading in query sequences, search parameters and library entries, and reporting the results of a search. We have isolated the code for the specific function that calculates the similarity score between the query and library sequence; alternative searching algorithms can be implemented by editing two files. We have implemented the rapid FASTA sequence comparison algorithm and the more rigorous Smith-Waterman algorithm within this framework. The PSCANLIB program on a 16 node iPSC/2 80386-based hypercube can compare a 229 amino acid protein sequence with a 3.4 million residue sequence library in approximately 16 s with the FASTA algorithm. Using the Smith-Waterman algorithm, the same search takes 35 min. The PCOMPLIB program can compare a 0.8 million amino acid protein sequence library with itself in 5.3 min with FASTA on a third-generation 32 node Intel iPSC/860 hypercube.     

L^{1}-optimal compensators for continuous-time systems

Previous work has been concerned with minimizing thel^{1}-norm of an error pulse response for discrete-time SISO [1] and MIMO [2] systems. In this paper we study the problem of minimizing the L¹-norm of the error impulse response for SISO continuous-time systems. This problem is quite different from the discrete-time problem in that irrational solutions are obtained even when the problem data are rational. Two methods are suggested for the solution of the continuous-time problem; an exact method which leads to a finite-dimensional nonlinear programming problem, and an approximate method which leads to a linear programming problem.     

The computer: liberator or jailor of the creative spirit

A discussion of the historical and aesthetic questions raised by the Fine Arts community regarding the uses of the computer by artists, its limitations and its potential. Creating a texture and context for this discussion necessitated the weaving into this discussion the role of technology, science, mathematics, the humanities, and aesthetics in the visual arts.     

A general framework for linear periodic systems with applicationsto H∞ sampled-data control

The authors present a framework for dealing with continuous-time periodic systems. The main tool is a lifting technique which provides a strong correspondence between continuous-time periodic systems and certain types of discrete-time time-invariant systems with infinite-dimensional input and output spaces. Despite the infinite dimensionality of the input and output spaces, a lifted system has a finite-dimensional state space if the original system does. This fact permits rather constructive methods for analyzing these systems. As a demonstration of the utility of this framework, the authors use it to describe the continuous-time (i.e., intersample) behavior of sampled-data systems, and to obtain a complete solution to the problem of parameterizing all controllers that constrain the L² -induced norm of a sampled-data system to within a certain bound     

No pain and gain!—experiences with Mentat on a biological application

Throughout much of the parallel processing community there is the sense that writing software for distributed-memory parallel processors Is subject to a ‘no pain—no gain’ rule: that In order to reap the benefits of parallel computation one must first suffer the pain of converting the application to run on a parallel machine. We believe this Is the result of Inadequate programming tools and not a problem Inherent to parallel processing. We will show that one can parallelize real scientific applications and obtain good performance with little effort If the right tools are used. Our vehicle for this demonstration is a 6000-line DNA and protein sequence comparison application that we have implemented in Mental, an object-oriented parallel processing system for both parallel and distributed architectures. We briefly describe the application and present performance information for both the Mentat version and a hand-coded parallel version of the application.     

Solving applied general equilibrium models represented as a mixture of linearized and levels equations

General equilibrium moels are usually represented as a system of levels equations (e.g., in North America) or a system of linearized equations (e.g., in Australia). Either representation can be used to obtain accurate solutions. General-purpose software is available in both cases-GAMS or MPS/GE is typically used by levels modellers and GEMPACK by linearizers. Some equations (notably accounting identities) are naturally expressed in the levels while others (especially behavioural equations) are naturally expressed in a linearized form. This paper describes the new GEMPACK facility for solving models represented as a mixture of levels and linearized equations and discusses the advantages to modellers of using such a representation.     

Nonlinear discrete-time models: state-space vs. I/O representations

This paper compares state-space and input–output realizations for nonlinear discrete-time dynamic models. For linear models, these two realizations are essentially equivalent and their structures are closely related, but these statements do not hold for nonlinear models. We illustrate this point with simple, realistic examples for which only one of the two realizations exists or for which both exist but their structures are profoundly different. Overall, the main point of this paper is the importance of the choice of realization in the development of nonlinear dynamic models.     

On matrices, automata, and double counting in constraint programming

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.     

Contact type dependency of texture classification in a whiskered mobile robot

Actuated artificial whiskers modeled on rat macrovibrissae can provide effective tactile sensor systems for autonomous robots. This article focuses on texture classification using artificial whiskers and addresses a limitation of previous studies, namely, their use of whisker deflection signals obtained under relatively constrained experimental conditions. Here we consider the classification of signals obtained from a whiskered robot required to explore different surface textures from a range of orientations and distances. This procedure resulted in a variety of deflection signals for any given texture. Using a standard Gaussian classifier we show, using both hand-picked features and ones derived from studies of rat vibrissal processing, that a robust rough-smooth discrimination is achievable without any knowledge of how the whisker interacts with the investigated object. On the other hand, finer discriminations appear to require knowledge of the target’s relative position and/or of the manner in which the whisker contact its surface. Electronic Supplementary Material  The online version of this article () contains supplementary material, which is available to authorized users.