Complex Biological Networks

185.A rapid algorithm for generating minimal pathway distances
186.System analysis of complex molecular networks by mathematical simulation and control theory
187.Parameter Estimation of Signal Transduction Pathways using Real-Coded Genetic Algorithms
188.A two-phase partition method simulates the dynamic behavior of the heat shock response with high accuracy at a remarkably high speed.
189.Integration of Computational Techniques for the Modelling of Signal Transduction
190.Validating Metabolic Prediction
192.Scale-free Behaviour in Protein Domain Networks
193.Inferring gene dependency networks using expression profiles from yeast deletion mutants
194.On Network Genomics
195.Semantic Modeling of Signal Transduction Pathways and the Linkage to Biological Datasources
196.Pathway Analysis of Metabolic Networks: New version of METATOOL and convenient classification of metabolites
198.PIMRider : an integrated exploration platform for large protein interaction network
199.From "pathways" to functional network. A new technology for reconstruction of human metabolism.
200.Protein Pathway Mapping in Human Cells
201.MAP-Kinase-Cascade: Switch, Amplifier or Feedback Controller?
202.Genomic Object Net: Basic Architechture and Visualization for Biopathway Simulation
203.KEGG human cell cycle pathway and its comparison to the viral genomes.

185. A rapid algorithm for generating minimal pathway distances (up)
S.C.G. Rison, J.M. Thornton, Department of Biochemistry and Molecular Biology, University College London;
E. Simeonidis, I.D.L. Bogle, L.G. Papageorgiou, Department of Chemical Engineering, University College London;
Short Abstract:

We present a rapid algorithm based on mathematical programming for calculating minimal pathway distances applied to metabolic networks. The algorithm presented is capable of finding the minimal distances from the source enzyme to all enzymes in the pathway in a single pass. This step is then repeated for each enzyme.

One Page Abstract:

We present a rapid algorithm based on mathematical programming for calculating minimal pathway distances applied to metabolic networks. Minimal pathway distances are identified as the smallest number of metabolic steps separating two enzymes in a pathway. The algorithm presented deals effectively with circularity and reaction directionality. It is capable of finding the minimal distances from the source enzyme to all enzymes in the pathway in a single pass. This step is then repeated for each enzyme.

We illustrate the use of minimal pathway distances by calculating them for Escherichia coli small molecule metabolism pathways and considering their correlations with genomic distance (distance separating two genes on a chromosome) and enzyme function (as characterised by EC number).

Although we consider only metabolic networks, the algorithm is generalised and applicable to many other biological networks such as signalling pathways.

186. System analysis of complex molecular networks by mathematical simulation and control theory (up)
Hiroyuki Kurata, Kyushu Institute of Technology;
Hisao Ohtake, Hiroshima University;
H. El-Samad, Iowa State University;
T.-M. Yi, California Institute of Technology;
M. Khammash, Iowa State University;
John Doyle, California Institute of Technology;
Short Abstract:

To extract the design principle of complex molecular networks of a biological system, we developed the technology regarding bioinformatics and systems engineering. Biosimulators for synthesizing a molecular system and control theory for analyzing it were strongly required in the post-genomic era.

One Page Abstract:

In biological systems, control is carried out through molecular interaction processes, whereas in artificial substances it is performed according to calculation based on physical and chemical laws. A molecular interaction network process may be a kind of systems for calculation, but its calculation method is completely different from that of artificial substances such as a computer. Is it possible to elucidate such biological systems using control theory for an artificial substance.? Molecular interaction processes can be converted into a mathematical model, but it is hard to analytically solve them due to their nonlinearity. What we can do is not to analytically analyze a biological system, but to numerically simulate a molecular interaction process, making clear the difference and similarity between biological and artificial systems. Such comparison leads us to extract design principles underlying a molecular architecture. In this article, the comparison with the artificial process enabled us to analyze a biological system with control theory, and to predict how the interaction among subsystems was generated in a biological system. To extract the design principle out of complicated networks, we study several systems such as the heat shock response, circadian clocks, and the ammonia assimilation system. In this study, we reported the topics of the heat shock response. We present a mathematical model that reproduced the main features of the heat shock response and analyzed it with control theory whose key words were complexity, robustness, and controls. In the heat shock response, the activity and amount of s32 is controlled by three mechanisms: DnaK-mediated s32 activity control (feedback control), heat-induced translation (feedforward control), and s32 degradation of s32-epxressed FtsH (local servo feedback control). Feedback control plays a major role in the heat shock response, because feedback functions well without feedforward and autogenous controls. The addition of feedforward and local servo feedback controls increased the insensitivity to the fluctuations from other subsystems. Briefly, complexity in s32 regulation showed the capability to generate robustness in the heat shock response, thereby making the parameter insensitive to the perturbation from other subsystems. The complexity of biological systems has introduced conceptual and practical difficulties. Among the most important has been the difficulty in isolating a smaller subsystem that could be analyzed separately. Complexity seems to impede isolating smaller subsystems out of the whole system. However, this study demonstrates that complexity can generate the insensitivity to perturbations among subsystems, thereby making it possible to extract a smaller subsystem out of the whole system and analyze it separately. If robustness is a common feature of the key properties of interconnected subsystems, a biological system is a collective body of mosaic-like subsystems rather than a melting pot of subsystems.

187. Parameter Estimation of Signal Transduction Pathways using Real-Coded Genetic Algorithms (up)
Shuhei Kimura, Takashi Naka, Mariko Hatakeyama, Akihiko Konagaya, RIKEN Genomic Sciences Center;
Short Abstract:

For understanding quantitative dynamics of signal transduction, a computational simulation is one of the most effective methods. However, a computational simulation often requires several kinetic parameters which are unmeasurable by the existing experimental techniques. We use a real-coded genetic algorithm for estimating these unknown parameters for EGF signal transduction.

One Page Abstract:

For predicting the biological phenomena in cells, it is effective to create mathematical models. We choose a set of ordinary differential equations as a mathematical model of reactions in cells. For a simulation, the set of differential equations requires kinetic parameters given from biological experiments. However, several kinetic parameters cannot be obtained by the existing biological techniques.

Thus, we must estimate these parameters from the experimentally measurable data. The problem of estimating the unknown kinetic parameters is formulated as a function optimization problem, if we treat unknown parameters as decision variables, and a difference between the measurable data and simulation results as an objective value.

In this optimization problem, it is impossible to calculate differential values analytically. Moreover, if there are only few measurable data, the problem may have plural optima. A real-coded genetic algorithm (GA) is suitable for a problem that has these properties. The GA is an optimization method inspired by Darwin's theory about evolution, and especially, the real-coded GA is proper to function optimization problems. We apply the real-coded GA to the kinetic parameter estimation problem. As an example, we employed receptor tyrosine kinase signal transduction pathway followed by EGF binding in mammalian cells.

188. A two-phase partition method simulates the dynamic behavior of the heat shock response with high accuracy at a remarkably high speed. (up)
Hiroyuki Kurata, Kyushu Institute of Technology;
Short Abstract:

In order to accurately simulate the dynamic behavior of a molecular network of a biological system at an extremely high speed, the two-phase partition method was developed that automatically divided all the chemical reaction equations into two phases: the binding phase and the reaction phase.

One Page Abstract:

Metabolic Control Analysis (MCA) and Biochemical Systems Theory (BST) have been demonstrated to be useful for simulating various metabolic circuits. However, there have been few reports of successful simulation of molecular networks consisting of proteins and DNAs, such as stress responses, cell division, chemotaxis, and circadian clocks, because such pathways cannot be described by the Michaelis-Menten rate equations. Generally, conventional mass action equations or the method for simplifying complicated networks into rate equations have been employed to simulate the protein and DNA networks. The problem is that the differential equations with the rate parameters whose values were quite different in the time-scale of reactions were so stiff that the calculation time became quite large. The simplified rate equation method depended on the structures of the network and on the values of the system parameters, because it neglects some reactions to simplify a complicated network. To overcome these problems, a two-phase partition method was developed that automatically divided all the chemical reaction equations into two phases: the binding phase and the reaction phase. This method simulated all the reactions involving protein and DNA signal transduction, and calculated them at an extremely high speed. Actually, the two-phase partition method accurately simulated the dynamic behavior of the heat shock response that contained the huge differences in the time-scale of reactions. The calculation speed was 4 x 104-fold higher than the conventional mass action method. The heat shock response was an excellent model showing the dynamic behavior with a quick and sharp transient response of a regulatory protein.

189. Integration of Computational Techniques for the Modelling of Signal Transduction (up)
Pedro Pablo González, Maura Cárdenas, Carlos Gershenson, Jaime Lagúnez-Otero, Chemistry Institute, National University of Mexico (UNAM);
Short Abstract:

We present an intracellular signalling model obtained by integrating several computational techniques into an agent-based paradigm. Cellulat, the model, takes into account two essential aspects of the intracellular signalling networks: cogntivie capacities and a spatial organization. The characteristics of an intracellular signalling virtual laboratory based on our model are discussed.

One Page Abstract:

Each cell in a multicellular organism receives specific combinations of chemical signals generated by other cells or from their internal milieu. The final effect of the signals received by a cell can be translated in the regulation of the cell metabolism, in cellular division or in its death. Once the extracellular signals bind to the receptors, different signalling processes are activated, generating complex information transmission networks. The more experimental data about cellular function we obtain, the more important the computational models become. The models allow for the visualization of the network components and permit the prediction of the effects of perturbations on components or sections of the signalling pathway. Within the computer sciences, the artificial intelligence is one of the main areas to model biological systems. This is due to the great variety of models, techniques and methods that support this research area, many of which are inherited from disciplines such as cognitive sciences and neuroscience. Among the main techniques of artificial intelligence and computer sciences commonly used to model cellular signalling networks are artificial neural networks, Boolean networks, petri nets, rule-based systems, cellular automata, and multi-agent systems. The high complexity level of intracellular communication networks makes them difficult to model with any isolated technique. However, when integrating the most relevant features of these techniques in a single computational system, it should be possible to obtain a more robust model of signal transduction. This would permit a better visualization, understanding of the processes and components that integrate the networks. The theory of behaviour-based systems constitutes an useful approach for the modelling of intracellular signalling networks. The model permits to take into account communication between agents via a shared data structure, in which other cellular compartments and elements of the signalling pathways can be explicitly represented. In this sense, the blackboard architecture becomes appropriate. In this work, we propose an effective and robust model of intracellular signalling, which has been obtained joining the main structural and functional characteristics of behaviour-based systems with the blackboard architecture. That is, a cell can be seen as a society of autonomous agents, where each agent communicates with the others through the creation or modification of signals on a shared data structure, named "blackboard". The autonomous agents model determinated functional components of intracellular signalling pathways, such as signalling proteins and other mechanisms. The blackboard levels represent different cellular compartments related to the signalling pathways, whereas the different objects created on the blackboard represent signal molecules, activation or inhibition signals or others elements belonging to the intracellular medium. One of the reasons for our interest in the analysis and understanding of the signalling pathways, is the possibility of regulating them. In principle, it is possible to observe this process in a virtual laboratory based on our paradigm. In particular, we would like to see the effects of perturbations on the systems such as adding elements or taking them out as knock-outs. The expected effects would be directly on the cognitive capacity of the network and ultimately on the decisions taken by the cell in order to differentiate, proliferate or become senescent. Pathologies and natural processes can be followed in the computation of the interactions made by the components in the modelled network. The paradigm presented here is the backbone of the virtual laboratory. With the virtual laboratory we hope that etiologies and expected results of putative therapeutic strategies can be visualized.

190. Validating Metabolic Prediction (up)
Lynda B.M. Ellis, Jiangbi Liu, John Carlis, Marielle Vigouroux, C. Douglas Hershberger, Lawrence P. Wackett, University of Minnesota;
Short Abstract:

A Pathway Engine is being developed to use UM-BBD ( knowledge to predict catabolic pathways for compounds the UM-BBD does not contain. The Engine was validated using 100 compounds with known pathways. Pathways were predicted for 69 of these compounds; 91% of them were reasonably similar to known pathways.

One Page Abstract:

The University of Minnesota Biocatalysis/ Biodegradation Database (UM-BBD,, 1) provides curated information on microbial catabolic enzymes and their organization into metabolic pathways. The UM-BBD's 100+ pathways represent the major microbial routes for biotransformation of many of the organic functional groups found in the environment. However the UM-BBD will never contain information on more than a fraction of all biodegradation that may occur. Our goal is to use the data in the UM-BBD to predict possible biodegradation pathways for compounds it does not contain. Towards this goal, we are developing a Pathway Engine.

Three challenges in Pathway Engine development are similarity, similarity and similarity. Which UM-BBD compounds are similar to a query compound? How similar are the reactions these UM-BBD compounds undergo? And how similar is a predicted pathway to a known pathway? We measure compound similarity using the Tversky similarity metric (2); reaction similarity using a method developed during this project based on enzyme EC (3) codes; and pathway similarity using a method developed during this project based on dynamic, pairwise, global alignment of EC code chains.

The Pathway Engine was cross-validated using the 100 compounds that begin catabolic pathways present in the UM-BBD, containing two or more reactions. The Engine predicted one or more degradation pathways for 69 of them. For 31 of these compounds (45%) the Engine’s most similar predicted pathway was very similar to a known pathway (pathway similarity score > 0.7). An additional 32 of these compounds (46%) had a pathway that was reasonably similar to a known pathway (0.7 > pathway similarity score > 0.5). The Pathway Engine will be described and challenges to be overcome in its further development will be discussed. _________

1. Ellis, L.B.M., Hershberger, C.D., Bryan, E.M., and Wackett, L.P. (2001) "The University of Minnesota Biocatalysis/Biodegradation Database: Emphasizing Enzymes" Nucleic Acids Research 29: 340-343.

2. Bradshaw, J. (1997) “Introduction to Tversky similarity measure” Proceedings of MUG '97, the 11th Annual Daylight User Group Meeting, URL =

3. Moss, G.P (2001) “Enzyme Nomenclature” Nomenclature Commission of the International Union of Biochemistry and Molecular Biology (IUBMB). URL =

192. Scale-free Behaviour in Protein Domain Networks (up)
Stefan Wuchty, European Media Laboratory;
Short Abstract:

Several technical, social and biological networks were recently found to demonstrate scale-free and small-world behaviour. The topology of protein domain networks generated with data from popular domain databases exhibits features of small-world and scale-free nets. The extent of connectivity among domains reflects the evolutionary complexity of the organisms considered.

One Page Abstract:

Diverse disordered systems are best described as networks with complex topologies. Often the connection topology is assumed to be either completely regular or completely random. Originally, small-world graphs are generated by randomly rewiring nodes in a regular network. By defining measures that distinguish these three types of networks, several sociological and technological networks are of the small-world type. A small-world graph is formally defined as a sparse graph which is much more highly clustered than an equally sparse random graph. Scale-free networks display a connectivity distribution which decays as a power-law. This feature was found to be a direct consequence of two generic mechanisms: (1) Networks are allowed to expand continously by the addition of new vertices. (2) These newly added nodes attach preferentially to sites that are already well connected. We are thus dealing with relatively few highly connected vertices and many rare connected ones.

Recently, metabolic networks were discovered as small-world and scale-free nets. This result encouraged us to investigate protein domains in a similar fashion. With the definition of domains as nodes and edges, which connect nodes, if domains occur together in one protein, the resulting graph was found to comprise small-world and scale-free behaviour. Domain data were retrieved from popular protein domain databases.

Interestingly, the degree of connectivity is different if one focuses on different species. In conclusion, the domains show a higher connectivity the higher the evolutionary level of the organism is. Apparently, an evolutionary trend to higher connectivity of domains as well as growing complexity in the domain architecture can be detected. Thus, complex domain arrangements provide protein sets which are sufficient to preserve cellular procedures without dramatically expanding the absolute size of the proteome.

193. Inferring gene dependency networks using expression profiles from yeast deletion mutants (up)
Johan Rung, Thomas Schlitt, Alvis Brazma, Ugis Sarkans, Jaak Vilo, EMBL-EBI;
Short Abstract:

We propose a method for inferring a graph structure describing gene functional dependencies, given microarray data collected from mutation experiments. The algorithm is applied to yeast microarray data, and we present suggested functional networks from different parts of the yeast regulatory system together with a performance analysis of the algorithm.

One Page Abstract:

We propose a method for inferring a graph structure describing gene dependencies, given gene expression data collected from a set of mutation experiments. By combining the information about the observed changes in expression levels after a mutation with a statistical analysis, we gather lists of dependencies between gene pairs, together with information about the direction of changes (positive or negative influence on the mRNA level). These connections are combined into a network structure with nodes containing single genes or groups of genes. The network represents the knowledge about pairwise influences regardless of the nature of the influence. It is constructed in a way that it can be used for stand-alone analysis with predictions about genetic functions and grouping of genes, and also as a good initial probabilistic network for structure learning algorithms. We have applied the algorithm to microarray data for Saccharomyces cerevisiae by Hughes et al. (Cell, July 7, 2000), which included 274 single-gene mutations. The gene-specific error model from that publication has been used in our experiments. The full network as given by the algorithm has been analyzed for consistency with known pathways, and we present examples from different parts of the regulatory system in yeast. Also, the performance of the algorithm has been analyzed with respect to consistency of edges and grouping of genes dependent on parameter settings. A comparison with gene grouping found by regular clustering algorithms is also presented together with functional predictions for a number of ORFs with unknown function.

194. On Network Genomics (up)
Christian V. Forst, Bioscience Division, Los Alamos National Laboratory;
Short Abstract:

"Network Genomics", a new research field that combines genomic information with connectivity information of cellular networks is presented. By analyzing gene-expression of metabolic networks chemical switches of metabolic flux have been identified. A comparative network genomics approach has revealed a relationship between gene-context/operon structure and networks.

One Page Abstract:

"Network Genomics", a new research field that combines genomic information with connectivity information of cellular networks is presented. The information provided by completely sequenced genomes can yield insights into the multi-level organization of organisms and their evolution. By gene-expression networks, genes coding for individual polypeptides are expressed. Individual enzyme complexes are formed, often through assembly of multiple polypeptides. At another level, sets of enzymes group into metabolic networks.

By analyzing gene-expression of metabolic networks chemical switches of metabolic flux have been identified. Special references to relationships between gene-context/operon structure and networks are made. For this purpose a method is presented that extends the conventional sequence comparison and phylogenetic analysis of individual enzymes to metabolic networks. The method will find application in comparative network analysis of microbial organisms.

195. Semantic Modeling of Signal Transduction Pathways and the Linkage to Biological Datasources (up)
M. Weismueller, R. Eils, Div. "Intelligent Bioinformatics Systems", German Cancer Research Center (dkfz), 69120 Heidelberg, Germany;
Short Abstract:

Our aim is to model signaling networks computationally in a semi-qualitative way and to use it for simulation of protein-protein interactions describing an information flow through the cell. For the modeling we use a synchronous process algebra, pi-calculus, and import signal data from a signal transduction database TRANSPATH.

One Page Abstract:

Signal transduction (ST) is the mechanism a cell reacts on a stimulus coming from outside the cell. ST alters gene transcription in the nucleus, therefore changing protein synthesis and the behavior of the cell. ST can be described as an information flow from outside into the cell mediated by biochemical reactions of signal molecules. ST pathways play a major role in the field of cancer research. Several pathways have been identified to be responsible for cancer development by over- / underexpression of genes or by functional modification of signal proteins caused by alterations of their sequence.

Quantitative data and measurements of signal molecules are not yet available for a comprehensive number of pathways. Several model systems have been studied in detail including concentration and activity measurements of signal molecules. But these attempts are not sufficient to allow a study of whole signal transduction networks of cells. Therefore the idea is to reduce the view on signal information flow in the cell to a state based one: A protein is active (mediating information) or inactive (not mediating information). Additional information is incooperated when available from biological experiments: Protein X binds to protein Y, protein X phosphorylates protein Y etc.

One way to describe this non-quantitative view on signal transduction of cells is the qualitative modeling of signal information flow through the cell. The information flow is an abstract view on biochemical reactions of signal molecules. These interactions of molecules are semantically modeled describing the biochemical interaction not in numerical equations like differential equations, but in abstracted biochemical reaction descriptions.

The aim to use the information of a ST database - TRANSPATH ( - to build up a comprehensive model of ST pathways in the computer. One should be able to answer biological questions about the interaction or alteration of pathways under certain conditions and formulate hypotheses, which might be tested in experiments.

To model ST pathways the pi-calculus ( is used to represent parallel interactions of proteins. This notion was adapted from the BioPSI project ( The pi-calculus is a kind of programming language. Protein interactions of ST pathways can be programmed and simulated using the information of TRANSPATH. These simulations result in an output, which has to be interpreted under the posed conditions.

The first step of the work is to model an important ST pathway: the ERK-MAPK pathway. In this model a protein is interpreted as a computational unit having an input layer, a computational layer and an output layer. This pathway model implementation exemplifies how ST pathways can be built up in a computer.

196. Pathway Analysis of Metabolic Networks: New version of METATOOL and convenient classification of metabolites (up)
Stefan Schuster, Ferdinand Moldenhauer, Ionela Oancea, Max Delbruck Center for Molecular Medicine, Dept. of Bioinformatics, D-13092 Berlin-Buch, Germany;
Thomas Pfeiffer, ETH Zurich, Experimental Ecology / Theoretical Biology, CH-8092 Zurich, Switzerland;
Short Abstract:

The concept of elementary modes formalizes the term "biochemical pathway." We present the newest version of METATOOL, a program for determining elementary modes and other topological features of metabolism. We outline strategies for finding a convenient classification of source and sinks metabolites and intermediates. This is illustrated by biochemical examples.

One Page Abstract:

The topological analysis of metabolic networks has become an important integrative part of bioinformatics. This analysis includes methods for the computer-aided synthesis of biochemical pathways, which is instrumental in functional genomics and biotechnology (Schuster et al., 2000). One of these methods is based on the concept of elementary flux modes. It allows one to test whether sets of enzymes form a coherent pathway allowing mass balancing for each intermediate and complying with the directionality of reactions (irreversibility). Importantly, pathway analysis can be performed without the knowledge of kinetic parameters. An algorithm for computing all elementary modes in biochemical reaction networks of any complexity has been implemented by us earlier, in the program METATOOL (Pfeiffer et al., 1999). Here, we present the newest version of METATOOL (version 3.5), which includes several new features such as the detection of the connectivity distribution (connectivity is defined as the number of reactions in which a given metabolite participates). Moreover, the branch point metabolites of a network and the conservation relations are explicitly given. Dead-end metabolites and sets of inconsistent irreversible reactions are indicated, which helps the user check model consistency. Moreover, the elementary modes are compared with the modes in the convex basis.

An important technical question in the computation of elementary modes is the convenient classification of external metabolites (sources and sinks) and internal metabolites (intermediates). A reasonable criterion for this classification is to minimize the number of elementary modes. This criterion is related to Kolmogorov complexity and was chosen in order to reduce combinatorial explosion in complex networks. We present two strategies (implemented as C programs) to find the convenient classification. These tools are illustrated by biochemical networks taken from nucleotide metabolism and monosaccharide metabolism.

References T. Pfeiffer, I. Sanchez-Valdenebro, J.C. Nuno, F. Montero, S. Schuster: METATOOL: For Studying Metabolic Networks. Bioinformatics 15 (1999) 251-257. S. Schuster, D. Fell, T. Dandekar: A General Definition of Metabolic Pathways Useful for Systematic Organization and Analysis of Complex Metabolic Networks. Nature Biotechnol. 18 (2000) 326-332.

198. PIMRider : an integrated exploration platform for large protein interaction network (up)
Jérôme WOJCIK, Fabien PETEL, Alain MEIL, Vincent SCHACHTER, Yvan CHEMAMA, Hybrigenics S.A., Paris, France;
Short Abstract:

The PIMRider is a web-based software platform developed to visualize and explore protein interaction networks. Experimental protein-protein interactions derived from yeast two-hybrid assays are integrated with external database annotations in a rich data structure. Modular viewers allow the biologist to focus on specific pathways and formulate new interpretations.

One Page Abstract:

Proteome-wide technologies that are now massively being used in the protein function study require highly sophisticated bioinfomatics tools to store and utilize the large amount of experimental data produced. We have developed a software platform to integrate in-house yeast two-hybrid assay data with several public and partner databases. "Rough" experimental data once stored are post-processed with specific algorithms that improve the reliability and the comprehensibility of the information. Finally, via several dedicated viewers refined results are available on-line to the scientific community and partners : the ProteinViewer™ displays the annotations, bibliographies, database entries, genomic information and interactions found for each protein of the proteome studied; the InteractionViewer™ displays in a graphical mode details of the interaction found by the yeast two-hybrid assay where interacting fragments and the computed Selected Interacting Domain (SID®) are positioned relatively to the coding sequence of the two proteins; the MultiSIDViewer™ displays in a graphical mode all the SID® computed and positioned relatively to the coding sequence of the protein studied; the PIMViewer™ displays the cell-wide protein interaction map as a graph and allows the biologist to filter information depending on their reliability and focus on a particular pathway; the PIMRider® Annotator module allows partner scientists to edit protein and interaction annotations on-line. The platform is based on multi-tier architecture including an Oracle relational database server accessible through a SQL layer, a Java Server Page™ that generates the HTML pages (viewers are included in the HTML pages as Java applets) and an Apache server to handle http queries. The PIMRider® platform permits to visualize both the experimental protein interaction map of Helicobacter pylori and the interaction network of Escherichia coli that were respectively used as source and predicted by the 'Interacting Domain Profile Pair' inference method (Wojcik and Schächter, ISMB 2001 communication). A PIMRider® free demonstration is available at

199. From "pathways" to functional network. A new technology for reconstruction of human metabolism. (up)
Tatiana Nikolskaya, Ph.D., Andrej Bugrim, Ph.D., GeneGo LLC;
Short Abstract:

We present a new technology, called functional reconstructions. It allows identification of a set of major metabolic, regulatory and developmental "functional units" in the context of a biochemical network. Our method involves integration of known human-specific pathways with kinds of data for computational reconstruction and analysis of relevant metabolic network.

One Page Abstract:

"Traditional" view of biochemistry was formulated in terms of "pathways", where a chain of biochemical transformations, a pathway presumably serves its specific function in the cell. On the other hand, many recent studies show that metabolic and cell signaling processes are actually highly interconnected and networks of immense complexity can potentially result from combining a limited number of reactions and interactions in many different combinations and sequences. How to reconcile these views? Here we present a new technology, called functional reconstructions. Our goal is to identify a set of major metabolic, regulatory and developmental "functional units" in the context of a biochemical network as a whole. We start with identification, careful annotation and elucidation of human-specific pathways for which biochemical evidence exists. Such "biochemical reconstructions" serve as informational "skeleton" for efficient functional integrating of different medical, biological and genomic kinds of data, thus providing a missing link between clinical data and human genome sequence. At the second stage we extend our collection of the pathways by computational reconstruction of relevant metabolic network. Finally, by integration of expression data into resulting metabolic map we can generate a "snap shot" for any specific cell, tissue, disease or condition. Comparison of such snap shots made for the same tissue at different developmental stages or different conditions provides a framework for identification of regulatory pathways and other potential "functional units" in the biochemical network, eventually leading to construction of a "functional view" of such network - Functional Reconstruction.

Our technology allows to:

1. Restore complicated cellular networks using abundant gene expression data (EST and micro-array) as well as genome sequence. 2. Precisely identify relationships between different human genes, pathways and parts of metabolism 3. Identify all over- and under-expressed genes, specific for given tissue/condition 4. Generate interactive, integrative metabolic functional outlines for all parts of human metabolism. 5. Produce user-friendly expression circuits for visualization and clustering of micro-array data. 6. Functionally localize SNPs and other genetic markers on generated metabolic and regulatory maps. 7. Propose human-specific developmental pathways by applying data from other organisms to human-specific functional reconstructions.

200. Protein Pathway Mapping in Human Cells (up)
Kunbin Qu, Nan Lin, Xiang Xu, Donald Payan, Rigel Pharmaceuticals, Inc.;
Short Abstract:

We present a large-scale (several hundred baits) pathway map in human cells by yeast-two-hybrid. The binding is represented as a matrix. Gene classification is achieved by recursively joining the matrix elements. Inferences are made for novel genes, providing a useful tool for functional annotation and pathway mapping.

One Page Abstract:

We present a large-scale pathway map of protein-protein interactions in human cells by yeast-two-hybrid methodologies and downstream data analysis. In the yeast-two-hybrid system, the protein of interest (the bait) is fused to a known DNA-binding domain such as GAL4, and the potential hit (a member of the cDNA library being screened) is fused to a cognate transcriptional activation domain. Co-expression of the two chimeric proteins results in transcriptional activation of the reporter that is downstream of the DNA-binding domain if the chimeric proteins associate. Baits utilized in this study include several hundred members of the following pathways: T and B cell signaling, cell cycle regulation, TNF pathway, exocytosis and others. Each bait generated five hits on average, in accordance with that published by Tucker et. al. (2001). The entire interaction network can be viewed as a matrix in which baits are represented by rows, and the non-redundant hits are listed in columns (cDNA library fragments are grouped by sequence similarity). The binding relationship of the bait and hit is represented by a binary vector within the matrix, the number 1 indicating a specific interaction, and 0 for no interaction. The binary matrix is then converted to a probabilistic matrix by the following fashion: each element is added by a pseudo-count, its value is then normalized based on the binding number of the whole network. Gene classification for both baits and hits is achieved by recursively joining the two elements with the highest Pearson correlation coefficients calculated from the probabilistic matrix until the matrix dimension reduces to one in the direction that the joining is performed. This process leads to clustering of genes with a similar binding vector profile. Those genes have a higher probability of sharing similar biological function and pathway assuming that they interact with similar proteins in the cell. Therefore, inferences are made for both baits and hits based on clustered members with documentation, providing a useful tool for functional annotation and detecting new members of a known pathway. For example, cRaf, Traf2, Traf5, I-flice, RIP, Flame-1, Clarp and Mch5 are clustered together by this analysis. Although these proteins have distinct roles in differing signaling pathways, they all participate in the biological process of programmed cell death. Another group has SAP, Fyn, Lyn and STAT1. These genes encode proteins with varying functional domains including adaptor proteins, kinases, and transcription factors. Commonality is found in the presence of an SH2 domain and a functional role in a variety of immune responses by association with the specific receptors. A graphical representation of the complexity-reduced network based on the clustered nodes provides better visualization of the resultant pathway network. The graph is implemented through a modified multilevel force-directed graph drawing algorithm (Walshaw G., 2000). This multilevel algorithm accelerates a large graph by force-directed layout with an improved regional and global quality up to 100,000 nodes. Detailed annotation and pathway mapping of novel genes present in each cluster is under way.

Tucker CL, Gera JF, Uetz P. Towards an understanding of complex protein networks. Trends in Cell Biology. Vol. 11, No. 3: 102-106.

Walshaw C. A Multilevel Algorithm for Force-Directed Graph Drawing. Tech. Rep. 00/IM/60, Univ. Greenwich, London SE10 9LS, UK, April 2000.

201. MAP-Kinase-Cascade: Switch, Amplifier or Feedback Controller? (up)
Nils Blüthgen, Hanspeter Herzel, Innovationskolleg Theoretische Biologie;
Short Abstract:

The MAP-Kinase-Cascade is a highly conserved module in signaling pathways in eukaryotes. By modeling reaction kinetics, we investigate the steady-states and dynamics of the system. We show how the switch-like behavior is realized and how amplification is generated. We also show adaptation introducing a negative feedback loop.

One Page Abstract:

The three-step MAP-Kinase-Cascade is a highly conserved module in signaling pathways. It is present in all eukaryotes and has a wide range of functions in signal transductions, e.g. stress-response, cell-cycle-control, cell-wall-construction, osmosensor, growth and differentiation. By modeling the reaction kinetics of the cascade we investigate the properties of steady state solutions and the dynamical behavior under the action of a negative feedback loop.

The system shows different behavior depending on the fraction of activated MAPKK: in the low activation range a rather switch-like response is observed while in the intermediate activation range amplification increases. This corresponds to a shift of the working point dependent on activated MAPKK concentration and other reaction parameters. In order to characterize the steady-state behavior of the whole MAP-kinase cascade we fit the signal response with a Hill curve. This defines a Hill coefficient for the entire system. Within this framework the models of Bhalla/Iyengar[1] and Huang/Ferrell[2] are compared and the remarkably different characteristics of their models can be understood. The robustness of the switch-like response is investigated by calculation of Hill-coefficients for varying reaction parameters.

Introducing an indirect negative feedback loop, the MAPK-Cascade shows damped oscillations, which can be interpreted as adaptation to different upstream signals. Asthagiri and Laufenburger suggest that the integral of activated MAPK over time is a reasonable metric for encapsulating information for transcription[3]. We analyse this integral for increasing stimulus.

References: [1] Science 1999. 283: 381-387 [2] PNAS 1996. 93: 10078-10083 [3] Annu. Rev. Biomed Eng. 2000. 02:31-53

202. Genomic Object Net: Basic Architechture and Visualization for Biopathway Simulation (up)
Hiroshi Matsuno, Atsushi Doi, Yamaguchi University;
Rainer Drath, ABB AG in Heidelberg, Germany;
Satoru Miyano, Human Genome Center, Institute of Medical Science, The University of Tokyo, 4-6-1 Shirokanedai, Minato-ku, Tokyo 108-;
Short Abstract:

Genomic Object Net is a software tool for describing and simulating structurally complex dynamic causal interactions and processes such as metabolic pathways, signal transduction cascades, gene regulations. The notion of hybrid object net is employed as its basic architechture, and visualization technique is developed for intuitive understanding of biopathway simulation.

One Page Abstract:

Along with the completion of many genome sequencing projects, a new interest of research is emerging for elucidating how the living systems function in terms of all levels of biological information, and then to develop information technology for applying such systemic information to medicine and biology. Among many issues related to this matter, a vital necessity is to develop information technology with which we can easily represent and simulate the structurally complex dynamic causal interactions and processes of various biological objects such as genomic DNA, mRNA, proteins, functional proteins, molecular transactions and processes such as metabolic pathways, signal transduction cascades, genetic networks, etc.

In order for software tools to be accepted by users in biology/medicine for biopathway representation and simulation, the following two matters should be resolved, at least: (1) Remove issues which are irrelevant to biological importance; (2) Allow users to represent biopathways intuitively and understand/manage easily the details of representation and simulation mechanism. We have developed a software tool Genomic Object Net (http://www.GenomicObject.Net/) for representing and simulating biopathways based on [1,2] together with visualization strategy that would satisfy (1) and (2). Its employs the notion of hybrid object net [2] as its basic simulation architechure. Usually, a biopathway information is conceputually described as a figure together with the explanation about the relations between biological objects of concern and the measured/observed data proving their qualitative/quantitative relations. These information can be easily described and simulated with Genomic Object Net. We show some representation and simulation examples of typical biopathways related to gene regulation, metabolic pathway, and signal transduction, which cover the basic ascpects in biopathways.

[1] Matsuno, H., Doi, A., Nagasaki, M., and Miyano, S. 2000. Hybrid Petri net representation of gene regulatory network. Proc. Pacific Symposium on Biocomputing 2000, pp. 338-349.

[2] Drath, R. 1998. Hybrid Object Nets: An object oriented concept for modeling complex hybrid systems. Proc. Hybrid Dynamical Systems. 3rd International Conference on Automation of Mixed Processes, ADPM'98, pp. 437-442.

203. KEGG human cell cycle pathway and its comparison to the viral genomes. (up)
Toshiaki Katayama, Yoshinori Okuji, Minoru Kanehisa, Bioinformatics Center, Kyoto University, Japan;
Short Abstract:

We have constructed human and yeast cell cycle pathway database under the KEGG project. We determined conserved and diverse pathways between these two species. By mapping homologous viral genes onto this pathway map, strategies of the viral proliferation were strongly suggested.

One Page Abstract:

Molecular mechanisms of the eukaryotic cell cycle regulation have been massively studied in the past decade. We have assembled this knowledge from literature and constructed yeast and human cell cycle regulatory pathway diagrams under the KEGG project. Compared to other works, our presentation provides an overall picture on the control flows involving various molecular interactions in the eukaryotic cell division. These pathway diagrams can be used for gene function assignment in other organisms, comparative network analysis of complex biological pathways, visualization and correlation analysis of gene expression data from microarrays, among others. In this study, we have mapped homologous viral genes onto the pathway diagrams by sequence similarity, which is a practical example of utilizing our pathway data. In parallel, we have constructed a database of viral genes from a set of complete viral genomes, called v-GENES and v-GENOME. As a result of homology search of v-GENES entries against pathway components, many viruses revealed to have counterparts of the cell cycle regulatory genes. For example, viruses have G1 Cyclin/CDK and its regulators or G1 transcription initiators, but do not have any subunit of a large protein complex. Such a tendency suggests that viruses carry only those genes that can critically affect initiation of the host cell's proliferative activities. We will show these results with taxonomical classifications of viruses having homologous genes to their hosts at the poster session. KEGG/PATHWAY, v-GENES, and v-GENOME databases are available from KEGG website at