MOTIVATION: We introduce Pycellerator, a Python library for reading Cellerator arrow notation from standard text files, conversion to differential equations, generating stand-alone Python solvers, and optionally running and plotting the solutions. All of the original Cellerator arrows, which represent reactions ranging from mass action, Michales-Menten-Henri (MMH) and Gene-Regulation (GRN) to Monod-Wyman-Changeaux (MWC), user defined reactions and enzymatic expansions (KMech), were previously represented with the Mathematica extended character set. These are now typed as reaction-like commands in ASCII text files that are read by Pycellerator, which includes a Python command line interface (CLI), a Python application programming interface (API) and an iPython notebook interface. RESULTS: Cellerator reaction arrows are now input in text files. The arrows are parsed by Pycellerator and translated into differential equations in Python, and Python code is automatically generated to solve the system. Time courses are produced by executing the auto-generated Python code. Users have full freedom to modify the solver and utilize the complete set of standard Python tools. The new libraries are completely independent of the old Cellerator software and do not require Mathematica. AVAILABILITY AND IMPLEMENTATION: All software is available (GPL) from the github repository at https://github.com/biomathman/pycellerator/releases. Details, including installation instructions and a glossary of acronyms and terms, are given in the Supplementary information.

An overview is presented of the construction and use of algebraic partition functions to represent the equilibrium statistical mechanics of multimolecular complexes and their action within a larger regulatory network. Unlike many applications of equilibrium statistical mechanics, multimolecular complexes may operate with various subsets of their components present and connected to the others, the rest remaining in solution. Thus they are variable-structure systems. This aspect of their behavior may be accounted for by the use of 'fugacity' variables as a representation within the partition functions. Four principles are proposed by which the combinatorics of molecular complex construction can be reflected in the construction of their partition functions. The corresponding algebraic operations on partition functions are multiplication, addition, function composition and a less commonly used operation called contraction. Each has a natural interpretation in terms of probability distributions on multimolecular structures. Possible generalizations to nonequilibrium statistical mechanics are briefly discussed.

A current challenge is to develop computational approaches to infer gene network regulatory relationships based on multiple types of large-scale functional genomic data. We find that single-layer feed-forward artificial neural network (ANN) models can effectively discover gene network structure by integrating global in vivo protein:DNA interaction data (ChIP/Array) with genome-wide microarray RNA data. We test this on the yeast cell cycle transcription network, which is composed of several hundred genes with phase-specific RNA outputs. These ANNs were robust to noise in data and to a variety of perturbations. They reliably identified and ranked 10 of 12 known major cell cycle factors at the top of a set of 204, based on a sum-of-squared weights metric. Comparative analysis of motif occurrences among multiple yeast species independently confirmed relationships inferred from ANN weights analysis. ANN models can capitalize on properties of biological gene networks that other kinds of models do not. ANNs naturally take advantage of patterns of absence, as well as presence, of factor binding associated with specific expression output; they are easily subjected to in silico "mutation" to uncover biological redundancies; and they can use the full range of factor binding values. A prominent feature of cell cycle ANNs suggested an analogous property might exist in the biological network. This postulated that "network-local discrimination" occurs when regulatory connections (here between MBF and target genes) are explicitly disfavored in one network module (G2), relative to others and to the class of genes outside the mitotic network. If correct, this predicts that MBF motifs will be significantly depleted from the discriminated class and that the discrimination will persist through evolution. Analysis of distantly related Schizosaccharomyces pombe confirmed this, suggesting that network-local discrimination is real and complements well-known enrichment of MBF sites in G1 class genes.

Abstract Motivation: As a first step toward the elucidation of the systems biology of complex biological systems, it was our goal to mathematically model common enzyme catalytic and regulatory mechanisms that repeatedly appear in biological processes such as signal transduction and metabolic pathways. Results: We describe kMech, a Cellerator language extension that describes a suite of enzyme mechanisms. Each enzyme mechanism is parsed by kMech into a set of fundamental association–dissociation reactions that are translated by Cellerator into ordinary differential equations that are numerically solved by Mathematica™. In addition, we present methods that use commonly available kinetic measurements to estimate rate constants required to solve these differential equations. Availability: A Mathematica™ executable kMech.m file is available at the University of California, Irvine, Institute for Genomics and Bioinformatics website, http://www.igb.uci.edu/servers/sb.html. Cellerator, free of charge to academic, US government, and other non-profit organizations, can be obtained at the Cellerator website, (http://www-aig.jpl.nasa.gov/public/mls/cellerator/feedback.html). Contact: Biology correspondence should be addressed to [email protected]. Computation correspondence should be addressed to [email protected]. Supplementary information: http://www.igb.uci.edu/servers/sb.html.

In this paper we present a family of algorithms that can simultaneously align and cluster sets of multidimensional curves defined on a discrete time grid. Our approach uses the Expectation-Maximization (EM) algorithm to recover both the mean curve shapes for each cluster, and the most likely shifts, offsets, and cluster memberships for each curve. We demonstrate how Bayesian estimation methods can improve the results for small sample sizes by enforcing smoothness in the cluster mean curves. We evaluate the methodology on two real-world data sets, time-course gene expression data and storm trajectory data. Experimental results show that models that incorporate curve alignment systematically provide improvements in predictive power and within-cluster variance on test data sets. The proposed approach provides a non-parametric, computationally efficient, and robust methodology for clustering broad classes of curve data.

We propose a functional mixture model for simultaneous clustering and alignment of sets of curves measured on a discrete time grid. The model is specifically tailored to gene expression time course data. Each func- tional cluster center is a nonlinear combination of solutions of a simple linear differential equation that describes the change of individual mRNA levels when the synthesis and decay rates are constant. The mixture of continuous time parametric functional forms allows one to (a) account for the heterogeneity in the observed profiles, (b) align the profiles in time by estimating real-valued time shifts, (c) capture the synthesis and decay of mRNA in the course of an experiment, and (d) regularize noisy profiles by enforcing smoothness in the mean curves. We derive an EM algo- rithm for estimating the parameters of the model, and apply the proposed approach to the set of cycling genes in yeast. The experiments show consistent improvement in predictive power and within cluster variance compared to regular Gaussian mixtures.

MOTIVATION: Molecular biotechnology now makes it possible to build elaborate systems models, but the systems biology community needs information standards if models are to be shared, evaluated and developed cooperatively. RESULTS: We summarize the Systems Biology Markup Language (SBML) Level 1, a free, open, XML-based format for representing biochemical reaction networks. SBML is a software-independent language for describing models common to research in many areas of computational biology, including cell signaling pathways, metabolic pathways, gene regulation, and others. AVAILABILITY: The specification of SBML Level 1 is freely available from http://www.sbml.org/

Abstract Summary: Cellerator describes single and multi-cellular signal transduction networks (STN) with a compact, optionally palette-driven, arrow-based notation to represent biochemical reactions and transcriptional activation. Multi-compartment systems are represented as graphs with STNs embedded in each node. Interactions include mass-action, enzymatic, allosteric and connectionist models. Reactions are translated into differential equations and can be solved numerically to generate predictive time courses or output as systems of equations that can be read by other programs. Cellerator simulations are fully extensible and portable to any operating system that supports Mathematica, and can be indefinitely nested within larger data structures to produce highly scaleable models. Availability: Cellerator can be licensed free of charge to noncommercial academic, U.S. government, and nonprofit users. Details and sample notebooks are available at http://www-aig.jpl.nasa.gov/public/mls/cellerator. Contact: [email protected] * To whom correspondence should be addressed.

Deformable models are central to non-rigid motion analysis, shape matching and non-rigid medical image registration. Spline-based deformations are a very popular class of parameterizations of deformable models and have been heavily used in multiple domains. In a somewhat separate sub-field, weighted graphs are a frequently used object parameterization. Graph matching using weighted graph object parameterizations finds application in a spectrum ranging from rigid pose estimation to deformable object recognition. Here, we demonstrate a hitherto unsuspected relationship between spline-based deformable models and weighted graphs. It turns out that spline parameterizations in the kernel representation can be used to construct equivalent weighted graphs. With this connection established, we envision a cross-fertilization between these two seemingly disparate sub-fields of computer vision.

Determining the rigid transformation relating 2D images to known 3D geometry is a classical problem in photogrammetry and computer vision. Heretofore, the best methods for solving the problem have relied on iterative optimization methods which cannot be proven to converge and/or which do not effectively account for the orthonormal structure of rotation matrices. We show that the pose estimation problem can be formulated as that of minimizing an error metric based on collinearity in object (as opposed to image) space. Using object space collinearity error, we derive an iterative algorithm which directly computes orthogonal rotation matrices and which is globally convergent. Experimentally, we show that the method is computationally efficient, that it is no less accurate than the best currently employed optimization methods, and that it outperforms all tested methods in robustness to outliers.

The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.

A fundamental open problem in computer vision—determining pose and correspondence between two sets of points in space—is solved with a novel, fast, robust and easily implementable algorithm. The technique works on noisy 2D or 3D point sets that may be of unequal sizes and may differ by non-rigid transformations. Using a combination of optimization techniques such as deterministic annealing and the softassign, which have recently emerged out of the recurrent neural network/statistical physics framework, analog objective functions describing the problems are minimized. Over thirty thousand experiments, on randomly generated points sets with varying amounts of noise and missing and spurious points, and on hand-written character sets demonstrate the robustness of the algorithm.

We present a novel method for the geometric alignment of autoradiographs of the brain. The method is based on finding the spatial mapping and the one-to-one correspondences (or homologies) between point features extracted from the images and rejecting non-homologies as outliers. In this way, we attempt to account for the local, natural and artifactual differences between the autoradiograph slices. We have used the resulting automated algorithm on a set of left prefrontal cortex autoradiograph slices, specifically demonstrated its ability to perform point outlier rejection, validated its robustness property using synthetically generated spatial mappings and provided an anecdotal visual comparison with the well-known iterated closest-point (ICP) algorithm. Visualization of a stack of aligned left prefrontal cortex autoradiograph slices is also provided.

We present a novel optimizing network architecture with applications in vision, learning, pattern recognition, and combinatorial optimization. This architecture is constructed by combining the following techniques: (1) deterministic annealing, (2) self-amplification, (3) algebraic transformations, (4) clocked objectives, and (5) softassign. Deterministic annealing in conjunction with self-amplification avoids poor local minima and ensures that a vertex of the hypercube is reached. Algebraic transformations and clocked objectives help partition the relaxation into distinct phases. The problems considered have doubly stochastic matrix constraints or minor variations thereof. We introduce a new technique, softassign, which is used to satisfy this constraint. Experimental results on different problems are presented and discussed.

Prior knowledge constraints are imposed upon a learning problem in the form of distance measures. Prototypical 2D point sets and graphs are learned by clustering with point-matching and graph-matching distance measures. The point-matching distance measure is approximately invariant under affine transformations—translation, rotation, scale, and shear—and permutations. It operates between noisy images with missing and spurious points. The graph-matching distance measure operates on weighted graphs and is invariant under permutations. Learning is formulated as an optimization problem. Large objectives so formulated (∼ million variables) are efficiently minimized using a combination of optimization techniques—softassign, algebraic transformations, clocked objectives, and deterministic annealing.

A Lagrangian relaxation network for graph matching is presented. The problem is formulated as follows: given graphs G and g, find a permutation matrix M that brings the two sets of vertices into correspondence. Permutation matrix constraints are formulated in the framework of deterministic annealing. Our approach is in the same spirit as a Lagrangian decomposition approach in that the row and column constraints are satisfied separately with a Lagrange multiplier used to equate the two "solutions". Due to the unavoidable symmetries in graph isomorphism (resulting in multiple global minima), we add a symmetry-breaking self-amplification term in order to obtain a permutation matrix. With the application of a fixpoint preserving algebraic transformation to both the distance measure and self-amplification terms, we obtain a Lagrangian relaxation network. The network performs minimization with respect to the Lagrange parameters and maximization with respect to the permutation matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities.

A fundamental open problem in computer vision-determining pose and correspondence between two sets of points in space(cid:173) is solved with a novel, robust and easily implementable algorithm. The technique works on noisy point sets that may be of unequal sizes and may differ by non-rigid transformations. A 2D varia(cid:173) tion calculates the pose between point sets related by an affine transformation-translation, rotation, scale and shear. A 3D to 3D variation calculates translation and rotation. An objective describ(cid:173) ing the problem is derived from Mean field theory. The objective is minimized with clocked (EM-like) dynamics. Experiments with both handwritten and synthetic data provide empirical evidence for the method.

Prior constraints are imposed upon a learning problem in the form of distance measures. Prototypical 2-D point sets and graphs are learned by clustering with point matching and graph matching dis(cid:173) tance measures. The point matching distance measure is approx. invariant under affine transformations - translation, rotation, scale and shear - and permutations. It operates between noisy images with missing and spurious points. The graph matching distance measure operates on weighted graphs and is invariant under per(cid:173) mutations. Learning is formulated as an optimization problem . Large objectives so formulated ('" million variables) are efficiently minimized using a combination of optimization techniques - alge(cid:173) braic transformations, iterative projective scaling, clocked objec(cid:173) tives, and deterministic annealing.

Given a relaxation-based neural network and a desired partition of the neurons in the network into modules with relatively slow communication between modules, we investigate relaxation dynamics for the resulting partitioned neural network. In particular, we show how the slow inter-module communication channels can be modeled by means of certain transformations of the original objective function which introduce new state variables for the inter-module communication links. We report on a parallel implementation of the resulting relaxation dynamics, for a two-dimensional image segmentation network, using a network of workstations. Experiments demonstrate a functional and efficient parallelization of this neural network algorithm. We also discuss implications for analog hardware implementations of relaxation networks.

This paper introduces a combined discrete/continuous model of plant development that integrates L-system-style productions and differential equations.The model is suitable for animating simulated developmental processes in a manner resembling time-lapse photography.The proposed technique is illustrated using several developmental models, including the flowering plants Campanula rapunculoides, Lychnis coronaria , and Hieracium umbellatum.

One way to speed up convergence in a large optimization problem is to introduce a smaller, approximate version of the problem at a coarser scale and to alternate between relaxation steps for the fine-scale and coarse-scale problems. Such an optimization method for neural networks governed by quite general objective functions is presented. At the coarse scale, there is a smaller approximating neural net which, like the original net, is nonlinear and has a nonquadratic objective function. The transitions and information flow from fine to coarse scale and back do not disrupt the optimization, and the user need only specify a partition of the original fine-scale variables. Thus, the method can be applied easily to many problems and networks. There is generally about a fivefold improvement in estimated cost under the multiscale method. In the networks to which it was applied, a nontrivial speedup by a constant factor of between two and five was observed, independent of problem size. Further improvements in computational cost are very likely to be available, especially for problem-specific multiscale neural net methods.

A multiscale optimization method for neural networks governed by quite general objective functions is presented. At the coarse scale, there is a smaller, approximating neural net. Like the original net, it is nonlinear and has a nonquadratic objective function, so the coarse-scale net is a more accurate approximation than a quadratic objective would be. The transitions and information flow form fine to coarse scale and back do not disrupt the optimization. The problem need not involve any geometric domain; all that is required is a partition of the original fine-scale variables. Given this partition, the rest of the multiscale optimization method requires no problem-specific design effort on the part of the user, since the mapping between coarse and fine scales is determined. Thus, the method can be applied easily to many problems and networks. Positive experimental results including cost comparisons are shown

We introduce an optimization approach for solving problems in computer vision that involve multiple levels of abstraction. Our objective functions include compositional and specialization hierarchies. We cast vision problems as inexact graph matching problems, formulate graph matching in terms of constrained optimization, and use analog neural networks to perform the optimization. The method is applicable to perceptual grouping and model matching. Preliminary experimental results are shown.

The minimum (symmetric) rank of a simple graph G over a field F is the smallest possible rank among all symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. The problem of determining minimum (symmetric) rank has been studied extensively. We define the minimum skew rank of a simple graph G to be the smallest possible rank among all skew-symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We apply techniques from the minimum (symmetric) rank problem and from skew-symmetric matrices to obtain results about the minimum skew rank problem.