On an exact populationary model of genetic algorithms

Genetic algorithms (GAs) are search methods that are being employed in a multitude of applications with extremely large search spaces. Recently, there has been considerable interest among GA researchers in understanding and formalizing the working of GAs. In an earlier paper, we have introduced the notion of binomially distributed populations as the central idea behind an exact ''populationary'' model of the large-population dynamics of the GA operators for objective functions called ''functions of unitation.'' In this paper, we extend this populationary model of GA dynamics to a more general class of objective functions called functions of unitation variables. We generalize the notion of a binomially distributed population to a generalized binomially distributed population (GBDP). We show that the effects of selection, crossover, and mutation can be exactly modelled after decomposing the population into GBDPs. Based on this generalized model, we have implemented a GA simulator for functions of two unitation variables-GASIM 2, and the distributions predicted by GASIM 2 match with those obtained from actual GA runs. The generalized populationary model of GA dynamics not only presents a novel and natural way of interpreting the workings of GAs with large populations, but it also provides for an efficient implementation of the model as a GA simulator. (C) Elsevier Science Inc. 1997.

Quantum clustering and network analysis of MD simulation trajectories to probe the conformational ensembles of protein-ligand interactions

In this article, we present a novel application of a quantum clustering (QC) technique to objectively cluster the conformations, sampled by molecular dynamics simulations performed on different ligand bound structures of the protein. We further portray each conformational population in terms of dynamically stable network parameters which beautifully capture the ligand induced variations in the ensemble in atomistic detail. The conformational populations thus identified by the QC method and verified by network parameters are evaluated for different ligand bound states of the protein pyrrolysyl-tRNA synthetase (DhPylRS) from D. hafniense. The ligand/environment induced re-distribution of protein conformational ensembles forms the basis for understanding several important biological phenomena such as allostery and enzyme catalysis. The atomistic level characterization of each population in the conformational ensemble in terms of the re-orchestrated networks of amino acids is a challenging problem, especially when the changes are minimal at the backbone level. Here we demonstrate that the QC method is sensitive to such subtle changes and is able to cluster MD snapshots which are similar at the side-chain interaction level. Although we have applied these methods on simulation trajectories of a modest time scale (20 ns each), we emphasize that our methodology provides a general approach towards an objective clustering of large-scale MD simulation data and may be applied to probe multistate equilibria at higher time scales, and to problems related to protein folding for any protein or protein-protein/RNA/DNA complex of interest with a known structure.

On the achievable rates of sources having a group alphabet in a distributed source coding setting

We consider the problem of compression via homomorphic encoding of a source having a group alphabet. This is motivated by the problem of distributed function computation, where it is known that if one is only interested in computing a function of several sources, then one can at times improve upon the compression rate required by the Slepian-Wolf bound. The functions of interest are those which could be represented by the binary operation in the group. We first consider the case when the source alphabet is the cyclic Abelian group, Zpr. In this scenario, we show that the set of achievable rates provided by Krithivasan and Pradhan [1], is indeed the best possible. In addition to that, we provide a simpler proof of their achievability result. In the case of a general Abelian group, an improved achievable rate region is presented than what was obtained by Krithivasan and Pradhan. We then consider the case when the source alphabet is a non-Abelian group. We show that if all the source symbols have non-zero probability and the center of the group is trivial, then it is impossible to compress such a source if one employs a homomorphic encoder. Finally, we present certain non-homomorphic encoders, which also are suitable in the context of function computation over non-Abelian group sources and provide rate regions achieved by these encoders.

Robust Formulations for Handling Uncertainty in Kernel Matrices

We study the problem of uncertainty in the entries of the Kernel matrix, arising in SVM formulation. Using Chance Constraint Programming and a novel large deviation inequality we derive a formulation which is robust to such noise. The resulting formulation applies when the noise is Gaussian, or has finite support. The formulation in general is non-convex, but in several cases of interest it reduces to a convex program. The problem of uncertainty in kernel matrix is motivated from the real world problem of classifying proteins when the structures are provided with some uncertainty. The formulation derived here naturally incorporates such uncertainty in a principled manner leading to significant improvements over the state of the art. 1.

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

In this paper we consider the problem of learning an n × n kernel matrix from m(1) similarity matrices under general convex loss. Past research have extensively studied the m = 1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well knownMirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m2 log n 2) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n × n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL,which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVMsolver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

Indian Ocean dipole mode events in an ocean general circulation model

The evolution of the dipole mode (DM) events in the Indian Ocean is examined using an ocean model that is driven by the NCEP fluxes for the period 1975-1998. The positive DM events during 1997, 1994 and 1982 and negative DM events during 1996 and 1984-1985 are captured by the model and it reproduces both the surface and subsurface features associated with these events. In its positive phase, the DM is characterized by warmer than normal SST in the western Indian Ocean and cooler than normal SST in the eastern Indian Ocean. The DM events are accompanied by easterly wind anomalies along the equatorial Indian Ocean and upwelling-favorable alongshore wind anomalies along the coast of Sumatra. The Wyrtki jets are weak during positive DM events, and the thermocline is shallower than normal in the eastern Indian Ocean and deeper in the west. This anomaly pattern reverses during negative DM events. During the positive phase of the DM easterly wind anomalies excite an upwelling equatorial Kelvin wave. This Kelvin wave reflects from the eastern boundary as an upwelling Rossby wave which propagates westward across the equatorial Indian Ocean. The anomalies in the eastern Indian Ocean weaken after the Rossby wave passes. A similar process excites a downwelling Rossby wave during the negative phase. This Rossby wave is much weaker but wind forcing in the central equatorial Indian Ocean amplifies the downwelling and increases its westward phase speed. This Rossby wave initiates the deepening of the thermocline in the western Indian Ocean during the following positive phase of the DM. Rossby wave generated in the southern tropical Indian Ocean by Ekman pumping contributes to this warming. Concurrently, the temperature equation of the model shows upwelling and downwelling to be the most important mechanism during both positive events of 1994 and 1997. (C) 2002 Elsevier Science Ltd. All rights reserved.

General theories for the electrical transport properties of carbon nanotubes

We have shown that the general theories of metals and semiconductors can be employed to understand the diameter and voltage dependency of current through metallic and semiconducting carbon nanotubes, respectively. The current through a semiconducting multiwalled carbon nanotube (MWCNT) is associated with the energy gap that is different for different shells. The contribution of the outermost shell is larger as compared to the inner shells. The general theories can also explain the diameter dependency of maximum current through nanotubes. We have also compared the current carrying ability of a MWCNT and an array of the same diameter of single wall carbon nanotubes (SWCNTs) and found that MWCNTs are better suited and deserve further investigation for possible applications as interconnects.

Temperature profiles of accretion discs around rapidly rotating strange stars in general relativity: A comparison with neutron stars

We compute the temperature profiles of accretion discs around rapidly rotating strange stars, using constant gravitational mass equilibrium sequences of these objects, considering the full effect of general relativity. Beyond a certain critical value of stellar angular momentum (J), we observe the radius ( $r_{\rm orb}$) of the innermost stable circular orbit (ISCO) to increase with J (a property seen neither in rotating black holes nor in rotating neutron stars). The reason for this is traced to the crucial dependence of ${\rm d}r_{\rm orb}/{\rm d}J$ on the rate of change of the radial gradient of the Keplerian angular velocity at $r_{\rm orb}$ with respect to J. The structure parameters and temperature profiles obtained are compared with those of neutron stars, as an attempt to provide signatures for distinguishing between the two. We show that when the full gamut of strange star equation of state models, with varying degrees of stiffness are considered, there exists a substantial overlap in properties of both neutron stars and strange stars. However, applying accretion disc model constraints to rule out stiff strange star equation of state models, we notice that neutron stars and strange stars exclusively occupy certain parameter spaces. This result implies the possibility of distinguishing these objects from each other by sensitive observations through future X-ray detectors.

A General Route to Nanoparticle Thin Films and Coatings

Nanoparticles thin films have wide range of applications such as nanoelectronics, magnetic storage devices, SERS substrate fabrication, optical grating and antireflective coating. Present work describes a method to prepare large area nanoparticles thin film of the order of few square centimeters. Thin film deposition has been done successfully on a wide range of conducting as well as non conducting substrates such as carbon-coated copper grid, silicon, m-plane of alumina, glass and (100) plane of NaCl single crystal. SEM, TEM and AFM studies have been done for microstructural characterization of the thin films. A basic mechanism has been proposed towards the understanding of the deposition process.

Fault-Tolerant Average Execution Time Optimization for General Purpose Multi-Processor System-on Chips

Fault-tolerance is due to the semiconductor technology development important, not only for safety-critical systems but also for general-purpose (non-safety critical) systems. However, instead of guaranteeing that deadlines always are met, it is for general-purpose systems important to minimize the average execution time (AET) while ensuring fault-tolerance. For a given job and a soft (transient) error probability, we define mathematical formulas for AET that includes bus communication overhead for both voting (active replication) and rollback-recovery with checkpointing (RRC). And, for a given multi-processor system-on-chip (MPSoC), we define integer linear programming (ILP) models that minimize AET including bus communication overhead when: (1) selecting the number of checkpoints when using RRC, (2) finding the number of processors and job-to-processor assignment when using voting, and (3) defining fault-tolerance scheme (voting or RRC) per job and defining its usage for each job. Experiments demonstrate significant savings in AET.

Focussed Crawling with large scale Ordinal Regression Solvers

In this paper we propose a novel, scalable, clustering based Ordinal Regression formulation, which is an instance of a Second Order Cone Program (SOCP) with one Second Order Cone (SOC) constraint. The main contribution of the paper is a fast algorithm, CB-OR, which solves the proposed formulation more eficiently than general purpose solvers. Another main contribution of the paper is to pose the problem of focused crawling as a large scale Ordinal Regression problem and solve using the proposed CB-OR. Focused crawling is an efficient mechanism for discovering resources of interest on the web. Posing the problem of focused crawling as an Ordinal Regression problem avoids the need for a negative class and topic hierarchy, which are the main drawbacks of the existing focused crawling methods. Experiments on large synthetic and benchmark datasets show the scalability of CB-OR. Experiments also show that the proposed focused crawler outperforms the state-of-the-art.

Topological analysis of general linear networks

A new method of network analysis, a generalization in several different senses of existing methods and applicable to all networks for which a branch-admittance (or impedance) matrix can be formed, is presented. The treatment of network determinants is very general and essentially four terminal rather than three terminal, and leads to simple expressions based on trees of a simple graph associated with the network and matrix, and involving products of low-order, usually(2 times 2)determinants of tree-branch admittances, in addition to tree-branch products as in existing methods. By comparison with existing methods, the total number of trees and of tree pairs is usually considerably reduced, and this fact, together with an easy method of tree-pair sign determination which is also presented, makes the new method simpler in general. The method can be very easily adapted, by the use of infinite parameters, to accommodate ideal transformers, operational amplifiers, and other forms of network constraint; in fact, is thought to be applicable to all linear networks.