Scalable remote homology detection and fold recognition in massive protein networks

The global connectivities in very large protein similarity networks contain traces of evolution among the proteins for detecting protein remote evolutionary relations or structural similarities. To investigate how well a protein network captures the evolutionary information, a key limitation is the intensive computation of pairwise sequence similarities needed to construct very large protein networks. In this article, we introduce label propagation on low-rank kernel approximation (LP-LOKA) for searching massively large protein networks. LP-LOKA propagates initial protein similarities in a low-rank graph by Nyström approximation without computing all pairwise similarities. With scalable parallel implementations based on distributed-memory using message-passing interface and Apache-Hadoop/Spark on cloud, LP-LOKA can search protein networks with one million proteins or more. In the experiments on Swiss-Prot/ADDA/CASP data, LP-LOKA significantly improved protein ranking over the widely used HMM-HMM or profile-sequence alignment methods utilizing large protein networks. It was observed that the larger the protein similarity network, the better the performance, especially on relatively small protein superfamilies and folds. The results suggest that computing massively large protein network is necessary to meet the growing need of annotating proteins from newly sequenced species and LP-LOKA is both scalable and accurate for searching massively large protein networks.     

Widespread polyphyly among Alopiinae snail genera: when phylogeny mirrors biogeography more closely than morphology

Consider a group of species that is evenly divided by an easily identifiable complex morphological character. Most biologists would assume that this character should provide better phylogenetic information than, say, the spatial distribution of these species over a fairly continuous 500-km radius area. Paradoxically, this is not the case among terrestrial snail genera in the clausiliid subfamily Alopiinae. Phylogenetic analysis using the nuclear markers ITS1/ITS2 and mitochondrial markers COI/12S reveals widespread homoplasy in the clausilial apparatus (a complex aperture-closing mechanism), and concomitant extensive polyphyly among Carinigera, Isabellaria, and Sericata. In contrast, phylogenetic relationships as revealed by molecular data are closely congruent with biogeography at a relatively small scale. A combination of extremely low vagility and extremely high morphological convergence has conspired to produce this unexpected result. Implications as to the function of the clausilial apparatus are discussed.     

Mean residence time of molecules diffusing in a cell bounded by a semi-permeable membrane: Monte Carlo simulations and an expression relating membrane transition probability to permeability

 The rapid exchange of water across erythrocyte membranes is readily measured using an NMR method that entails doping a suspension of cells with a moderately high concentration of Mn²⁺ and measuring the rate of transverse relaxation of the nuclear magnetisation. Analysis of the data yields an estimate of the rate constant for membrane transport, from which the membrane permeability can be determined. It is assumed in the analysis that the efflux rate of the water is solely a function of the rate of membrane permeation and that the time it takes for intracellular water molecules to diffuse to the membrane is relatively insignificant. The limits of this assumption were explored by using random-walk simulations of diffusion in cells modelled as parallel planes, spheres, and biconcave discs. The rate of membrane transport was specified in terms of a transition probability but it was not initially clear what the relationship should be between this parameter and the diffusional membrane permeability P _d. This relationship was derived and used to show that the mean residence time for a water molecule is determined by P _d when the diffusion coefficient is above a certain threshold value; it is determined by the distance to the membrane below that value. Received: 7 January 2000 / Revised version: 4 April 2000 / Accepted: 4 April 2000     

Distributed torsion angle grid search in high dimensions: A systematic approach to NMR structure determination

Two complementary approaches for systematic search in torsion angle space are described for the generation of all conformations of polypeptides which satisfy experimental NMR restraints, hard-sphere van der Waals radii, and rigid covalent geometry. The first procedure is based on a recursive, tree search algorithm for the examination of linear chains of torsion angles, and uses a novel treatment to propagate the search results to neighboring regions so that the structural consequences of the restraints are fully realized. The second procedure is based on a binary combination of torsion vector spaces for connected submolecules, and produces intermediate results in Cartesian space for a more robust restraint analysis. Restraints for NMR applications include bounds on torsion angles and internuclear distances, including relational and degenerate restraints involving equivalent and nonstereoassigned protons. To illustrate these methods, conformation search results are given for the tetrapeptide APGA restrained to an idealized -turn conformation, an alanine octapeptide restrained to a right-handed helical conformation, and the structured region of the peptide SYPFDV.     

Tug-of-war model for the two-bandit problem: Nonlocally-correlated parallel exploration via resource conservation

We propose a model - the “tug-of-war (TOW) model” - to conduct unique parallel searches using many nonlocally-correlated search agents. The model is based on the property of a single-celled amoeba, the true slime mold Physarum, which maintains a constant intracellular resource volume while collecting environmental information by concurrently expanding and shrinking its branches. The conservation law entails a “nonlocal correlation” among the branches, i.e., volume increment in one branch is immediately compensated by volume decrement(s) in the other branch(es). This nonlocal correlation was shown to be useful for decision making in the case of a dilemma. The multi-armed bandit problem is to determine the optimal strategy for maximizing the total reward sum with incompatible demands, by either exploiting the rewards obtained using the already collected information or exploring new information for acquiring higher payoffs involving risks. Our model can efficiently manage the “exploration-exploitation dilemma” and exhibits good performances. The average accuracy rate of our model is higher than those of well-known algorithms such as the modified ?-greedy algorithm and modified softmax algorithm, especially, for solving relatively difficult problems. Moreover, our model flexibly adapts to changing environments, a property essential for living organisms surviving in uncertain environments.     

Microfluidic formation of single cell array for parallel analysis of Ca release-activated Ca (CRAC) channel activation and inhibition

High-throughput single cell analysis is required for understanding and predicting the complex stochastic responses of individual cells in changing environments. We have designed a microfluidic device consisting of parallel, independent channels with cell-docking structures for the formation of an array of individual cells. The microfluidic cell array was used to quantify single cell responses and the distribution of response patterns of calcium channels among a population of individual cells. In this device, 15 cell-docking units in each channel were fabricated with each unit containing 5 sandbag structures, such that an array of individual cells was formed in 8 independent channels. Single cell responses to different treatments in different channels were monitored in parallel to study the effects of the specific activator and inhibitor of the Ca²⁺ release-activated Ca²⁺ (CRAC) channels. Multichannel detection was performed to obtain the response patterns of the population of cells within this single cell array. The results demonstrate that it is possible to acquire single cell features in multichannels simultaneously with passive structural control, which provides an opportunity for high-throughput single cell response analysis in a microfluidic chip.     

A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem

We present a P system with replicated rewriting to solve the Maximum Clique Problem for a graph. Strings representing cliques are built gradually. This involves the use of inhibitors that control the space of all generated solutions to the problem. Calculating the maximum clique for a graph is a highly relevant issue not only on purely computational grounds, but also because of its relationship to fundamental problems in genomics. We propose to implement the designed P system by means of a DNA algorithm. This algorithm is then compared with two standard papers that addressed the same problem and its DNA implementation in the past. This comparison is carried out on the basis of a series of computational and physical parameters. Our solution features a significantly lower cost in terms of time, the number and size of strands, as well as the simplicity of the biological implementation.     

Malleable applications for scalable high performance computing

Iterative applications are known to run as slow as their slowest computational component. This paper introduces malleability, a new dynamic reconfiguration strategy to overcome this limitation. Malleability is the ability to dynamically change the data size and number of computational entities in an application. Malleability can be used by middleware to autonomously reconfigure an application in response to dynamic changes in resource availability in an architecture-aware manner, allowing applications to optimize the use of multiple processors and diverse memory hierarchies in heterogeneous environments. The modular Internet Operating System (IOS) was extended to reconfigure applications autonomously using malleability. Two different iterative applications were made malleable. The first is used in astronomical modeling, and representative of maximum-likelihood applications was made malleable in the SALSA programming language. The second models the diffusion of heat over a two dimensional object, and is representative of applications such as partial differential equations and some types of distributed simulations. Versions of the heat application were made malleable both in SALSA and MPI. Algorithms for concurrent data redistribution are given for each type of application. Results show that using malleability for reconfiguration is 10 to 100 times faster on the tested environments. The algorithms are also shown to be highly scalable with respect to the quantity of data involved. While previous work has shown the utility of dynamically reconfigurable applications using only computational component migration, malleability is shown to provide up to a 15% speedup over component migration alone on a dynamic cluster environment. This work is part of an ongoing research effort to enable applications to be highly reconfigurable and autonomously modifiable by middleware in order to efficiently utilize distributed environments. Grid computing environments are becoming increasingly heterogeneous and dynamic, placing new demands on applications’ adaptive behavior. This work shows that malleability is a key aspect in enabling effective dynamic reconfiguration of iterative applications in these environments.

Performance analysis of MPI collective operations

Previous studies of application usage show that the performance of collective communications are critical for high-performance computing. Despite active research in the field, both general and feasible solution to the optimization of collective communication problem is still missing. In this paper, we analyze and attempt to improve intra-cluster collective communication in the context of the widely deployed MPI programming paradigm by extending accepted models of point-to-point communication, such as Hockney, LogP/LogGP, and PLogP, to collective operations. We compare the predictions from models against the experimentally gathered data and using these results, construct optimal decision function for broadcast collective. We quantitatively compare the quality of the model-based decision functions to the experimentally-optimal one. Additionally, in this work, we also introduce a new form of an optimized tree-based broadcast algorithm, splitted-binary. Our results show that all of the models can provide useful insights into various aspects of the different algorithms as well as their relative performance. Still, based on our findings, we believe that the complete reliance on models would not yield optimal results. In addition, our experimental results have identified the gap parameter as being the most critical for accurate modeling of both the classical point-to-point-based pipeline and our extensions to fan-out topologies.