Search

Network alignment aims to uncover topologically similar regions in the protein–protein interaction (PPI) networks of two or more species under the assumption that topologically similar regions tend to perform similar functions. Although there exist a plethora of both network alignment algorithms and measures of topological similarity, currently no "gold standard" exists for evaluating how well either is able to uncover functionally similar regions. Here we propose a formal, mathematically and statistically rigorous method for evaluating the statistical significance of shared GO terms in a global, 1-to-1 alignment between two PPI networks. Given an alignment in which k aligned protein pairs share a particular GO term g, we use a combinatorial argument to precisely quantify the p-value of that alignment with respect to g compared to a random alignment. The p-value of the alignment with respect to all GO terms, including their inter-relationships, is approximated using the Empirical Brown's Method. We note that, just as with BLAST's p-values, this method is not designed to guide an alignment algorithm towards a solution; instead, just as with BLAST, an alignment is guided by a scoring matrix or function; the p-values herein are computed after the fact, providing independent feedback to the user on the biological quality of the alignment that was generated by optimizing the scoring function. Importantly, we demonstrate that among all GO-based measures of network alignments, ours is the only one that correlates with the precision of GO annotation predictions, paving the way for network alignment-based protein function prediction. [ABSTRACT FROM AUTHOR]

Motivation Protein–protein interaction (PPI) networks provide valuable insights into the function of biological systems. Aligning multiple PPI networks may expose relationships beyond those observable by pairwise comparisons. However, assessing the biological quality of multiple network alignments is a challenging problem. Results We propose two new measures to evaluate the quality of multiple network alignments using functional information from Gene Ontology (GO) terms. When aligning multiple real PPI networks across species, we observe that both measures are highly correlated with objective quality indicators, such as common orthologs. Additionally, our measures strongly correlate with an alignment's ability to predict novel GO annotations, which is a unique advantage over existing GO-based measures. Availability and implementation The scripts and the links to the raw and alignment data can be accessed at https://github.com/kimiayazdani/GO_Measures.git [ABSTRACT FROM AUTHOR]

Motivation: Gene Ontology (GO) terms are frequently used to score alignments between protein--protein interaction (PPI) networks. Methods exist to measure GO similarity between proteins in isolation, but proteins in a network alignment are not isolated: each pairing is dependent on every other via the alignment itself. Existing measures fail to take into account the frequency of GO terms across networks, instead imposing arbitrary rules on when to allow GO terms. Results: Here we develop NetGO, a new measure that naturally weighs infrequent, informative GO terms more heavily than frequent, less informative GO terms, without arbitrary cutoffs, instead downweighting GO terms according to their frequency in the networks being aligned. This is a global measure applicable only to alignments, independent of pairwise GO measures, in the same sense that the edge-based EC or S3 scores are global measures of topological similarity independent of pairwise topological similarities. We demonstrate the superiority of NetGO in alignments of predetermined quality and show that NetGO correlates with alignment quality better than any existing GO-based alignment measures. We also demonstrate that NetGO provides a measure of taxonomic similarity between species, consistent with existing taxonomic measuresa feature not shared with existing GObased network alignment measures. Finally, we re-score alignments produced by almost a dozen aligners from a previous study and show that NetGO does a better job at separating good alignments from bad ones. [ABSTRACT FROM AUTHOR]

Summary: Every alignment algorithm consists of two orthogonal components: an objective function M measuring the quality of an alignment, and a search algorithm that explores the space of alignments looking for ones scoring well according to M. We introduce a new search algorithm called SANA (Simulated Annealing Network Aligner) and apply it to protein-protein interaction networks using S³ as the topological measure. Compared against 12 recent algorithms, SANA produces 5-10 times as many correct node pairings as the others when the correct answer is known. We expose an anti-correlation in many existing aligners between their ability to produce good topological vs. functional similarity scores, whereas SANA usually outscores other methods in both measures. If given the perfect objective function encoding the identity mapping, SANA quickly converges to the perfect solution while many other algorithms falter. We observe that when aligning networks with a known mapping and optimizing only S³, SANA creates alignments that are not perfect and yet whose S³ scores match that of the perfect alignment. We call this phenomenon saturation of the topological score. Saturation implies that a measure's correlation with alignment correctness falters before the perfect alignment is reached. This, combined with SANA's ability to produce the perfect alignment if given the perfect objective function, suggests that better objective functions may lead to dramatically better alignments. We conclude that future work should focus on finding better objective functions, and offer SANA as the search algorithm of choice. [ABSTRACT FROM AUTHOR]

Recently, a study (H&T in this work) compared the pitch angle measurements of several methods on toy spiral galaxies. They claimed that their method outperformed the other methods. In particular, they claimed that our method, SpArcFiRe , either failed completely or produced erroneous results on many of their toy galaxies. In this paper, we assess the validity of that claim with respect to: (1) their toy models as realistic approximations of galaxies, and (2) the handling of SpArcFiRe 's parameters to correctly trace the arms of the toy galaxies. We demonstrate that the structure displayed in their toy galaxies deviates significantly from those of real galaxies. Given that SpArcFiRe was designed for and tested against hundreds of thousands of images of real galaxies, SpArcFiRe could not have been expected to work well with default parameters on H&T's unrealistic toy galaxies. We then review the parameters that affected SpArcFiRe 's ability to measure pitch angles in the toy galaxies, and show that with minor parameter adjustments, SpArcFiRe easily measures the pitch angles of the toy galaxies with mean error less than 1° and maximum error less than 4°, completely eliminating the failures and outliers discussed by H&T. [ABSTRACT FROM AUTHOR]

We present a novel, online algorithm for exact summation of a stream of floating-point numbers. By "online" we mean that the algorithm needs to see only one input at a time, and can take an arbitrary length input stream of such inputs while requiring only constant memory. By "exact" we mean that the sum of the internal array of our algorithm is exactly equal to the sum of all the inputs, and the returned result is the correctly-rounded sum. The proof of correctness is valid for all inputs (including nonnormalized numbers but modulo intermediate overflow), and is independent of the number of summands or the condition number of the sum. The algorithm asymptotically needs only 5 FLOPs per summand, and due to instruction-level parallelism runs only about 2-3 times slower than the obvious, fast-but-dumb "ordinary recursive summation" loop when the number of summands is greater than 10,000. Thus, to our knowledge, it is the fastest, most accurate, and most memory efficient among known algorithms. Indeed, it is difficult to see how a faster algorithm or one requiring significantly fewer FLOPs could exist without hardware improvements. An application for a large number of summands is provided. [ABSTRACT FROM AUTHOR]

We report on some simple experiments on the nature of chaos in our planetary system. We make the following interesting observations. First, we look at the system of Sun + four Jovian planets as an isolated five-body system interacting only via Newtonian gravity. We find that if we measure the Lyapunov time of this system across thousands of initial conditions all within observational uncertainty, then the value of the Lyapunov time seems relatively smooth across some regions of initial condition space, while in other regions it fluctuates wildly on scales as small as we can reliably measure using numerical methods. This probably indicates a fractal structure of Lyapunov exponents measured across initial condition space. Then, we add the four inner terrestrial planets and several post-Newtonian corrections such as general relativity into the model. In this more realistic Sun + eight-planet system, we find that the above structure of chaos for the outer planets becomes uniformly chaotic for almost all planets and almost all initial conditions, with a Lyapunov time-scale of about 5–20 Myr. This seems to indicate that the addition of the inner planets adds more chaos to the system. Finally, we show that if we instead remove the outer planets and look at the isolated five-body system of the Sun + four terrestrial planets, then the terrestrial planets alone show no evidence of chaos at all, over a large range of initial conditions inside the observational error volume. We thus conclude that the uniformity of chaos in the outer planets comes not from the inner planets themselves, but from the interplay between the outer and inner ones. Interestingly, however, there exist rare and isolated initial conditions for which one individual outer planetary orbit may appear integrable over a 200-Myr time-scale, while all the other planets simultaneously appear chaotic. [ABSTRACT FROM AUTHOR]

We present two algorithms for computing correctly rounded sums of arrays of floatingpoint numbers. First, iFastSum improves upon our previous FastSum by requiring no additional space beyond the original array, which is destroyed. It runs about 20% faster than FastSum in the general case and two times faster when extremely ill-conditioned data are used. The second algorithm is HybridSum, which combines three summation ideas together: splitting the mantissa, radix sorting, and using iFastSum. The result is that when the number of summands is greater than about 104, for a given n its running time is almost a constant, independent of the condition number. It runs almost as fast as iFastSum in the general case and much faster than iFastSum when ill-conditioned data are used. HybridSum requires only one pass through the input array and uses constant storage, and it is thus suitable for exact summation as an "online" algorithm. Neither algorithm requires extra precision accumulators, and both work in any base. Their accuracy is guaranteed independent of the condition number and the number of summands. [ABSTRACT FROM AUTHOR]

We demonstrate that the system of Sun and Jovian planets, integrated for 200 Myr as an isolated five-body system using many sets of initial conditions all within the uncertainty bounds of their currently known positions, can display both chaos and near-integrability. The conclusion is consistent across four different integrators, including several comparisons against integrations utilizing quadruple precision. We demonstrate that the Wisdom–Holman symplectic map using simple symplectic correctors as implemented inmercury 6.2 gives a reliable characterization of the existence of chaos for a particular initial condition only with time-steps less than about 10 d, corresponding to about 400 steps per orbit. We also integrate the canonical DE405 initial condition out to 5 Gyr, and show that it has a Lyapunov time of 200–400 Myr, opening the remote possibility of accurate prediction of the Jovian planetary positions for 5 Gyr. [ABSTRACT FROM AUTHOR]

Numerical solutions to chaotic dynamical systems are suspect because the exponential divergence of nearby trajectories causes numerical errors to be exponentially magnified with time. To bolster confidence in the reliability of such numerical solutions, we turn to the study of shadowing: a shadow is an exact trajectory of a chaotic dynamical system that stays close to a numerical trajectory for a long time. Finding shadows of numerical trajectories is very computationally intensive, and until recently it has been infeasible to study shadows of higher-dimensional systems. This paper introduces several optimizations to previous algorithms, which collectively achieve an average speedup of almost two orders of magnitude with no measurable loss in effectiveness. We test the algorithm on systems with up to 180 dimensions. Its application to large gravitational N-body integrations has already led to a deeper understanding of the reliability of galaxy and cosmological simulations. The source code (available from the first author) provides to the experienced user a generic interface capable of searching for shadows of any set of ordinary differential equations. [ABSTRACT FROM AUTHOR]

The quest for reliable integration of initial value problems (IVPs) for ordinary differential equations (ODEs) is a long-standing problem in numerical analysis. At one end of the reliability spectrum are fixed stepsize methods implemented using standard floating point, where the onus lies entirely with the user to ensure the stepsize chosen is adequate for the desired accuracy. At the other end of the reliability spectrum are rigorous interval-based methods, that can provide provably correct bounds on the error of a numerical solution. This rigour comes at a price, however: interval methods are generally two to three orders of magnitude more expensive than fixed stepsize floating-point methods. Along the spectrum between these two extremes lie various methods of different expense that estimate and control some measure of the local errors and adjust the stepsize accordingly. In this article, we continue previous investigations into a class of interpolants for use in Runge- Kutta methods that have a defect function whose qualitative behavior is asymptotically independent of the problem being integrated. In particular the point, in a step, where the maximum defect occurs as h ↠0 is known a priori. This property allows the defect to be monitored and controlled in an efficient and robust manner even for modestly large stepsizes. Our interpolants also have a defect with the highest possible order given the constraints imposed by the order of the underlying discrete formula. We demonstrate the approach on three Runge-Kutta methods of orders 5, 6, and 8, and provide Fortran and preliminary Matlab interfaces to these three new integrators. We also consider how sensitive such methods are to roundoff errors. Numerical results for four problems on a range of accuracy requests are presented. [ABSTRACT FROM AUTHOR]

An exact trajectory of a dynamical system lying close to a numerical trajectory is called a shadow. We present a general-purpose method for proving the existence of finite-time shadows of numerical ODE integrations of arbitrary dimension in which some measure of hyperbolicity is present and there are either 0 or 1 expanding modes, or 0 or 1 contracting modes. Much of the rigor is provided automatically by interval arithmetic and validated ODE integration software that is freely available. The method is a generalization of a previously published containment process that was applicable only to two-dimensional maps. We extend it to handle maps of arbitrary dimension with the above restrictions, and finally to ODEs. The method involves building n-cubes around each point of the discrete numerical trajectory through which the shadow is guaranteed to pass at appropriate times. The proof consists of two steps: first, the rigorous computational verification of a simple geometric property, which we call the inductive containment property, and second, a simple geometric argument showing that this property implies the existence of a shadow. The computational step is almost entirely automated and easily adaptable to any ODE problem. The method allows for the rescaling of time, which is a necessary ingredient for successfully shadowing ODEs. Finally, the method is local, in the sense that it builds the shadow inductively, requiring information only from the most recent integration step, rather than more global information typical of several other methods. The method produces shadows of comparable length and distance to all currently published results. Finally, we conjecture that the inductive containment property implies the existence of a shadow without restriction on the number of expanding and contracting modes, although proof currently eludes us. [ABSTRACT FROM AUTHOR]

The existence of chaos among the jovian planets is a contested issue. There exists both apparently unassailable evidence that the outer Solar System is chaotic, and that it is not. The discrepancy is particularly disturbing given that computed chaos is sometimes due to numerical artefacts. Here, we discount the possibility of numerical artefacts and demonstrate that the discrepancy seen between various investigators is real. It is caused by observational uncertainty in the orbital positions of the jovian planets, which is currently a few parts in 10 million. Within that observational uncertainty, there exist clearly chaotic trajectories with complex structure and Lyapunov times—the timescale for the onset of chaos—ranging from 2 million years to 230 million years, as well as trajectories that show no evidence of chaos over 1 Gyr timescales. Determining the true Lyapunov time of the outer Solar System will require a more accurate observational determination of the orbits of the jovian planets. A full understanding of the nature and consequences of the chaos may require further theoretical development. [ABSTRACT FROM AUTHOR]

Topological network alignment aims to align two networks node-wise in order to maximize the observed common connection (edge) topology between them. The topological alignment of two protein–protein interaction (PPI) networks should thus expose protein pairs with similar interaction partners allowing, for example, the prediction of common Gene Ontology (GO) terms. Unfortunately, no network alignment algorithm based on topology alone has been able to achieve this aim, though those that include sequence similarity have seen some success. We argue that this failure of topology alone is due to the sparsity and incompleteness of the PPI network data of almost all species, which provides the network topology with a small signal-to-noise ratio that is effectively swamped when sequence information is added to the mix. Here we show that the weak signal can be detected using multiple stochastic samples of "good" topological network alignments, which allows us to observe regions of the two networks that are robustly aligned across multiple samples. The resulting network alignment frequency (NAF) strongly correlates with GO-based Resnik semantic similarity and enables the first successful cross-species predictions of GO terms based on topology-only network alignments. Our best predictions have an AUPR of about 0.4, which is competitive with state-of-the-art algorithms, even when there is no observable sequence similarity and no known homology relationship. While our results provide only a "proof of concept" on existing network data, we hypothesize that predicting GO terms from topology-only network alignments will become increasingly practical as the volume and quality of PPI network data increase. [ABSTRACT FROM AUTHOR]

Given an approximately centered image of a spiral galaxy, we describe an entirely automated method that finds, centers, and sizes the galaxy (possibly masking nearby stars and other objects if necessary in order to isolate the galaxy itself) and then automatically extracts structural information about the spiral arms. For each arm segment found, we list the pixels in that segment, allowing image analysis on a per-arm-segment basis. We also perform a least-squares fit of a logarithmic spiral arc to the pixels in that segment, giving per-arc parameters, such as the pitch angle, arm segment length, location, etc. The algorithm takes about one minute per galaxies, and can easily be scaled using parallelism. We have run it on all ∼644,000 Sloan objects that are larger than 40 pixels across and classified as “galaxies.” We find a very good correlation between our quantitative description of a spiral structure and the qualitative description provided by Galaxy Zoo humans. Our objective, quantitative measures of structure demonstrate the difficulty in defining exactly what constitutes a spiral “arm,” leading us to prefer the term “arm segment.” We find that pitch angle often varies significantly segment-to-segment in a single spiral galaxy, making it difficult to define the pitch angle for a single galaxy. We demonstrate how our new database of arm segments can be queried to find galaxies satisfying specific quantitative visual criteria. For example, even though our code does not explicitly find rings, a good surrogate is to look for galaxies having one long, low-pitch-angle arm—which is how our code views ring galaxies. SpArcFiRe is available at http://sparcfire.ics.uci.edu. [ABSTRACT FROM AUTHOR]

In this paper, we study the morphological properties of spiral galaxies, including measurements of spiral arm number and pitch angle. Using Galaxy Zoo 2, a stellar mass-complete sample of 6222 SDSS spiral galaxies is selected. We use the machine vision algorithm SPARCFIRE to identify spiral arm features and measure their associated geometries. A support vector machine classifier is employed to identify reliable spiral features, with which we are able to estimate pitch angles for half of our sample. We use these machine measurements to calibrate visual estimates of arm tightness, and hence estimate pitch angles for our entire sample. The properties of spiral arms are compared with respect to various galaxy properties. The star formation properties of galaxies vary significantly with arm number, but not pitch angle. We find that galaxies hosting strong bars have spiral arms substantially (4°-6°) looser than unbarred galaxies. Accounting for this, spiral arms associated with many-armed structures are looser (by 2°) than those in two-armed galaxies. In contrast to this average trend, galaxies with greater bulge-to-total stellar mass ratios display both fewer and looser spiral arms. This effect is primarily driven by the galaxy disc, such that galaxies with more massive discs contain more spiral arms with tighter pitch angles. This implies that galaxy central mass concentration is not the dominant cause of pitch angle and arm number variations between galaxies, which in turn suggests that not all spiral arms are governed by classical density waves or modal theories. [ABSTRACT FROM AUTHOR]

Summary BLAST creates local sequence alignments by first building a database of small k -letter sub-sequences called k -mers. Identical k -mers from different regions provide 'seeds' for longer local alignments. This seed-and-extend heuristic makes BLAST extremely fast and has led to its almost exclusive use despite the existence of more accurate, but slower, algorithms. In this paper, we introduce the Basic Local Alignment for Networks Tool (BLANT). BLANT is the analog of BLAST, but for networks: given an input graph, it samples small, induced, k -node sub-graphs called k -graphlets. Graphlets have been used to classify networks, quantify structure, align networks both locally and globally, identify topology-function relationships and build taxonomic trees without the use of sequences. Given an input network, BLANT produces millions of graphlet samples in seconds—orders of magnitude faster than existing methods. BLANT offers sampled graphlets in various forms: distributions of graphlets or their orbits; graphlet degree or graphlet orbit degree vectors, the latter being compatible with ORCA; or an index to be used as the basis for seed-and-extend local alignments. We demonstrate BLANT's usefelness by using its indexing mode to find functional similarity between yeast and human PPI networks. Availability and implementation BLANT is written in C and is available at https://github.com/waynebhayes/BLANT/releases. Supplementary information Supplementary data are available at Bioinformatics online. [ABSTRACT FROM AUTHOR]

The Galaxy Zoo project has provided a plethora of valuable morphological data on a large number of galaxies from various surveys, and their team members have identified and/or corrected for many biases. Here we study a new bias related to spiral arm pitch angles, which first requires selecting a sample of spiral galaxies that show observable structure. One obvious way is to select galaxies using a threshold in spirality, which we define as the fraction of Galaxy Zoo humans who have reported seeing spiral structure. Using such a threshold, we use the automated tool SpArcFiRe (SPiral ARC FInder and REporter) to measure spiral arm pitch angles. We observe that the mean pitch angle of spiral arms increases linearly with redshift for 0.05 <  z  < 0.085. We hypothesize that this is a selection effect due to tightly wound arms becoming less visible as image quality degrades, leading to fewer such galaxies being above the spirality threshold as redshift increases. We corroborate this hypothesis by first artificially degrading images of nearby galaxies, and then using a machine learning algorithm trained on Galaxy Zoo data to provide a spirality for each artificially degraded image. We find that SpARcFiRe’s ability to accurately measure pitch angles decreases as the image degrades, but that spirality decreases more quickly in galaxies with tightly wound arms, leading to the selection effect. This new bias means one must be careful in selecting a sample on which to measure spiral structure. Finally, we also include a sensitivity analysis of SpArcFiRe’s internal parameters. [ABSTRACT FROM AUTHOR]

Borders are important as they demarcate developing tissue into distinct functional units. A key challenge is the discovery of mechanisms that can convert morphogen gradients into tissue borders. While mechanisms that produce ultrasensitive cellular responses provide a solution, how extracellular morphogens drive such mechanisms remains poorly understood. Here, we show how Bone Morphogenetic Protein (BMP) and Fibroblast Growth Factor (FGF) pathways interact to generate ultrasensitivity and borders in the dorsal telencephalon. BMP and FGF signaling manipulations in explants produced border defects suggestive of cross inhibition within single cells, which was confirmed in dissociated cultures. Using mathematical modeling, we designed experiments that ruled out alternative cross inhibition mechanisms and identified a cross-inhibitory positive feedback (CIPF) mechanism, or “toggle switch”, which acts upstream of transcriptional targets in dorsal telencephalic cells. CIPF explained several cellular phenomena important for border formation such as threshold tuning, ultrasensitivity, and hysteresis. CIPF explicitly links graded morphogen signaling in the telencephalon to switch-like cellular responses and has the ability to form multiple borders and scale pattern to size. These benefits may apply to other developmental systems. [ABSTRACT FROM AUTHOR]

Motivation: Precise tracking of individual cells—especially tracking the family lineage, for example in a developing embryo—has widespread applications in biology and medicine. Due to significant noise in microscope images, existing methods have difficulty precisely tracking cell activities. These difficulties often require human intervention to resolve. Humans are helpful because our brain naturally and automatically builds a simulation "model" of any scene that we observe. Because we understand simple truths about the world—for example cells can move and divide, but they cannot instantaneously move vast distances—this model "in our heads" helps us to severely constrain the possible interpretations of what we see, allowing us to easily distinguish signal from noise, and track the motion of cells even in the presence of extreme levels of noise that would completely confound existing automated methods. Results: Here, we mimic the ability of the human brain by building an explicit computer simulation model of the scene. Our simulated cells are programmed to allow movement and cell division consistent with reality. At each video frame, we stochastically generate millions of nearby "Universes" and evolve them stochastically to the next frame. We then find and fit the best universes to reality by minimizing the residual between the real image frame and a synthetic image of the simulation. The rule-based simulation puts extremely stringent constraints on possible interpretations of the data, allowing our system to perform far better than existing methods even in the presense of extreme levels of image noise. We demonstrate the viability of this method by accurately tracking every cell in a colony that grows from 4 to over 300 individuals, doing about as well as a human can in the difficult task of tracking cell lineages. [ABSTRACT FROM AUTHOR]