Bringing Web 2.0 to bioinformatics

Enabling deft data integration from numerous, voluminous andheterogeneous data sources is a major bioinformatic challenge.Several approaches have been proposed to address this challenge,including data warehousing and federated databasing. Yet despitethe rise of these approaches, integration of data from multiplesources remains problematic and toilsome. These two approachesfollow a user-to-computer communication model for data exchange,and do not facilitate a broader concept of data sharing or collaborationamong users. In this report, we discuss the potential of Web2.0 technologies to transcend this model and enhance bioinformaticsresearch. We propose a Web 2.0-based Scientific Social Community(SSC) model for the implementation of these technologies. Byestablishing a social, collective and collaborative platformfor data creation, sharing and integration, we promote a webservices-based pipeline featuring web services for computer-to-computerdata exchange as users add value. This pipeline aims to simplifydata integration and creation, to realize automatic analysis,and to facilitate reuse and sharing of data. SSC can fostercollaboration and harness collective intelligence to createand discover new knowledge. In addition to its research potential,we also describe its potential role as an e-learning platformin education. We discuss lessons from information technology,predict the next generation of Web (Web 3.0), and describe itspotential impact on the future of bioinformatics studies.      

What failure in collective decision-making tells us about metacognition

Condorcet (1785) proposed that a majority vote drawn from individual, independent and fallible (but not totally uninformed) opinions provides near-perfect accuracy if the number of voters is adequately large. Research in social psychology has since then repeatedly demonstrated that collectives can and do fail more often than expected by Condorcet. Since human collective decisions often follow from exchange of opinions, these failures provide an exquisite opportunity to understand human communication of metacognitive confidence. This question can be addressed by recasting collective decision-making as an information-integration problem similar to multisensory (cross-modal) perception. Previous research in systems neuroscience shows that one brain can integrate information from multiple senses nearly optimally. Inverting the question, we ask: under what conditions can two brains integrate information about one sensory modality optimally? We review recent work that has taken this approach and report discoveries about the quantitative limits of collective perceptual decision-making, and the role of the mode of communication and feedback in collective decision-making. We propose that shared metacognitive confidence conveys the strength of an individual's opinion and its reliability inseparably. We further suggest that a functional role of shared metacognition is to provide substitute signals in situations where outcome is necessary for learning but unavailable or impossible to establish.     

Nonparametric simulation-based statistics for detecting linkage in general pedigrees.

We present here four nonparametric statistics for linkage analysis that test whether pairs of affected relatives share marker alleles more often than expected. These statistics are based on simulating the null distribution of a given statistic conditional on the unaffecteds' marker genotypes. Each statistic uses a different measure of marker sharing: the SimAPM statistic uses the simulation-based affected-pedigree-member measure based on identity-by-state (IBS) sharing. The SimKIN (kinship) measure is 1.0 for identity-by-descent (IBD) sharing, 0.0 for no IBD status sharing, and the kinship coefficient when the IBD status is ambiguous. The simulation-based IBD (SimIBD) statistic uses a recursive algorithm to determine the probability of two affecteds sharing a specific allele IBD. The SimISO statistic is identical to SimIBD, except that it also measures marker similarity between unaffected pairs. We evaluated our statistics on data simulated under different two-locus disease models, comparing our results to those obtained with several other nonparametric statistics. Use of IBD information produces dramatic increases in power over the SimAPM method, which uses only IBS information. The power of our best statistic in most cases meets or exceeds the power of the other nonparametric statistics. Furthermore, our statistics perform comparisons between all affected relative pairs within general pedigrees and are not restricted to sib pairs or nuclear families.     

Protein threading with profiles and distance constraints using clique based algorithms

With the advent of experimental technologies like chemical cross-linking, it has become possible to obtain distances between specific residues of a newly sequenced protein. These types of experiments usually are less time consuming than X-ray crystallography or NMR. Consequently, it is highly desired to develop a method that incorporates this distance information to improve the performance of protein threading methods. However, protein threading with profiles in which constraints on distances between residues are given is known to be NP-hard. By using the notion of a maximum edge-weight clique finding algorithm, we introduce a more efficient method called FTHREAD for profile threading with distance constraints that is 18 times faster than its predecessor CLIQUETHREAD. Moreover, we also present a novel practical algorithm NTHREAD for profile threading with Non-strict constraints. The overall performance of FTHREAD on a data set shows that although our algorithm uses a simple threading function, our algorithm performs equally well as some of the existing methods. Particularly, when there are some unsatisfied constraints, NTHREAD (Non-strict constraints threading algorithm) performs better than threading with FTHREAD (Strict constraints threading algorithm). We have also analyzed the effects of using a number of distance constraints. This algorithm helps the enhancement of alignment quality between the query sequence and template structure, once the corresponding template structure is determined for the target sequence.     

Collective animal behavior from Bayesian estimation and probability matching

Animals living in groups make movement decisions that depend, among other factors, on social interactions with other group members. Our present understanding of social rules in animal collectives is mainly based on empirical fits to observations, with less emphasis in obtaining first-principles approaches that allow their derivation. Here we show that patterns of collective decisions can be derived from the basic ability of animals to make probabilistic estimations in the presence of uncertainty. We build a decision-making model with two stages: Bayesian estimation and probabilistic matching. In the first stage, each animal makes a Bayesian estimation of which behavior is best to perform taking into account personal information about the environment and social information collected by observing the behaviors of other animals. In the probability matching stage, each animal chooses a behavior with a probability equal to the Bayesian-estimated probability that this behavior is the most appropriate one. This model derives very simple rules of interaction in animal collectives that depend only on two types of reliability parameters, one that each animal assigns to the other animals and another given by the quality of the non-social information. We test our model by obtaining theoretically a rich set of observed collective patterns of decisions in three-spined sticklebacks, Gasterosteus aculeatus, a shoaling fish species. The quantitative link shown between probabilistic estimation and collective rules of behavior allows a better contact with other fields such as foraging, mate selection, neurobiology and psychology, and gives predictions for experiments directly testing the relationship between estimation and collective behavior.     

Bioacoustics for species management: two case studies with a Hawaiian forest bird

The management of animal endangered species requires detailed information on their distribution and abundance, which is often hard to obtain. When animals communicate using sounds, one option is to use automatic sound recorders to gather information on the species for long periods of time with low effort. One drawback of this method is that processing all the information manually requires large amounts of time and effort. Our objective was to create a relatively “user‐friendly” (i.e., that does not require big programming skills) automatic detection algorithm to improve our ability to get basic data from sound‐emitting animal species. We illustrate our algorithm by showing two possible applications with the Hawai'i ‘Amakihi, Hemignathus virens virens, a forest bird from the island of Hawai'i. We first characterized the ‘Amakihi song using recordings from areas where the species is present in high densities. We used this information to train a classification algorithm, the support vector machine (SVM), in order to identify ‘Amakihi songs from a series of potential songs. We then used our algorithm to detect the species in areas where its presence had not been previously confirmed. We also used the algorithm to compare the relative abundance of the species in different areas where management actions may be applied. The SVM had an accuracy of 86.5% in identifying ‘Amakihi. We confirmed the presence of the ‘Amakihi at the study area using the algorithm. We also found that the relative abundance of ‘Amakihi changes among study areas, and this information can be used to assess where management strategies for the species should be better implemented. Our automatic song detection algorithm is effective, “user‐friendly” and can be very useful for optimizing the management and conservation of those endangered animal species that communicate acoustically.     

Negative feedback from maternal signals reduces false alarms by collectively signalling offspring

Within animal groups, individuals can learn of a predator's approach by attending to the behaviour of others. This use of social information increases an individual's perceptual range, but can also lead to the propagation of false alarms. Error copying is especially likely in species that signal collectively, because the coordination required for collective displays relies heavily on social information. Recent evidence suggests that collective behaviour in animals is, in part, regulated by negative feedback. Negative feedback may reduce false alarms by collectively signalling animals, but this possibility has not yet been tested. We tested the hypothesis that negative feedback increases the accuracy of collective signalling by reducing the production of false alarms. In the treehopper Umbonia crassicornis, clustered offspring produce collective signals during predator attacks, advertising the predator's location to the defending mother. Mothers signal after evicting the predator, and we show that this maternal communication reduces false alarms by offspring. We suggest that maternal signals elevate offspring signalling thresholds. This is, to our knowledge, the first study to show that negative feedback can reduce false alarms by collectively behaving groups.     

A hierarchical modeling framework for multiple observer transect surveys

Ecologists often use multiple observer transect surveys to census animal populations. In addition to animal counts, these surveys produce sequences of detections and non-detections for each observer. When combined with additional data (i.e. covariates such as distance from the transect line), these sequences provide the additional information to estimate absolute abundance when detectability on the transect line is less than one. Although existing analysis approaches for such data have proven extremely useful, they have some limitations. For instance, it is difficult to extrapolate from observed areas to unobserved areas unless a rigorous sampling design is adhered to; it is also difficult to share information across spatial and temporal domains or to accommodate habitat-abundance relationships. In this paper, we introduce a hierarchical modeling framework for multiple observer line transects that removes these limitations. In particular, abundance intensities can be modeled as a function of habitat covariates, making it easier to extrapolate to unsampled areas. Our approach relies on a complete data representation of the state space, where unobserved animals and their covariates are modeled using a reversible jump Markov chain Monte Carlo algorithm. Observer detections are modeled via a bivariate normal distribution on the probit scale, with dependence induced by a distance-dependent correlation parameter. We illustrate performance of our approach with simulated data and on a known population of golf tees. In both cases, we show that our hierarchical modeling approach yields accurate inference about abundance and related parameters. In addition, we obtain accurate inference about population-level covariates (e.g. group size). We recommend that ecologists consider using hierarchical models when analyzing multiple-observer transect data, especially when it is difficult to rigorously follow pre-specified sampling designs. We provide a new R package, hierarchicalDS, to facilitate the building and fitting of these models.     

Imitation Combined with a Characteristic Stimulus Duration Results in Robust Collective Decision-Making

For group-living animals, reaching consensus to stay cohesive is crucial for their fitness, particularly when collective motion starts and stops. Understanding the decision-making at individual and collective levels upon sudden disturbances is central in the study of collective animal behavior, and concerns the broader question of how information is distributed and evaluated in groups. Despite the relevance of the problem, well-controlled experimental studies that quantify the collective response of groups facing disruptive events are lacking. Here we study the behavior of small-sized groups of uninformed individuals subject to the departure and stop of a trained conspecific. We find that the groups reach an effective consensus: either all uninformed individuals follow the trained one (and collective motion occurs) or none does. Combining experiments and a simple mathematical model we show that the observed phenomena results from the interplay between simple mimetic rules and the characteristic duration of the stimulus, here, the time during which the trained individual is moving away. The proposed mechanism strongly depends on group size, as observed in the experiments, and even if group splitting can occur, the most likely outcome is always a coherent collective group response (consensus). The prevalence of a consensus is expected even if the groups of naives face conflicting information, e.g. if groups contain two subgroups of trained individuals, one trained to stay and one trained to leave. Our results indicate that collective decision-making and consensus in (small) animal groups are likely to be self-organized phenomena that do not involve concertation or even communication among the group members.     

Rapid Sampling of Molecular Motions with Prior Information Constraints

Proteins are active, flexible machines that perform a range of different functions. Innovative experimental approaches may now provide limited partial information about conformational changes along motion pathways of proteins. There is therefore a need for computational approaches that can efficiently incorporate prior information into motion prediction schemes. In this paper, we present PathRover, a general setup designed for the integration of prior information into the motion planning algorithm of rapidly exploring random trees (RRT). Each suggested motion pathway comprises a sequence of low-energy clash-free conformations that satisfy an arbitrary number of prior information constraints. These constraints can be derived from experimental data or from expert intuition about the motion. The incorporation of prior information is very straightforward and significantly narrows down the vast search in the typically high-dimensional conformational space, leading to dramatic reduction in running time. To allow the use of state-of-the-art energy functions and conformational sampling, we have integrated this framework into Rosetta, an accurate protocol for diverse types of structural modeling. The suggested framework can serve as an effective complementary tool for molecular dynamics, Normal Mode Analysis, and other prevalent techniques for predicting motion in proteins. We applied our framework to three different model systems. We show that a limited set of experimentally motivated constraints may effectively bias the simulations toward diverse predicates in an outright fashion, from distance constraints to enforcement of loop closure. In particular, our analysis sheds light on mechanisms of protein domain swapping and on the role of different residues in the motion.     

A Scheme to Optimize Flow Routing and Polling Switch Selection of Software Defined Networks

This paper aims at minimizing the communication cost for collecting flow information in Software Defined Networks (SDN). Since flow-based information collecting method requires too much communication cost, and switch-based method proposed recently cannot benefit from controlling flow routing, jointly optimize flow routing and polling switch selection is proposed to reduce the communication cost. To this end, joint optimization problem is formulated as an Integer Linear Programming (ILP) model firstly. Since the ILP model is intractable in large size network, we also design an optimal algorithm for the multi-rooted tree topology and an efficient heuristic algorithm for general topology. According to extensive simulations, it is found that our method can save up to 55.76% communication cost compared with the state-of-the-art switch-based scheme.     

Determining protein loop conformation using scaling-relaxation techniques.

We recently developed a rapid loop closure algorithm in which bond lengths are scaled to constrain the ends of a segment to match a known distance and then gradually relaxed to their standard values, with boundary constraints maintained. Although the algorithm predicted the Zif286 zinc-finger loop to within approximately 2 A, it had a serious limitation that made its more general use tentative: it omitted the atomic environment of the loop. Here we report an extension of the algorithm to take into account the protein environment surrounding a given loop from the outset of the conformational search and show that it predicts structure with an efficiency and accuracy that could not be achieved without continuous environmental inclusion. The algorithm should be widely applicable to structure determination when complete experimental information is unavailable.     

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.

Gossip-Based Solutions for Discrete Rendezvous in Populations of Communicating Agents

The objective of the rendezvous problem is to construct a method that enables a population of agents to agree on a spatial (and possibly temporal) meeting location. We introduce the buffered gossip algorithm as a general solution to the rendezvous problem in a discrete domain with direct communication between decentralized agents. We compare the performance of the buffered gossip algorithm against the well known uniform gossip algorithm. We believe that a buffered solution is preferable to an unbuffered solution, such as the uniform gossip algorithm, because the use of a buffer allows an agent to use multiple information sources when determining its desired rendezvous point, and that access to multiple information sources may improve agent decision making by reinforcing or contradicting an initial choice. To show that the buffered gossip algorithm is an actual solution for the rendezvous problem, we construct a theoretical proof of convergence and derive the conditions under which the buffered gossip algorithm is guaranteed to produce a consensus on rendezvous location. We use these results to verify that the uniform gossip algorithm also solves the rendezvous problem. We then use a multi-agent simulation to conduct a series of simulation experiments to compare the performance between the buffered and uniform gossip algorithms. Our results suggest that the buffered gossip algorithm can solve the rendezvous problem faster than the uniform gossip algorithm; however, the relative performance between these two solutions depends on the specific constraints of the problem and the parameters of the buffered gossip algorithm.     

Simulating the Real Origins of Communication

How communication systems emerge is a topic of relevance to several academic disciplines. Numerous existing models, both mathematical and computational, study this emergence. However, with few exceptions, these models all build some form of communication into their initial specification. Consequently, what these models study is how communication systems transition from one form to another, and not how communication itself emerges in the first place. Here we present a new computational model of the emergence of communication which, unlike previous models, does not pre-specify the existence of communication. We conduct two experiments using this model, in order to derive general statements about how communication systems emerge. The two main routes to communication that we identify correspond with findings from the empirical literature on the evolution of animal signals. We use this finding to explain when and why we should expect communication to emerge in nature. We also compare our model to experimental research on the origins of human communication systems, and hence show that humans are an important exception to the general trends we observe. We argue that this is because humans, and probably only humans, are able to ‘signal signalhood’, i.e. to express communicative intentions.     

Self-organizing circuit assembly through spatiotemporally coordinated neuronal migration within geometric constraints

Background

Neurons are dynamically coupled with each other through neurite-mediated adhesion during development. Understanding the collective behavior of neurons in circuits is important for understanding neural development. While a number of genetic and activity-dependent factors regulating neuronal migration have been discovered on single cell level, systematic study of collective neuronal migration has been lacking. Various biological systems are shown to be self-organized, and it is not known if neural circuit assembly is self-organized. Besides, many of the molecular factors take effect through spatial patterns, and coupled biological systems exhibit emergent property in response to geometric constraints. How geometric constraints of the patterns regulate neuronal migration and circuit assembly of neurons within the patterns remains unexplored.

Methodology/Principal Findings

We established a two-dimensional model for studying collective neuronal migration of a circuit, with hippocampal neurons from embryonic rats on Matrigel-coated self-assembled monolayers (SAMs). When the neural circuit is subject to geometric constraints of a critical scale, we found that the collective behavior of neuronal migration is spatiotemporally coordinated. Neuronal somata that are evenly distributed upon adhesion tend to aggregate at the geometric center of the circuit, forming mono-clusters. Clustering formation is geometry-dependent, within a critical scale from 200 µm to approximately 500 µm. Finally, somata clustering is neuron-type specific, and glutamatergic and GABAergic neurons tend to aggregate homo-philically.

Conclusions/Significance

We demonstrate self-organization of neural circuits in response to geometric constraints through spatiotemporally coordinated neuronal migration, possibly via mechanical coupling. We found that such collective neuronal migration leads to somata clustering, and mono-cluster appears when the geometric constraints fall within a critical scale. The discovery of geometry-dependent collective neuronal migration and the formation of somata clustering in vitro shed light on neural development in vivo.     

A distance geometry program for determining the structures of small proteins and other macromolecules from nuclear magnetic resonance measurements of intramolecular1H−1H proximities in solution

DISGEO is a new implementation of a distance geometry algorithm which has been specialized for the calculation of macromolecular conformation from distance measurements obtained by two-dimensional nuclear Overhauser enhancement spectroscopy. The improvements include (1) a decomposition of the complete embedding process into two successive, more tractable calculations by the use of “substructures”, (2) a compact data structure for storing incomplete distance information on a structure, (3) a more efficient shortest-path algorithm for computing the triangle inequality limits on all distances from this information, (4) a new algorithm for selecting random metric spaces from within these limits, (5) the use of chirality constraints to obtain good covalent geometry without the use ofad hoc weights or excessive optimization. The utility of the resultant program with nuclear magnetic resonance data is demonstrated by embedding complete spatial structures for the protein basic pancreatic trypsin inhibitor vs all 508 intramolecular, interresidue proton-proton contacts shorter than 4.0 Å that were present in its crystal structure. The crystal structure could be reproduced from this data set to within 1.3 Å minimum root mean square coordinate difference between the backbone atoms. We conclude that the information potentially available from nuclear magnetic resonance experiments in solution is sufficient to define the spatial structure of small proteins.     

Systemic Testing on Bradley-Terry Model against Nonlinear Ranking Hierarchy

We take a system point of view toward constructing any power or ranking hierarchy onto a society of human or animal players. The most common hierarchy is the linear ranking, which is habitually used in nearly all real-world problems. A stronger version of linear ranking via increasing and unvarying winning potentials, known as Bradley-Terry model, is particularly popular. Only recently non-linear ranking hierarchy is discussed and developed through recognition of dominance information contents beyond direct dyadic win-and-loss. We take this development further by rigorously arguing for the necessity of accommodating system''s global pattern information contents, and then introducing a systemic testing on Bradley-Terry model. Our test statistic with an ensemble based empirical distribution favorably compares with the Deviance test equipped with a Chi-squared asymptotic approximation. Several simulated and real data sets are analyzed throughout our development.