A graph-based semantic similarity measure for the gene ontology

Existing methods for calculating semantic similarities between pairs of Gene Ontology (GO) terms and gene products often rely on external databases like Gene Ontology Annotation (GOA) that annotate gene products using the GO terms. This dependency leads to some limitations in real applications. Here, we present a semantic similarity algorithm (SSA), that relies exclusively on the GO. When calculating the semantic similarity between a pair of input GO terms, SSA takes into account the shortest path between them, the depth of their nearest common ancestor, and a novel similarity score calculated between the definitions of the involved GO terms. In our work, we use SSA to calculate semantic similarities between pairs of proteins by combining pairwise semantic similarities between the GO terms that annotate the involved proteins. The reliability of SSA was evaluated by comparing the resulting semantic similarities between proteins with the functional similarities between proteins derived from expert annotations or sequence similarity. Comparisons with existing state-of-the-art methods showed that SSA is highly competitive with the other methods. SSA provides a reliable measure for semantics similarity independent of external databases of functional-annotation observations.     

The Edge-Disjoint Path Problem on Random Graphs by Message-Passing

We present a message-passing algorithm to solve a series of edge-disjoint path problems on graphs based on the zero-temperature cavity equations. Edge-disjoint paths problems are important in the general context of routing, that can be defined by incorporating under a unique framework both traffic optimization and total path length minimization. The computation of the cavity equations can be performed efficiently by exploiting a mapping of a generalized edge-disjoint path problem on a star graph onto a weighted maximum matching problem. We perform extensive numerical simulations on random graphs of various types to test the performance both in terms of path length minimization and maximization of the number of accommodated paths. In addition, we test the performance on benchmark instances on various graphs by comparison with state-of-the-art algorithms and results found in the literature. Our message-passing algorithm always outperforms the others in terms of the number of accommodated paths when considering non trivial instances (otherwise it gives the same trivial results). Remarkably, the largest improvement in performance with respect to the other methods employed is found in the case of benchmarks with meshes, where the validity hypothesis behind message-passing is expected to worsen. In these cases, even though the exact message-passing equations do not converge, by introducing a reinforcement parameter to force convergence towards a sub optimal solution, we were able to always outperform the other algorithms with a peak of 27% performance improvement in terms of accommodated paths. On random graphs, we numerically observe two separated regimes: one in which all paths can be accommodated and one in which this is not possible. We also investigate the behavior of both the number of paths to be accommodated and their minimum total length.     

Network-based Phenome-Genome Association Prediction by Bi-Random Walk

MotivationThe availability of ontologies and systematic documentations of phenotypes and their genetic associations has enabled large-scale network-based global analyses of the association between the complete collection of phenotypes (phenome) and genes. To provide a fundamental understanding of how the network information is relevant to phenotype-gene associations, we analyze the circular bigraphs (CBGs) in OMIM human disease phenotype-gene association network and MGI mouse phentoype-gene association network, and introduce a bi-random walk (BiRW) algorithm to capture the CBG patterns in the networks for unveiling human and mouse phenome-genome association. BiRW performs separate random walk simultaneously on gene interaction network and phenotype similarity network to explore gene paths and phenotype paths in CBGs of different sizes to summarize their associations as predictions.ResultsThe analysis of both OMIM and MGI associations revealed that majority of the phenotype-gene associations are covered by CBG patterns of small path lengths, and there is a clear correlation between the CBG coverage and the predictability of the phenotype-gene associations. In the experiments on recovering known associations in cross-validations on human disease phenotypes and mouse phenotypes, BiRW effectively improved prediction performance over the compared methods. The constructed global human disease phenome-genome association map also revealed interesting new predictions and phenotype-gene modules by disease classes.     

Navigation between initial and desired community states using shortcuts

Ecological management problems often involve navigating from an initial to a desired community state. We ask whether navigation without brute-force additions and deletions of species is possible via: adding/deleting a small number of individuals of a species, changing the environment, and waiting. Navigation can yield direct paths (single sequence of actions) or shortcut paths (multiple sequences of actions with lower cost than a direct path). We ask (1) when is non-brute-force navigation possible?; (2) do shortcuts exist and what are their properties?; and (3) what heuristics predict shortcut existence? Using a state diagram framework applied to several empirical datasets, we show that (1) non-brute-force navigation is only possible between some state pairs, (2) shortcuts exist between many state pairs; and (3) changes in abundance and richness are the strongest predictors of shortcut existence, independent of dataset and algorithm choices. State diagrams thus unveil hidden strategies for manipulating species coexistence and efficiently navigating between states.     

Cooperative navigation in robotic swarms

We study cooperative navigation for robotic swarms in the context of a general event-servicing scenario. In the scenario, one or more events need to be serviced at specific locations by robots with the required skills. We focus on the question of how the swarm can inform its members about events, and guide robots to event locations. We propose a solution based on delay-tolerant wireless communications: by forwarding navigation information between them, robots cooperatively guide each other towards event locations. Such a collaborative approach leverages on the swarm’s intrinsic redundancy, distribution, and mobility. At the same time, the forwarding of navigation messages is the only form of cooperation that is required. This means that the robots are free in terms of their movement and location, and they can be involved in other tasks, unrelated to the navigation of the searching robot. This gives the system a high level of flexibility in terms of application scenarios, and a high degree of robustness with respect to robot failures or unexpected events. We study the algorithm in two different scenarios, both in simulation and on real robots. In the first scenario, a single searching robot needs to find a single target, while all other robots are involved in tasks of their own. In the second scenario, we study collective navigation: all robots of the swarm navigate back and forth between two targets, which is a typical scenario in swarm robotics. We show that in this case, the proposed algorithm gives rise to synergies in robot navigation, and it lets the swarm self-organize into a robust dynamic structure. The emergence of this structure improves navigation efficiency and lets the swarm find shortest paths.     

A red knot as a black swan: how a single bird shows navigational abilities during repeat crossings of the Greenland Icecap

Despite the wealth of studies on seasonal movements of birds between southern nonbreeding locations and High Arctic breeding locations, the key mechanisms of navigation during these migrations remain elusive. A flight along the shortest possible route between pairs of points on a sphere (‘orthodrome’) requires a bird to be able to assess its current location in relation to its migration goal and to make continuous adjustment of heading to reach that goal. Alternatively, birds may navigate along a vector with a fixed orientation (‘loxodrome’) based on magnetic and/or celestial compass mechanisms. Compass navigation is considered especially challenging for summer migrations in Polar regions, as continuous daylight and complexity in the geomagnetic field may complicate the use of both celestial and magnetic compasses here. We examine the possible use of orientation mechanisms during migratory flights across the Greenland Icecap. Using a novel 2 g solar-powered satellite transmitter, we documented the flight paths travelled by a female red knot Calidris canutus islandica during two northward and two southward migrations. The geometry of the paths suggests that red knots can migrate across the Greenland Icecap along the shortest-, orthodrome-like, path instead of the previously suggested loxodrome path. This particular bird's ability to return to locations visited in a previous year, together with its sudden course changes (which would be appropriate responses to ambient wind fields), suggest a map sense that enables red knots to determine location, so that they can tailor their route depending on local conditions.     

Identification of retinoblastoma related genes with shortest path in a protein-protein interaction network

This paper presents a new method for identifying retinoblastoma related genes by integrating gene expression profile and shortest path in a functional linkage graph. With the existing protein-protein interaction data from STRING, a weighted functional linkage graph is constructed. 119 consistently differentially expressed genes between retinoblastoma and normal retina were obtained from the overlap of two gene expression studies of retinoblastoma. Then the shortest paths between each pair of these 119 genes were determined with Dijkstra's algorithm. Finally, all the genes present on the shortest paths were extracted and ranked according to their betweenness and the 119 shortest genes with a betweenness greater than 100 and with a p-value less than 0.05 were selected for further analysis. We also identified 53 retinoblastoma related miRNAs from published miRNA array data and most of the 238 (119 consistently differentially expressed genes and 119 shortest path genes) retinoblastoma genes were shown to be target genes of these 53 miRNAs. Interestingly, the genes we identified from both the gene expression profiles and the functional protein association network included more cancer genes than did the genes identified from the gene expression profiles alone. In addition, these genes also had greater functional similarity to the reported cancer genes than did the genes identified from the gene expression profiles alone. This study shows promising results and proves the efficiency of the proposed methods.     

Das Landschaftsgedächtnis der Bienen. Kleine Gehirne – überraschendes Orientierungsvermögen

We have used a new device, the harmonic radar, to monitor continously the flight paths of bees. Bees are well oriented within the area they have explored during their orientation flights. Bees transported and released at an unexpected site within this area are not lost but fly back to the hive on direct routes after a short search phase. Bees that have been trained to a feeding place may fly first to the feeding place and then back to the hive indicating that they are able to decide between two destinations for their fast return flights. Since bees could not use a beacon at the indicated goals or the structure of the horizon we conclude that their navigation memory is organized according to a geometric map.     

Gene Ontology-based semantic alignment of biological pathways by evolutionary search

A large number of biological pathways have been elucidated recently, and there is a need for methods to analyze these pathways. One class of methods compares pathways semantically in order to discover parts that are evolutionarily conserved between species or to discover intraspecies similarities. Such methods usually require that the topologies of the pathways being compared are known, i.e. that a query pathway is being aligned to a model pathway. However, sometimes the query only consists of an unordered set of gene products. Previous methods for mapping sets of gene products onto known pathways have not been based on semantic comparison of gene products using ontologies or other abstraction hierarchies. Therefore, we here propose an approach that uses a similarity function defined in Gene Ontology (GO) terms to find semantic alignments when comparing paths in biological pathways where the nodes are gene products. A known pathway graph is used as a model, and an evolutionary algorithm (EA) is used to evolve putative paths from a set of experimentally determined gene products. The method uses a measure of GO term similarity to calculate a match score between gene products, and the fitness value of each candidate path alignment is derived from these match scores. A statistical test is used to assess the significance of evolved alignments. The performance of the method has been tested using regulatory pathways for S. cerevisiae and M. musculus.     

Path-finding in real and simulated rats: assessing the influence of path characteristics on navigation learning

A large body of experimental evidence suggests that the hippocampal place field system is involved in reward based navigation learning in rodents. Reinforcement learning (RL) mechanisms have been used to model this, associating the state space in an RL-algorithm to the place-field map in a rat. The convergence properties of RL-algorithms are affected by the exploration patterns of the learner. Therefore, we first analyzed the path characteristics of freely exploring rats in a test arena. We found that straight path segments with mean length 23 cm up to a maximal length of 80 cm take up a significant proportion of the total paths. Thus, rat paths are biased as compared to random exploration. Next we designed a RL system that reproduces these specific path characteristics. Our model arena is covered by overlapping, probabilistically firing place fields (PF) of realistic size and coverage. Because convergence of RL-algorithms is also influenced by the state space characteristics, different PF-sizes and densities, leading to a different degree of overlap, were also investigated. The model rat learns finding a reward opposite to its starting point. We observed that the combination of biased straight exploration, overlapping coverage and probabilistic firing will strongly impair the convergence of learning. When the degree of randomness in the exploration is increased, convergence improves, but the distribution of straight path segments becomes unrealistic and paths become 'wiggly'. To mend this situation without affecting the path characteristic two additional mechanisms are implemented: a gradual drop of the learned weights (weight decay) and path length limitation, which prevents learning if the reward is not found after some expected time. Both mechanisms limit the memory of the system and thereby counteract effects of getting trapped on a wrong path. When using these strategies individually divergent cases get substantially reduced and for some parameter settings no divergence was found anymore at all. Using weight decay and path length limitation at the same time, convergence is not much improved but instead time to convergence increases as the memory limiting effect is getting too strong. The degree of improvement relies also on the size and degree of overlap (coverage density) in the place field system. The used combination of these two parameters leads to a trade-off between convergence and speed to convergence. Thus, this study suggests that the role of the PF-system in navigation learning cannot be considered independently from the animals' exploration pattern.     

Revealing hidden interval graph structure in STS-content data.

MOTIVATION: STS-content data for genomic mapping contain numerous errors and anomalies resulting in cross-links among distant regions of the genome. Identification of contigs within the data is an important and difficult problem. RESULTS: This paper introduces a graph algorithm which creates a simplified view of STS-content data. The shape of the resulting structure graph provides a quality check - coherent data produce a straight line, while anomalous data produce branches and loops. In the latter case, it is sometimes possible to disentangle the various paths into subsets of the data covering contiguous regions of the genome, i.e. contigs. These straight subgraphs can then be analyzed in standard ways to construct a physical map. A theoretical basis for the method is presented along with examples of its application to current STS data from human genome centers. AVAILABILITY: Freely available on request.     

Self-organized cooperation between robotic swarms

We study self-organized cooperation between heterogeneous robotic swarms. The robots of each swarm play distinct roles based on their different characteristics. We investigate how the use of simple local interactions between the robots of the different swarms can let the swarms cooperate in order to solve complex tasks. We focus on an indoor navigation task, in which we use a swarm of wheeled robots, called foot-bots, and a swarm of flying robots that can attach to the ceiling, called eye-bots. The task of the foot-bots is to move back and forth between a source and a target location. The role of the eye-bots is to guide foot-bots: they choose positions at the ceiling and from there give local directional instructions to foot-bots passing by. To obtain efficient paths for foot-bot navigation, eye-bots need on the one hand to choose good positions and on the other hand learn the right instructions to give. We investigate each of these aspects. Our solution is based on a process of mutual adaptation, in which foot-bots execute instructions given by eye-bots, and eye-bots observe the behavior of foot-bots to adapt their position and the instructions they give. Our approach is inspired by pheromone mediated navigation of ants, as eye-bots serve as stigmergic markers for foot-bot navigation. Through simulation, we show how this system is able to find efficient paths in complex environments, and to display different kinds of complex and scalable self-organized behaviors, such as shortest path finding and automatic traffic spreading.     

Path Similarity Analysis: A Method for Quantifying Macromolecular Pathways

Diverse classes of proteins function through large-scale conformational changes and various sophisticated computational algorithms have been proposed to enhance sampling of these macromolecular transition paths. Because such paths are curves in a high-dimensional space, it has been difficult to quantitatively compare multiple paths, a necessary prerequisite to, for instance, assess the quality of different algorithms. We introduce a method named Path Similarity Analysis (PSA) that enables us to quantify the similarity between two arbitrary paths and extract the atomic-scale determinants responsible for their differences. PSA utilizes the full information available in 3N-dimensional configuration space trajectories by employing the Hausdorff or Fréchet metrics (adopted from computational geometry) to quantify the degree of similarity between piecewise-linear curves. It thus completely avoids relying on projections into low dimensional spaces, as used in traditional approaches. To elucidate the principles of PSA, we quantified the effect of path roughness induced by thermal fluctuations using a toy model system. Using, as an example, the closed-to-open transitions of the enzyme adenylate kinase (AdK) in its substrate-free form, we compared a range of protein transition path-generating algorithms. Molecular dynamics-based dynamic importance sampling (DIMS) MD and targeted MD (TMD) and the purely geometric FRODA (Framework Rigidity Optimized Dynamics Algorithm) were tested along with seven other methods publicly available on servers, including several based on the popular elastic network model (ENM). PSA with clustering revealed that paths produced by a given method are more similar to each other than to those from another method and, for instance, that the ENM-based methods produced relatively similar paths. PSA applied to ensembles of DIMS MD and FRODA trajectories of the conformational transition of diphtheria toxin, a particularly challenging example, showed that the geometry-based FRODA occasionally sampled the pathway space of force field-based DIMS MD. For the AdK transition, the new concept of a Hausdorff-pair map enabled us to extract the molecular structural determinants responsible for differences in pathways, namely a set of conserved salt bridges whose charge-charge interactions are fully modelled in DIMS MD but not in FRODA. PSA has the potential to enhance our understanding of transition path sampling methods, validate them, and to provide a new approach to analyzing conformational transitions.     

Ants find the shortest path: a mathematical proof

In the most basic application of Ant Colony Optimization (ACO), a set of artificial ants find the shortest path between a source and a destination. Ants deposit pheromone on paths they take, preferring paths that have more pheromone on them. Since shorter paths are traversed faster, more pheromone accumulates on them in a given time, attracting more ants and leading to reinforcement of the pheromone trail on shorter paths. This is a positive feedback process that can also cause trails to persist on longer paths, even when a shorter path becomes available. To counteract this persistence on a longer path, ACO algorithms employ remedial measures, such as using negative feedback in the form of uniform evaporation on all paths. Obtaining high performance in ACO algorithms typically requires fine tuning several parameters that govern pheromone deposition and removal. This paper proposes a new ACO algorithm, called EigenAnt, for finding the shortest path between a source and a destination, based on selective pheromone removal that occurs only on the path that is actually chosen for each trip. We prove that the shortest path is the only stable equilibrium for EigenAnt, which means that it is maintained for arbitrary initial pheromone concentrations on paths, and even when path lengths change with time. The EigenAnt algorithm uses only two parameters and does not require them to be finely tuned. Simulations that illustrate these properties are provided.     

Evolvable neuronal paths: a novel basis for information and search in the brain

We propose a previously unrecognized kind of informational entity in the brain that is capable of acting as the basis for unlimited hereditary variation in neuronal networks. This unit is a path of activity through a network of neurons, analogous to a path taken through a hidden Markov model. To prove in principle the capabilities of this new kind of informational substrate, we show how a population of paths can be used as the hereditary material for a neuronally implemented genetic algorithm, (the swiss-army knife of black-box optimization techniques) which we have proposed elsewhere could operate at somatic timescales in the brain. We compare this to the same genetic algorithm that uses a standard 'genetic' informational substrate, i.e. non-overlapping discrete genotypes, on a range of optimization problems. A path evolution algorithm (PEA) is defined as any algorithm that implements natural selection of paths in a network substrate. A PEA is a previously unrecognized type of natural selection that is well suited for implementation by biological neuronal networks with structural plasticity. The important similarities and differences between a standard genetic algorithm and a PEA are considered. Whilst most experiments are conducted on an abstract network model, at the conclusion of the paper a slightly more realistic neuronal implementation of a PEA is outlined based on Izhikevich spiking neurons. Finally, experimental predictions are made for the identification of such informational paths in the brain.     

Along signal paths: an empirical gene set approach exploiting pathway topology

Gene set analysis using biological pathways has become a widely used statistical approach for gene expression analysis. A biological pathway can be represented through a graph where genes and their interactions are, respectively, nodes and edges of the graph. From a biological point of view only some portions of a pathway are expected to be altered; however, few methods using pathway topology have been proposed and none of them tries to identify the signal paths, within a pathway, mostly involved in the biological problem. Here, we present a novel algorithm for pathway analysis clipper, that tries to fill in this gap. clipper implements a two-step empirical approach based on the exploitation of graph decomposition into a junction tree to reconstruct the most relevant signal path. In the first step clipper selects significant pathways according to statistical tests on the means and the concentration matrices of the graphs derived from pathway topologies. Then, it identifies within these pathways the signal paths having the greatest association with a specific phenotype. We test our approach on simulated and two real expression datasets. Our results demonstrate the efficacy of clipper in the identification of signal transduction paths totally coherent with the biological problem.     

Maintaining a cognitive map in darkness: the need to fuse boundary knowledge with path integration

Spatial navigation requires the processing of complex, disparate and often ambiguous sensory data. The neurocomputations underpinning this vital ability remain poorly understood. Controversy remains as to whether multimodal sensory information must be combined into a unified representation, consistent with Tolman's "cognitive map", or whether differential activation of independent navigation modules suffice to explain observed navigation behaviour. Here we demonstrate that key neural correlates of spatial navigation in darkness cannot be explained if the path integration system acted independently of boundary (landmark) information. In vivo recordings demonstrate that the rodent head direction (HD) system becomes unstable within three minutes without vision. In contrast, rodents maintain stable place fields and grid fields for over half an hour without vision. Using a simple HD error model, we show analytically that idiothetic path integration (iPI) alone cannot be used to maintain any stable place representation beyond two to three minutes. We then use a measure of place stability based on information theoretic principles to prove that featureless boundaries alone cannot be used to improve localization above chance level. Having shown that neither iPI nor boundaries alone are sufficient, we then address the question of whether their combination is sufficient and - we conjecture - necessary to maintain place stability for prolonged periods without vision. We addressed this question in simulations and robot experiments using a navigation model comprising of a particle filter and boundary map. The model replicates published experimental results on place field and grid field stability without vision, and makes testable predictions including place field splitting and grid field rescaling if the true arena geometry differs from the acquired boundary map. We discuss our findings in light of current theories of animal navigation and neuronal computation, and elaborate on their implications and significance for the design, analysis and interpretation of experiments.     

Heuristic Reusable Dynamic Programming: Efficient Updates of Local Sequence Alignment

Recomputation of the previously evaluated similarity results between biological sequences becomes inevitable when researchers realize errors in their sequenced data or when the researchers have to compare nearly similar sequences, e.g., in a family of proteins. We present an efficient scheme for updating local sequence alignments with an affine gap model. In principle, using the previous matching result between two amino acid sequences, we perform a forward-backward alignment to generate heuristic searching bands which are bounded by a set of suboptimal paths. Given a correctly updated sequence, we initially predict a new score of the alignment path for each contour to select the best candidates among them. Then, we run the Smith-Waterman algorithm in this confined space. Furthermore, our heuristic alignment for an updated sequence shows that it can be further accelerated by using reusable dynamic programming (rDP), our prior work. In this study, we successfully validate "relative node tolerance bound” (RNTB) in the pruned searching space. Furthermore, we improve the computational performance by quantifying the successful RNTB tolerance probability and switch to rDP on perturbation-resilient columns only. In our searching space derived by a threshold value of 90 percent of the optimal alignment score, we find that 98.3 percent of contours contain correctly updated paths. We also find that our method consumes only 25.36 percent of the runtime cost of sparse dynamic programming (sDP) method, and to only 2.55 percent of that of a normal dynamic programming with the Smith-Waterman algorithm.     

Prediction and simulation of motion in pairs of transmembrane alpha-helices

MOTIVATION: Motion in transmembrane (TM) proteins plays an essential role in a variety of biological phenomena. Thus, developing an automated method for predicting and simulating motion in this class of proteins should result in an increased level of understanding of crucial physiological mechanisms. We have developed an algorithm for predicting and simulating motion in TM proteins of the alpha-helix bundle type. Our method employs probabilistic motion-planning techniques to suggest possible collision-free motion paths. The resulting paths are ranked according to the quality of the van der Waals interactions between the TM helices. Our algorithm considers a wide range of degrees of freedom (dofs) involved in the motion, including external and internal moves. However, in order to handle the vast dimensionality of the problem, we employ some constraints on these dofs in a way that is unlikely to rule out the native motion of the protein. Our algorithm simulates the motion, including all the dofs, and automatically produces a movie that demonstrates it. RESULTS: Overexpression of the RTK ErbB2 was implicated in causing a variety of human cancers. Recently, a molecular mechanism for rotation-coupled activation of the receptor was suggested. We applied our algorithm to investigate the TM domain of this protein, and compared our results with this mechanism. A motion pathway that was similar to the proposed mechanism ranked first, and motions with partial overlap to this pathway followed in rank order. In addition, we conducted a negative-control computational-experiment using Glycophorin A. Our results confirmed the immobility of this TM protein, resulting in degenerate paths comprising native-like conformations.     

Finding the way with a noisy brain

Successful navigation is fundamental to the survival of nearly every animal on earth, and achieved by nervous systems of vastly different sizes and characteristics. Yet surprisingly little is known of the detailed neural circuitry from any species which can accurately represent space for navigation. Path integration is one of the oldest and most ubiquitous navigation strategies in the animal kingdom. Despite a plethora of computational models, from equational to neural network form, there is currently no consensus, even in principle, of how this important phenomenon occurs neurally. Recently, all path integration models were examined according to a novel, unifying classification system. Here we combine this theoretical framework with recent insights from directed walk theory, and develop an intuitive yet mathematically rigorous proof that only one class of neural representation of space can tolerate noise during path integration. This result suggests many existing models of path integration are not biologically plausible due to their intolerance to noise. This surprising result imposes significant computational limitations on the neurobiological spatial representation of all successfully navigating animals, irrespective of species. Indeed, noise-tolerance may be an important functional constraint on the evolution of neuroarchitectural plans in the animal kingdom.