A finite population model of mlecular evolution: theory and computation

This article is concerned with the evolution of haploid organisms that reproduce asexually. In a seminal piece of work, Eigen and coauthors proposed the quasispecies model in an attempt to understand such an evolutionary process. Their work has impacted antiviral treatment and vaccine design strategies. Yet, predictions of the quasispecies model are at best viewed as a guideline, primarily because it assumes an infinite population size, whereas realistic population sizes can be quite small. In this paper we consider a population genetics-based model aimed at understanding the evolution of such organisms with finite population sizes and present a rigorous study of the convergence and computational issues that arise therein. Our first result is structural and shows that, at any time during the evolution, as the population size tends to infinity, the distribution of genomes predicted by our model converges to that predicted by the quasispecies model. This justifies the continued use of the quasispecies model to derive guidelines for intervention. While the stationary state in the quasispecies model is readily obtained, due to the explosion of the state space in our model, exact computations are prohibitive. Our second set of results are computational in nature and address this issue. We derive conditions on the parameters of evolution under which our stochastic model mixes rapidly. Further, for a class of widely used fitness landscapes we give a fast deterministic algorithm which computes the stationary distribution of our model. These computational tools are expected to serve as a framework for the modeling of strategies for the deployment of mutagenic drugs.

An eigenproblem approach to classical screw theory

This paper presents a novel algebraic formulation of the central problem of screw theory, namely the determination of the principal screws of a given system. Using the algebra of dual numbers, it shows that the principal screws can be determined via the solution of a generalised eigenproblem of two real, symmetric matrices. This approach allows the study of the principal screws of the general two-, three-systems associated with a manipulator of arbitrary geometry in terms of closed-form expressions of its architecture and configuration parameters. We also present novel methods for the determination of the principal screws for four-, five-systems which do not require the explicit computation of the reciprocal systems. Principal screws of the systems of different orders are identified from one uniform criterion, namely that the pitches of the principal screws are the extreme values of the pitch.The classical results of screw theory, namely the equations for the cylindroid and the pitch-hyperboloid associated with the two-and three-systems, respectively have been derived within the proposed framework. Algebraic conditions have been derived for some of the special screw systems. The formulation is also illustrated with several examples including two spatial manipulators of serial and parallel architecture, respectively.

An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.

Eigenvalues of kinematical conservation laws (KCL) based 3-D weakly nonlinear ray theory (WNLRT)

System of kinematical conservation laws (KCL) govern evolution of a curve in a plane or a surface in space, even if the curve or the surface has singularities on it. In our recent publication K. R. Arun, P. Prasad, 3-D kinematical conservation laws (KCL): evolution of a surface in R-3-in particular propagation of a nonlinear wavefront, Wave Motion 46 (2009) 293-311] we have developed a mathematical theory to study the successive positions and geometry of a 3-D weakly nonlinear wavefront by adding an energy transport equation to KCL. The 7 x 7 system of equations of this KCL based 3-D weakly nonlinear ray theory (WNLRT) is quite complex and explicit expressions for its two nonzero eigenvalues could not be obtained before. In this short note, we use two different methods: (i) the equivalence of KCL and ray equations and (ii) the transformation of surface coordinates, to derive the same exact expressions for these eigenvalues. The explicit expressions for nonzero eigenvalues are important also for checking stability of any numerical scheme to solve 3-D WNLRT. (C) 2010 Elsevier Inc. All rights reserved.

Parallel Computation of 2D Morse-Smale Complexes

The Morse-Smale complex is a useful topological data structure for the analysis and visualization of scalar data. This paper describes an algorithm that processes all mesh elements of the domain in parallel to compute the Morse-Smale complex of large two-dimensional data sets at interactive speeds. We employ a reformulation of the Morse-Smale complex using Forman's Discrete Morse Theory and achieve scalability by computing the discrete gradient using local accesses only. We also introduce a novel approach to merge gradient paths that ensures accurate geometry of the computed complex. We demonstrate that our algorithm performs well on both multicore environments and on massively parallel architectures such as the GPU.

Distributed Function Computation over Fields and Rings via Linear Compression of Sources

The setting considered in this paper is one of distributed function computation. More specifically, there is a collection of N sources possessing correlated information and a destination that would like to acquire a specific linear combination of the N sources. We address both the case when the common alphabet of the sources is a finite field and the case when it is a finite, commutative principal ideal ring with identity. The goal is to minimize the total amount of information needed to be transmitted by the N sources while enabling reliable recovery at the destination of the linear combination sought. One means of achieving this goal is for each of the sources to compress all the information it possesses and transmit this to the receiver. The Slepian-Wolf theorem of information theory governs the minimum rate at which each source must transmit while enabling all data to be reliably recovered at the receiver. However, recovering all the data at the destination is often wasteful of resources since the destination is only interested in computing a specific linear combination. An alternative explored here is one in which each source is compressed using a common linear mapping and then transmitted to the destination which then proceeds to use linearity to directly recover the needed linear combination. The article is part review and presents in part, new results. The portion of the paper that deals with finite fields is previously known material, while that dealing with rings is mostly new.Attempting to find the best linear map that will enable function computation forces us to consider the linear compression of source. While in the finite field case, it is known that a source can be linearly compressed down to its entropy, it turns out that the same does not hold in the case of rings. An explanation for this curious interplay between algebra and information theory is also provided in this paper.

Parallel Computation of 3D Morse-Smale Complexes

The Morse-Smale complex is a topological structure that captures the behavior of the gradient of a scalar function on a manifold. This paper discusses scalable techniques to compute the Morse-Smale complex of scalar functions defined on large three-dimensional structured grids. Computing the Morse-Smale complex of three-dimensional domains is challenging as compared to two-dimensional domains because of the non-trivial structure introduced by the two types of saddle criticalities. We present a parallel shared-memory algorithm to compute the Morse-Smale complex based on Forman's discrete Morse theory. The algorithm achieves scalability via synergistic use of the CPU and the GPU. We first prove that the discrete gradient on the domain can be computed independently for each cell and hence can be implemented on the GPU. Second, we describe a two-step graph traversal algorithm to compute the 1-saddle-2-saddle connections efficiently and in parallel on the CPU. Simultaneously, the extremasaddle connections are computed using a tree traversal algorithm on the GPU.

Secure Computation in a Bidirectional Relay

Bidirectional relaying, where a relay helps two user nodes to exchange equal length binary messages, has been an active area of recent research. A popular strategy involves a modified Gaussian MAC, where the relay decodes the XOR of the two messages using the naturally-occurring sum of symbols simultaneously transmitted by user nodes. In this work, we consider the Gaussian MAC in bidirectional relaying with an additional secrecy constraint for protection against a honest but curious relay. The constraint is that, while the relay should decode the XOR, it should be fully ignorant of the individual messages of the users. We exploit the symbol addition that occurs in a Gaussian MAC to design explicit strategies that achieve perfect independence between the received symbols and individual transmitted messages. Our results actually hold for a more general scenario where the messages at the two user nodes come from a finite Abelian group G, and the relay must decode the sum within G of the two messages. We provide a lattice coding strategy and study optimal rate versus average power trade-offs for asymptotically large dimensions.

Simulation of inhomogeneous distributions of ultracold atoms in an optical lattice via a massively parallel implementation of nonequilibrium strong-coupling perturbation theory

We present a nonequilibrium strong-coupling approach to inhomogeneous systems of ultracold atoms in optical lattices. We demonstrate its application to the Mott-insulating phase of a two-dimensional Fermi-Hubbard model in the presence of a trap potential. Since the theory is formulated self-consistently, the numerical implementation relies on a massively parallel evaluation of the self-energy and the Green's function at each lattice site, employing thousands of CPUs. While the computation of the self-energy is straightforward to parallelize, the evaluation of the Green's function requires the inversion of a large sparse 10(d) x 10(d) matrix, with d > 6. As a crucial ingredient, our solution heavily relies on the smallness of the hopping as compared to the interaction strength and yields a widely scalable realization of a rapidly converging iterative algorithm which evaluates all elements of the Green's function. Results are validated by comparing with the homogeneous case via the local-density approximation. These calculations also show that the local-density approximation is valid in nonequilibrium setups without mass transport.

Markov chains, R-trivial monoids and representation theory

We develop a general theory of Markov chains realizable as random walks on R-trivial monoids. It provides explicit and simple formulas for the eigenvalues of the transition matrix, for multiplicities of the eigenvalues via Mobius inversion along a lattice, a condition for diagonalizability of the transition matrix and some techniques for bounding the mixing time. In addition, we discuss several examples, such as Toom-Tsetlin models, an exchange walk for finite Coxeter groups, as well as examples previously studied by the authors, such as nonabelian sandpile models and the promotion Markov chain on posets. Many of these examples can be viewed as random walks on quotients of free tree monoids, a new class of monoids whose combinatorics we develop.

Sidewall inclined slot in a rectangular waveguide: Theory and experiment

A novel analysis to compute the admittance characteristics of the slots cut in the narrow wall of a rectangular waveguide, which includes the corner diffraction effects and the finite waveguide wall thickness, is presented. A coupled magnetic field integral equation is formulated at the slot aperture which is solved by the Galerkin approach of the method of moments using entire domain sinusoidal basis functions. The externally scattered fields are computed using the finite difference method (FDM) coupled with the measured equation of invariance (MEI). The guide wall thickness forms a closed cavity and the fields inside it are evaluated using the standard FDM. The fields scattered inside the waveguide are formulated in the spectral domain for faster convergence compared to the traditional spatial domain expansions. The computed results have been compared with the experimental results and also with the measured data published in previous literature. Good agreement between the theoretical and experimental results is obtained to demonstrate the validity of the present analysis.

Einstein Relation in n-Channel Inversion Layers of Nonlinear Optical, Optoelectronic and Related Materials: Simplified Theory, Relative Comparison and Suggestion for an Experimental Determination

In this paper, we study the Einstein relation for the diffusivity to mobility ratio (DMR) in n-channel inversion layers of non-linear optical materials on the basis of a newly formulated electron dispersion relation by considering their special properties within the frame work of k.p formalism. The results for the n-channel inversion layers of III-V, ternary and quaternary materials form a special case of our generalized analysis. The DMR for n-channel inversion layers of II-VI, IV-VI and stressed materials has been investigated by formulating the respective 2D electron dispersion laws. It has been found, taking n-channel inversion layers of CdGeAs2, Cd(3)AS(2), InAs, InSb, Hg1-xCdxTe, In1-xGaxAsyP1-y lattice matched to InP, CdS, PbTe, PbSnTe, Pb1-xSnxSe and stressed InSb as examples, that the DMR increases with the increasing surface electric field with different numerical values and the nature of the variations are totally band structure dependent. The well-known expression of the DMR for wide gap materials has been obtained as a special case under certain limiting conditions and this compatibility is an indirect test for our generalized formalism. Besides, an experimental method of determining the 2D DMR for n-channel inversion layers having arbitrary dispersion laws has been suggested.

Molecular theory for the effects of specific solute-solvent interaction on the diffusion of a solute particle in a molecular liquid

An understanding of the effect of specific solute-solvent interactions on the diffusion of a solute probe is a long standing problem of physical chemistry. In this paper a microscopic treatment of this effect is presented. The theory takes into account the modification of the solvent structure around the solute due to this specific interaction between them. It is found that for strong, attractive interaction, there is an enhanced coupling between the solute and the solvent dynamic modes (in particular, the density mode), which leads to a significant increase in the friction on the solute. The diffusion coefficient of the solute is found to depend strongly and nonlinearly on the magnitude of the attractive interaction. An interesting observation is that specific solute-solvent interaction can induce a crossover from a sliplike to a sticklike diffusion. In the limit of strong attractive interaction, we recover a dynamic version of the solvent-berg picture. On the other hand, for repulsive interaction, the diffusion coefficient of the solute increases. These results are in qualitative agreement with recent experimental observations.

Precipitation In Small Systems--II. Mean Field Equations More Effective Than Population Balance

Part I (Manjunath et al., 1994, Chem. Engng Sci. 49, 1451-1463) of this paper showed that the random particle numbers and size distributions in precipitation processes in very small drops obtained by stochastic simulation techniques deviate substantially from the predictions of conventional population balance. The foregoing problem is considered in this paper in terms of a mean field approximation obtained by applying a first-order closure to an unclosed set of mean field equations presented in Part I. The mean field approximation consists of two mutually coupled partial differential equations featuring (i) the probability distribution for residual supersaturation and (ii) the mean number density of particles for each size and supersaturation from which all average properties and fluctuations can be calculated. The mean field equations have been solved by finite difference methods for (i) crystallization and (ii) precipitation of a metal hydroxide both occurring in a single drop of specified initial supersaturation. The results for the average number of particles, average residual supersaturation, the average size distribution, and fluctuations about the average values have been compared with those obtained by stochastic simulation techniques and by population balance. This comparison shows that the mean field predictions are substantially superior to those of population balance as judged by the close proximity of results from the former to those from stochastic simulations. The agreement is excellent for broad initial supersaturations at short times but deteriorates progressively at larger times. For steep initial supersaturation distributions, predictions of the mean field theory are not satisfactory thus calling for higher-order approximations. The merit of the mean field approximation over stochastic simulation lies in its potential to reduce expensive computation times involved in simulation. More effective computational techniques could not only enhance this advantage of the mean field approximation but also make it possible to use higher-order approximations eliminating the constraints under which the stochastic dynamics of the process can be predicted accurately.

Certain Aspects Related To Computation By Modified Crack Closure Integral(MCCI)

This paper presents the proper computational approach for the estimation of strain energy release rates by modified crack closure integral (MCCI). In particular, in the estimation of consistent nodal force vectors used in the MCCI expressions for quarter-point singular elements (wherein all the nodal force vectors participate in computation of strain energy release rates by MCCI). The numerical example of a centre crack tension specimen under uniform loading is presented to illustrate the approach.