Discrete simulations of genetic regulatory networks have been used to study subsystems of yeast successfully. Existing models underling these simulations are based on specific transition functions, which determine the node states in the network. However, implementations of existing models are not freely available and support only a textual user interface (TUI). Additionally, even if an implementation that supports a graphic user interface (GUI) were available, the computations necessary to analyze the simulations would still have to be done manually. Furthermore, the usage of different transition functions by existing models suggests that an enriched model is needed. We developed a software tool, called GRegNetSim, that allows the end-user (a biologist) to describe genetic regulatory networks graphically. The input is displayed visually via Cytoscape (an open-source platform for the representation and analysis of biological networks). The user can specify various transition functions at different nodes of the network, supporting, for example, threshold and gradient effects, thereby analyzing the network under a variety of modes dictated by these functions. GRegNetSim displays the relationship between the inputs and the mode of behavior of the network in a graphic form that is easy to interpret. Furthermore, it automatically extracts statistical data such as the percentage of simulations that reached a steady state or the percentage of simulations that terminated with a certain state. The discrete simulations performed by GRegNetSim can be used to elucidate and predict the behavior, structure, and properties of genetic regulatory networks in a unified manner. GRegNetSim is implemented as a Cytoscape App. Installation files, examples, and source code, along with a detailed user guide, are freely available at https://sites.google.com/site/gregnetsim/.

We introduce a generalization of interval graphs, which we call Dotted Interval Graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (dotted intervals). Coloring of dotted interval graphs naturally arises in the context of high throughput genotyping. We study the properties of dotted interval graphs, with a focus on coloring. We show that any graph is a DIG, but that DIG d graphs, that is, DIGs in which the arithmetic progressions have a jump of at most d , form a strict hierarchy. We show that coloring DIG d graphs is NP-complete even for d = 2. For any fixed d , we provide a 5/6 d + o ( d ) approximation for the coloring of DIG d graphs. Finally, we show that finding the maximal clique in DIG d graphs is fixed parameter tractable in d .

BACKGROUND: Pathways provide topical descriptions of cellular circuitry. Comparing analogous pathways reveals intricate insights into individual functional differences among species. While previous works in the field performed genomic comparisons and evolutionary studies that were based on specific genes or proteins, whole genomic sequence, or even single pathways, none of them described a genomic system level comparative analysis of metabolic pathways. In order to properly implement such an analysis one should overcome two specific challenges: how to combine the effect of many pathways under a unified framework and how to appropriately analyze co-evolution of pathways. Here we present a computational approach for solving these two challenges. First, we describe a comprehensive, scalable, information theory based computational pipeline that calculates pathway alignment information and then compiles it in a novel manner that allows further analysis. This approach can be used for building phylogenies and for pointing out specific differences that can then be analyzed in depth. Second, we describe a new approach for comparing the evolution of metabolic pathways. This approach can be used for detecting co-evolutionary relationships between metabolic pathways. RESULTS: We demonstrate the advantages of our approach by applying our pipeline to data from the MetaCyc repository (which includes a total of 205 organisms and 660 metabolic pathways). Our analysis revealed several surprising biological observations. For example, we show that the different habitats in which Archaea organisms reside are reflected by a pathway based phylogeny. In addition, we discover two striking clusters of metabolic pathways, each cluster includes pathways that have very similar evolution. CONCLUSION: We demonstrate that distance measures that are based on the topology and the content of metabolic networks are useful for studying evolution and co-evolution.

The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.

MOTIVATION: Several recent studies attempted to establish measures for the similarity between genes that are based on the topological properties of metabolic networks. However, these approaches offer only a static description of the properties of interest and offer moderate (albeit significant) correlations with pertinent experimental data. RESULTS: Using a constraint-based large-scale metabolic model, we present two effectively computable measures of functional gene similarity, one based on the response of the metabolic network to gene knockouts and the other based on the metabolic flux activity across a variety of growth media. We applied these measures to 750 genes comprising the metabolic network of the budding yeast. Comparing the in silico computed functional similarities to Gene Ontology (GO) annotations and gene expression data, we show that our computational method captures functional similarities between metabolic genes that go beyond those obtained by the topological analysis of metabolic networks alone, thus revealing dynamic characteristics of gene function. Interestingly, the measure based on the network response to different growth environments markedly outperforms the measure based on its response to gene knockouts, though both have some added synergistic value in depicting the functional relationships between metabolic genes. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We present MAGIC, an integrative and accurate method for comparative genome mapping. Our method consists of two phases: preprocessing for identifying "maximal similar segments," and mapping for clustering and classifying these segments. MAGIC's main novelty lies in its biologically intuitive clustering approach, which aims towards both calculating reorder-free segments and identifying orthologous segments. In the process, MAGIC efficiently handles ambiguities resulting from duplications that occurred before the speciation of the considered organisms from their most recent common ancestor. We demonstrate both MAGIC's robustness and scalability: the former is asserted with respect to its initial input and with respect to its parameters' values. The latter is asserted by applying MAGIC to distantly related organisms and to large genomes. We compare MAGIC to other comparative mapping methods and provide detailed analysis of the differences between them. Our improvements allow a comprehensive study of the diversity of genetic repertoires resulting from large-scale mutations, such as indels and duplications, including explicitly transposable and phagic elements. The strength of our method is demonstrated by detailed statistics computed for each type of these large-scale mutations. MAGIC enabled us to conduct a comprehensive analysis of the different forces shaping prokaryotic genomes from different clades, and to quantify the importance of novel gene content introduced by horizontal gene transfer relative to gene duplication in bacterial genome evolution. We use these results to investigate the breakpoint distribution in several prokaryotic genomes.

We present HyperFlow, a novel visual language for information analysis that combines features from visual dataflow and visual query languages into a unified framework. HyperFlow is designed to make it easier for users to retrieve, filter, and manipulate information, using databases alongside e.g. Web services, in a transparent, intuitive, reproducible and traceable manner. It allows users to visually design and execute information analysis processes in a single diagram. We present HyperFlow's constructs and describe the characteristics of a prototype interface we have implemented.

MOTIVATION: Several genome-scale efforts are underway to reconstruct metabolic networks for a variety of organisms. As the resulting data accumulates, the need for analysis tools increases. A notable requirement is a pathway alignment finder that enables both the detection of conserved metabolic pathways among different species as well as divergent metabolic pathways within a species. When comparing two pathways, the tool should be powerful enough to take into account both the pathway topology as well as the nodes' labels (e.g. the enzymes they denote), and allow flexibility by matching similar--rather than identical--pathways. RESULTS: MetaPathwayHunter is a pathway alignment tool that, given a query pathway and a collection of pathways, finds and reports all approximate occurrences of the query in the collection, ranked by similarity and statistical significance. It is based on a novel, efficient graph matching algorithm that extends the functionality of known techniques. The program also supports a visualization interface with which the alignment of two homologous pathways can be graphically displayed. We employed this tool to study the similarities and differences in the metabolic networks of the bacterium Escherichia coli and the yeast Saccharomyces cerevisiae, as represented in highly curated databases. We reaffirmed that most known metabolic pathways common to both the species are conserved. Furthermore, we discovered a few intriguing relationships between pathways that provide insight into the evolution of metabolic pathways. We conclude with a description of biologically meaningful meta-queries, demonstrating the power and flexibility of our new tool in the analysis of metabolic pathways.

Programs in languages such as Fortran, Pascal, and C were designed and written for a sequential machine model. During the last decade, several methods to vectorize such programs and recover other forms of parallelism that apply to more advanced machine architectures have been developed (particularly for Fortran, due to its pointer-free semantics). We propose and demonstrate a more powerful translation technique for making such programs run efficiently on parallel machines which support facilities such as parallel prefix operations as well as parallel and vector capabilities. This technique, which is global in nature and involves a modification of the traditional definition of the program dependence graph (PDG), is based on the extraction of parallelizable program structures (“idioms”) from the given (sequential) program. The benefits of our technique extend beyond the above-mentioned architectures and can be viewed as a general program optimization method, applicable in many other situations. We show a few examples in which our method indeed outperforms existing analysis techniques.

Programs in languages such as FORTRAN, Pascal, and which our method indeed outperforms existing analysis techniques.

Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and shorter) compiled code. Our approach has been compared to both standard and priority-based coloring algorithms, universally outperforming them.

An algorithmic framework is presented for mapping CMOS circuit diagrams into area-efficient, high-performance layouts in the style of one-dimensional transistor arrays. Using efficient search techniques and accurate evaluation methods, the huge solution space that is typical to such problems is transversed extremely fast, yielding designs of hand-layout quality. In addition to generating circuits that meet prespecified layout constraints in the context of a fixed target image, on-the-fly optimizations are performed to meet secondary optimization criteria. A practical dynamic programming routing algorithm is utilized to accommodate the special conditions that arise in this context. This algorithm has been implemented and is currently used at IBM for cell-library generation.>

Chaining is the ability to pipeline two or more vector instructions on Cray-1 like machines. The authors show how to optimally use this feature to compute (vector) expression trees in the context of automatic code generation. They present a linear time scheduling algorithm for finding an optimal order of evaluation for a machine with a bounded number of registers.>

We describe an algorithm that maps a CMOS circuit diagram into an area-efficient, high-performance layout in the style of a transistor chain. It is superior to other published algorithms of this kind in terms of the class of input circuits it accepts, its efficiency, and the quality of the results it produces. This algorithm is intended for the automatic generation of basic cells in a custom or semicustom design environment, thereby removing the burden of arduous mask definition from the designer. We show how our method was used to compose cells in a row into a functional slice (e.g. an adder) that can be used in, say, a data path.

We propose a new machine model in which load operations can be performed in parallel with arithmetic operations by two separate functional units. For this model, the evaluation of expression trees is considered. An efficient algorithm to produce an optimal order of evaluation is described and analyzed. For a tree with n vertices the algorithm runs in time Ο(n log2n). If the arithmetic operations have at most two arguments, the complexity goes down to Ο(n logn).

As the final stage in laying out a chip, the logic of the integrated circuit is assembled into one (not necessarily rectangular) module which must then be connected to pads lying along a rectangular frame. A placement for the module must be determined to assure the feasibility of the (river) routing from the logic inside to the pads on the periphery. We first show how to solve the routing problem in a stationary context: given the placement, can the signals be wired in the given doughnut-shaped area? Then we use the routability analysis developed in the first part to find a placement of the circuit that yields a feasible routing (if one exists). Both algorithms run in time that is quadratic in the size of the input, and there exist cases for which this bound cannot be improved upon.

Programs for integrated circuit layout typically have two phases; placement and routing. The router tries to produce as efficient a layout as possible, but of course the quality of the routing depends heavily on the quality of the placement. On the other hand, the placement procedure ideally should know the impact of its placement decisions on the quality of a routing. In this paper, we present a placement-and-routing problem for which there is perfect interaction between the two phases. The algorithms for this commonly arising problem are fast, simple and optimal. River routing is the problem of connecting in order a set of terminals $a_1 , \cdots ,a_n $ on a line to another set $b_1 , \cdots ,b_n $ across a rectangular channel. The terminals are located on modules which must be placed relative to one another before routing. This placement-and-routing problem arises frequently in design systems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which may be placed separately. In this paper we give concise necessary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single-source-longest-paths problem. For rectilinear wiring, the special structure of graphs that arise allows an optimal solution to be determined quickly.

Many problems that arise in general channel routing manifest themselves in simpler situations. We consider connecting a set of n terminals on a line to another set on a parallel line across a rectangular channel. We show that in any solution to the problem that (almost) minimizes the width of the channel (i.e. the distance between the lines the terminals reside on) a net may require as many as ?(?n) horizontal jogs no net routed from top to bottom need ever turn upward in the middle We also present an efficient algorithm to obtain minimal jogging in river routing, and provide necessary and sufficient conditions for conflict cycle resolution. These and other results are presented in the context of a general survey on routing from a combinatorial complexity point of view.