MOTIVATION: The functional complexity of biochemical processes is strongly related to the interplay of proteins and their assembly into protein complexes. In recent years, the discovery and characterization of protein complexes have substantially progressed through advances in cryo-electron microscopy, proteomics, and computational structure prediction. This development results in a strong need for computational approaches to analyse the data of large protein complexes for structural and functional characterization. Here, we aim to provide a suitable approach, which processes the growing number of large protein complexes, to obtain biologically meaningful information on the hierarchical organization of the structures of protein complexes. RESULTS: We modelled the quaternary structure of protein complexes as undirected, labelled graphs called complex graphs. In complex graphs, the vertices represent protein chains and the edges spatial chain-chain contacts. We hypothesized that clusters based on the complex graph correspond to functional biological modules. To compute the clusters, we applied the Leiden clustering algorithm. To evaluate our approach, we chose the human respiratory complex I, which has been extensively investigated and exhibits a known biological module structure experimentally validated. Additionally, we characterized a eukaryotic group II chaperonin TRiC/CCT and the head of the bacteriophage Φ29. The analysis of the protein complexes correlated with experimental findings and indicated known functional, biological modules. Using our approach enables not only to predict functional biological modules in large protein complexes with characteristic features but also to investigate the flexibility of specific regions and coformational changes. The predicted modules can aid in the planning and analysis of experiments. AVAILABILITY AND IMPLEMENTATION: Jupyter notebooks to reproduce the examples are available on our public GitHub repository: https://github.com/MolBIFFM/PTGLtools/tree/main/PTGLmodulePrediction.

BACKGROUND: Prostate cancer is a major health concern in aging men. Paralleling an aging society, prostate cancer prevalence increases emphasizing the need for efficient diagnostic algorithms. METHODS: Retrospectively, 106 prostate tissue samples from 48 patients (mean age, [Formula: see text] years) were included in the study. Patients suffered from prostate cancer (n = 38) or benign prostatic hyperplasia (n = 10) and were treated with radical prostatectomy or Holmium laser enucleation of the prostate, respectively. We constructed tissue microarrays (TMAs) comprising representative malignant (n = 38) and benign (n = 68) tissue cores. TMAs were processed to histological slides, stained, digitized and assessed for the applicability of machine learning strategies and open-source tools in diagnosis of prostate cancer. We applied the software QuPath to extract features for shape, stain intensity, and texture of TMA cores for three stainings, H&E, ERG, and PIN-4. Three machine learning algorithms, neural network (NN), support vector machines (SVM), and random forest (RF), were trained and cross-validated with 100 Monte Carlo random splits into 70% training set and 30% test set. We determined AUC values for single color channels, with and without optimization of hyperparameters by exhaustive grid search. We applied recursive feature elimination to feature sets of multiple color transforms. RESULTS: Mean AUC was above 0.80. PIN-4 stainings yielded higher AUC than H&E and ERG. For PIN-4 with the color transform saturation, NN, RF, and SVM revealed AUC of [Formula: see text], [Formula: see text], and [Formula: see text], respectively. Optimization of hyperparameters improved the AUC only slightly by 0.01. For H&E, feature selection resulted in no increase of AUC but to an increase of 0.02-0.06 for ERG and PIN-4. CONCLUSIONS: Automated pipelines may be able to discriminate with high accuracy between malignant and benign tissue. We found PIN-4 staining best suited for classification. Further bioinformatic analysis of larger data sets would be crucial to evaluate the reliability of automated classification methods for clinical practice and to evaluate potential discrimination of aggressiveness of cancer to pave the way to automatic precision medicine.

The paper describes a mathematical model of the molecular switches of cell survival, apoptosis, and necroptosis in cellular signaling pathways initiated by tumor necrosis factor 1. Based on experimental findings in the literature, we constructed a Petri net model based on detailed molecular reactions of the molecular players, protein complexes, post-translational modifications, and cross talk. The model comprises 118 biochemical entities, 130 reactions, and 299 edges. We verified the model by evaluating invariant properties of the system at steady state and by in silico knockout analysis. Applying Petri net analysis techniques, we found 279 pathways, which describe signal flows from receptor activation to cellular response, representing the combinatorial diversity of functional pathways.120 pathways steered the cell to survival, whereas 58 and 35 pathways led to apoptosis and necroptosis, respectively. For 65 pathways, the triggered response was not deterministic and led to multiple possible outcomes. We investigated the in silico knockout behavior and identified important checkpoints of the TNFR1 signaling pathway in terms of ubiquitination within complex I and the gene expression dependent on NF-κB, which controls the caspase activity in complex II and apoptosis induction. Despite not knowing enough kinetic data of sufficient quality, we estimated system's dynamics using a discrete, semi-quantitative Petri net model.

SUMMARY: We provide a software to describe the topology of large protein complexes based mainly on cryo-EM data and stored as macromolecular Crystallographic Information Files (mmCIFs) in the PDB. The software extends the Protein Topology Graph Library and implements an efficient file parser to analyze mmCIFs. The extended Protein Topology Graph Library includes a graph-based representation of the topology of protein complexes on the supersecondary and quaternary structure level. The library holds topology graphs of 151 837 PDB files; 921 of them are large structures. The abstraction of protein structure complexes to undirected labeled graphs enables classification and comparison of large protein complexes on quaternary structure level. AVAILABILITY AND IMPLEMENTATION: Online access at http://ptgl.uni-frankfurt.de. Source code in Java under GNU public license 2.0 at https://github.com/MolBIFFM/vplg. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In pathology, tissue images are evaluated using a light microscope, relying on the expertise and experience of pathologists. There is a great need for computational methods to quantify and standardize histological observations. Computational quantification methods become more and more essential to evaluate tissue images. In particular, the distribution of tumor cells and their microenvironment are of special interest. Here, we systematically investigated tumor cell properties and their spatial neighborhood relations by a new application of statistical analysis to whole slide images of Hodgkin lymphoma, a tumor arising in lymph nodes, and inflammation of lymph nodes called lymphadenitis. We considered properties of more than 400, 000 immunohistochemically stained, CD30-positive cells in 35 whole slide images of tissue sections from subtypes of the classical Hodgkin lymphoma, nodular sclerosis and mixed cellularity, as well as from lymphadenitis. We found that cells of specific morphology exhibited significantly favored and unfavored spatial neighborhood relations of cells in dependence of their morphology. This information is important to evaluate differences between Hodgkin lymph nodes infiltrated by tumor cells (Hodgkin lymphoma) and inflamed lymph nodes, concerning the neighborhood relations of cells and the sizes of cells. The quantification of neighborhood relations revealed new insights of relations of CD30-positive cells in different diagnosis cases. The approach is general and can easily be applied to whole slide image analysis of other tumor types.

SUMMARY: isiKnock is a new software that automatically conducts in silico knockouts for mathematical models of signaling pathways. The software allows for the prediction of the behavior of biological systems after single or multiple knockout. The implemented algorithm applies transition invariants and the novel concept of Manatee invariants. A knockout matrix visualizes the results. The tool enables the analysis of dependencies, for example, in signal flows from the receptor activation to the cell response at steady state. AVAILABILITY AND IMPLEMENTATION: isiKnock is an open-source tool, freely available at http://www.bioinformatik.uni-frankfurt.de/tools/isiKnock/. It requires at least Java 8 and runs under Microsoft Windows, Linux, and Mac OS.

BACKGROUND: Autophagy is a conserved molecular pathway involved in the degradation and recycling of cellular components. It is active either as response to starvation or molecular damage. Evidence is emerging that autophagy plays a key role in the degradation of damaged cellular components and thereby affects aging and lifespan control. In earlier studies, it was found that autophagy in the aging model Podospora anserina acts as a longevity assurance mechanism. However, only little is known about the individual components controlling autophagy in this aging model. Here, we report a biochemical and bioinformatics study to detect the protein-protein interaction (PPI) network of P. anserina combining experimental and theoretical methods. RESULTS: We constructed the PPI network of autophagy in P. anserina based on the corresponding networks of yeast and human. We integrated PaATG8 interaction partners identified in an own yeast two-hybrid analysis using ATG8 of P. anserina as bait. Additionally, we included age-dependent transcriptome data. The resulting network consists of 89 proteins involved in 186 interactions. We applied bioinformatics approaches to analyze the network topology and to prove that the network is not random, but exhibits biologically meaningful properties. We identified hub proteins which play an essential role in the network as well as seven putative sub-pathways, and interactions which are likely to be evolutionary conserved amongst species. We confirmed that autophagy-associated genes are significantly often up-regulated and co-expressed during aging of P. anserina. CONCLUSIONS: With the present study, we provide a comprehensive biological network of the autophagy pathway in P. anserina comprising PPI and gene expression data. It is based on computational prediction as well as experimental data. We identified sub-pathways, important hub proteins, and evolutionary conserved interactions. The network clearly illustrates the relation of autophagy to aging processes and enables further specific studies to understand autophagy and aging in P. anserina as well as in other systems.

UNLABELLED: : We introduce Path2PPI, a new R package to identify protein-protein interaction (PPI) networks for fully sequenced organisms for which nearly none PPI are known. Path2PPI predicts PPI networks based on sets of proteins from well-established model organisms, providing an intuitive visualization and usability. It can be used to combine and transfer information of a certain pathway or biological process from several reference organisms to one target organism. AVAILABILITY AND IMPLEMENTATION: Path2PPI is an open-source tool implemented in R. It can be obtained from the Bioconductor project: http://bioconductor.org/packages/Path2PPI/ CONTACT: : [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Hodgkin lymphoma (HL) is a type of B-cell lymphoma. To diagnose the subtypes, biopsies are taken and immunostained. The slides are scanned to produce high-resolution digital whole slide images (WSI). Pathologists manually inspect the spatial distribution of cells, but little is known on the statistical properties of cell distributions in WSIs. Such properties would give valuable information for the construction of theoretical models that describe the invasion of malignant cells in the lymph node and the intercellular interactions. RESULTS: In this work, we define and discuss HL cell graphs. We identify CD30(+) cells in HL WSIs, bringing together the fields of digital imaging and network analysis. We define special graphs based on the positions of the immunostained cells. We present an automatic analysis of complete WSIs to determine significant morphological and immunohistochemical features of HL cells and their spatial distribution in the lymph node tissue under three different medical conditions: lymphadenitis (LA) and two types of HL. We analyze the vertex degree distributions of CD30 cell graphs and compare them to a null model. CD30 cell graphs show higher vertex degrees than expected by a random unit disk graph, suggesting clustering of the cells. We found that a gamma distribution is suitable to model the vertex degree distributions of CD30 cell graphs, meaning that they are not scale-free. Moreover, we compare the graphs for LA and two subtypes of HL. LA and classical HL showed different vertex degree distributions. The vertex degree distributions of the two HL subtypes NScHL and mixed cellularity HL (MXcHL) were similar. AVAILABILITY AND IMPLEMENTATION: The CellProfiler pipeline used for cell detection is available at https://sourceforge.net/projects/cellgraphs/. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUMMARY: We present a new, extended version of the Protein Topology Graph Library web server. The Protein Topology Graph Library describes the protein topology on the super-secondary structure level. It allows to compute and visualize protein ligand graphs and search for protein structural motifs. The new server features additional information on ligand binding to secondary structure elements, increased usability and an application programming interface (API) to retrieve data, allowing for an automated analysis of protein topology. AVAILABILITY AND IMPLEMENTATION: The Protein Topology Graph Library server is freely available on the web at http://ptgl.uni-frankfurt.de. The website is implemented in PHP, JavaScript, PostgreSQL and Apache. It is supported by all major browsers. The VPLG software that was used to compute the protein ligand graphs and all other data in the database is available under the GNU public license 2.0 from http://vplg.sourceforge.net. CONTACT: [email protected]; [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The hallmarks of Alzheimer's disease (AD) are characterized by cognitive decline and behavioral changes. The most prominent brain region affected by the progression of AD is the hippocampal formation. The pathogenesis involves a successive loss of hippocampal neurons accompanied by a decline in learning and memory consolidation mainly attributed to an accumulation of senile plaques. The amyloid precursor protein (APP) has been identified as precursor of Aβ-peptides, the main constituents of senile plaques. Until now, little is known about the physiological function of APP within the central nervous system. The allocation of APP to the proteome of the highly dynamic presynaptic active zone (PAZ) highlights APP as a yet unknown player in neuronal communication and signaling. In this study, we analyze the impact of APP deletion on the hippocampal PAZ proteome. The native hippocampal PAZ derived from APP mouse mutants (APP-KOs and NexCreAPP/APLP2-cDKOs) was isolated by subcellular fractionation and immunopurification. Subsequently, an isobaric labeling was performed using TMT6 for protein identification and quantification by high-resolution mass spectrometry. We combine bioinformatics tools and biochemical approaches to address the proteomics dataset and to understand the role of individual proteins. The impact of APP deletion on the hippocampal PAZ proteome was visualized by creating protein-protein interaction (PPI) networks that incorporated APP into the synaptic vesicle cycle, cytoskeletal organization, and calcium-homeostasis. The combination of subcellular fractionation, immunopurification, proteomic analysis, and bioinformatics allowed us to identify APP as structural and functional regulator in a context-sensitive manner within the hippocampal active zone network.

The degradation of cytosol-invading pathogens by autophagy, a process known as xenophagy, is an important mechanism of the innate immune system. Inside the host, Salmonella Typhimurium invades epithelial cells and resides within a specialized intracellular compartment, the Salmonella-containing vacuole. A fraction of these bacteria does not persist inside the vacuole and enters the host cytosol. Salmonella Typhimurium that invades the host cytosol becomes a target of the autophagy machinery for degradation. The xenophagy pathway has recently been discovered, and the exact molecular processes are not entirely characterized. Complete kinetic data for each molecular process is not available, so far. We developed a mathematical model of the xenophagy pathway to investigate this key defense mechanism. In this paper, we present a Petri net model of Salmonella xenophagy in epithelial cells. The model is based on functional information derived from literature data. It comprises the molecular mechanism of galectin-8-dependent and ubiquitin-dependent autophagy, including regulatory processes, like nutrient-dependent regulation of autophagy and TBK1-dependent activation of the autophagy receptor, OPTN. To model the activation of TBK1, we proposed a new mechanism of TBK1 activation, suggesting a spatial and temporal regulation of this process. Using standard Petri net analysis techniques, we found basic functional modules, which describe different pathways of the autophagic capture of Salmonella and reflect the basic dynamics of the system. To verify the model, we performed in silico knockout experiments. We introduced a new concept of knockout analysis to systematically compute and visualize the results, using an in silico knockout matrix. The results of the in silico knockout analyses were consistent with published experimental results and provide a basis for future investigations of the Salmonella xenophagy pathway.

SUMMARY: We introduce nova, a software for the analysis of complexome profiling data. nova supports the investigation of the composition of complexes, cluster analysis of the experimental data, visual inspection and comparison of experiments and many other features. AVAILABILITY AND IMPLEMENTATION: nova is licensed under the Artistic License 2.0. It is freely available at http://www.bioinformatik.uni-frankfurt.de. nova requires at least Java 7 and runs under Linux, Microsoft Windows and Mac OS. CONTACT: [email protected].

BACKGROUND: The concept of Petri nets (PN) is widely used in systems biology and allows modeling of complex biochemical systems like metabolic systems, signal transduction pathways, and gene expression networks. In particular, PN allows the topological analysis based on structural properties, which is important and useful when quantitative (kinetic) data are incomplete or unknown. Knowing the kinetic parameters, the simulation of time evolution of such models can help to study the dynamic behavior of the underlying system. If the number of involved entities (molecules) is low, a stochastic simulation should be preferred against the classical deterministic approach of solving ordinary differential equations. The Stochastic Simulation Algorithm (SSA) is a common method for such simulations. The combination of the qualitative and semi-quantitative PN modeling and stochastic analysis techniques provides a valuable approach in the field of systems biology. RESULTS: Here, we describe the implementation of stochastic analysis in a PN environment. We extended MONALISA - an open-source software for creation, visualization and analysis of PN - by several stochastic simulation methods. The simulation module offers four simulation modes, among them the stochastic mode with constant firing rates and Gillespie's algorithm as exact and approximate versions. The simulator is operated by a user-friendly graphical interface and accepts input data such as concentrations and reaction rate constants that are common parameters in the biological context. The key features of the simulation module are visualization of simulation, interactive plotting, export of results into a text file, mathematical expressions for describing simulation parameters, and up to 500 parallel simulations of the same parameter sets. To illustrate the method we discuss a model for insulin receptor recycling as case study. CONCLUSIONS: We present a software that combines the modeling power of Petri nets with stochastic simulation of dynamic processes in a user-friendly environment supported by an intuitive graphical interface. The program offers a valuable alternative to modeling, using ordinary differential equations, especially when simulating single-cell experiments with low molecule counts. The ability to use mathematical expressions provides an additional flexibility in describing the simulation parameters. The open-source distribution allows further extensions by third-party developers. The software is cross-platform and is licensed under the Artistic License 2.0.

Erratum After publication of the original article [1] the authors have brought to our attention that the following revisions had not been incorporated into the final published version. In Definition 1 (Petri net): “E⊆ ((P x T)∪(T x P))” is the set of directed edges not “E⊆ ((P T) ∪ (T P))”. A segment of the Legend in Figure two: “A model of insulin receptor activation and recycling.” was incorrect and has been removed. The Legend of Figure three was incorrect and the correct legend is: “The model of insulin receptor recycling according to Figure 2 is represented as a Petri net. Places are drawn as circles and transitions as black squares.” These mistakes have been updated in the original article as detailed in this erratum.

BACKGROUND: Microarray analysis represents a powerful way to test scientific hypotheses on the functionality of cells. The measurements consider the whole genome, and the large number of generated data requires sophisticated analysis. To date, no gold-standard for the analysis of microarray images has been established. Due to the lack of a standard approach there is a strong need to identify new processing algorithms. METHODS: We propose a novel approach based on hyperbolic partial differential equations (PDEs) for unsupervised spot segmentation. Prior to segmentation, morphological operations were applied for the identification of co-localized groups of spots. A grid alignment was performed to determine the borderlines between rows and columns of spots. PDEs were applied to detect the inflection points within each column and row; vertical and horizontal luminance profiles were evolved respectively. The inflection points of the profiles determined borderlines that confined a spot within adapted rectangular areas. A subsequent k-means clustering determined the pixels of each individual spot and its local background. RESULTS: We evaluated the approach for a data set of microarray images taken from the Stanford Microarray Database (SMD). The data set is based on two studies on global gene expression profiles of Arabidopsis Thaliana. We computed values for spot intensity, regression ratio, and coefficient of determination. For spots with irregular contours and inner holes, we found intensity values that were significantly different from those determined by the GenePix Pro microarray analysis software. We determined the set of differentially expressed genes from our intensities and identified more activated genes than were predicted by the GenePix software. CONCLUSIONS: Our method represents a worthwhile alternative and complement to standard approaches used in industry and academy. We highlight the importance of our spot segmentation approach, which identified supplementary important genes, to better explains the molecular mechanisms that are activated in a defense responses to virus and pathogen infection.

SUMMARY: Structural modeling of biochemical networks enables qualitative as well as quantitative analysis of those networks. Automated network decomposition into functional modules is a crucial point in network analysis. Although there exist approaches for the analysis of networks, there is no open source tool available that combines editing, visualization and the computation of steady-state functional modules. We introduce a new tool called MonaLisa, which combines computation and visualization of functional modules as well as an editor for biochemical Petri nets. The analysis techniques allow for network decomposition into functional modules, for example t-invariants (elementary modes), maximal common transition sets, minimal cut sets and t-clusters. The graphical user interface provides various functionalities to construct and modify networks as well as to visualize the results of the analysis. AVAILABILITY AND IMPLEMENTATION: MonaLisa is licensed under the Artistic License 2.0. It is freely available at http://www.bioinformatik.uni-frankfurt.de/software.html. MonaLisa requires at least Java 6 and runs under Linux, Microsoft Windows and Mac OS.

SUMMARY: Small RNA deep sequencing is widely used to characterize non-coding RNAs (ncRNAs) differentially expressed between two conditions, e.g. healthy and diseased individuals and to reveal insights into molecular mechanisms underlying condition-specific phenotypic traits. The ncRNAome is composed of a multitude of RNAs, such as transfer RNA, small nucleolar RNA and microRNA (miRNA), to name few. Here we present omiRas, a Web server for the annotation, comparison and visualization of interaction networks of ncRNAs derived from next-generation sequencing experiments of two different conditions. The Web tool allows the user to submit raw sequencing data and results are presented as: (i) static annotation results including length distribution, mapping statistics, alignments and quantification tables for each library as well as lists of differentially expressed ncRNAs between conditions and (ii) an interactive network visualization of user-selected miRNAs and their target genes based on the combination of several miRNA-mRNA interaction databases. AVAILABILITY AND IMPLEMENTATION: The omiRas Web server is implemented in Python, PostgreSQL, R and can be accessed at: http://tools.genxpro.net/omiras/.

We describe the establishment of bioinformatics in Germany and give an overview of current bioinformatics education in this country, from the perspective of the practitioner. The aim of this study is to demonstrate development of a strong bioinformatics education at German universities and research institutes during the last years. Beginning with a definition of the multi-disciplinary field bioinformatics, we give a survey of government initiatives in Germany in support of this field, which resulted in a wide spectrum of courses. To the best of our knowledge, we compile all ongoing courses at universities and research institutes. Five case studies featuring university courses with different educational focus illustrate the variety of efforts. In this context we also discuss the main components of German bioinformatics curricula. These components can be considered as the basic knowledge of German bioinformaticians. We conclude by giving perspectives for further development of bioinformatics education.

BACKGROUND: Structural analysis of biochemical networks is a growing field in bioinformatics and systems biology. The availability of an increasing amount of biological data from molecular biological networks promises a deeper understanding but confronts researchers with the problem of combinatorial explosion. The amount of qualitative network data is growing much faster than the amount of quantitative data, such as enzyme kinetics. In many cases it is even impossible to measure quantitative data because of limitations of experimental methods, or for ethical reasons. Thus, a huge amount of qualitative data, such as interaction data, is available, but it was not sufficiently used for modeling purposes, until now. New approaches have been developed, but the complexity of data often limits the application of many of the methods. Biochemical Petri nets make it possible to explore static and dynamic qualitative system properties. One Petri net approach is model validation based on the computation of the system's invariant properties, focusing on t-invariants. T-invariants correspond to subnetworks, which describe the basic system behavior.With increasing system complexity, the basic behavior can only be expressed by a huge number of t-invariants. According to our validation criteria for biochemical Petri nets, the necessary verification of the biological meaning, by interpreting each subnetwork (t-invariant) manually, is not possible anymore. Thus, an automated, biologically meaningful classification would be helpful in analyzing t-invariants, and supporting the understanding of the basic behavior of the considered biological system. METHODS: Here, we introduce a new approach to automatically classify t-invariants to cope with network complexity. We apply clustering techniques such as UPGMA, Complete Linkage, Single Linkage, and Neighbor Joining in combination with different distance measures to get biologically meaningful clusters (t-clusters), which can be interpreted as modules. To find the optimal number of t-clusters to consider for interpretation, the cluster validity measure, Silhouette Width, is applied. RESULTS: We considered two different case studies as examples: a small signal transduction pathway (pheromone response pathway in Saccharomyces cerevisiae) and a medium-sized gene regulatory network (gene regulation of Duchenne muscular dystrophy). We automatically classified the t-invariants into functionally distinct t-clusters, which could be interpreted biologically as functional modules in the network. We found differences in the suitability of the various distance measures as well as the clustering methods. In terms of a biologically meaningful classification of t-invariants, the best results are obtained using the Tanimoto distance measure. Considering clustering methods, the obtained results suggest that UPGMA and Complete Linkage are suitable for clustering t-invariants with respect to the biological interpretability. CONCLUSION: We propose a new approach for the biological classification of Petri net t-invariants based on cluster analysis. Due to the biologically meaningful data reduction and structuring of network processes, large sets of t-invariants can be evaluated, allowing for model validation of qualitative biochemical Petri nets. This approach can also be applied to elementary mode analysis.

BACKGROUND: Signal transduction pathways are usually modelled using classical quantitative methods, which are based on ordinary differential equations (ODEs). However, some difficulties are inherent in this approach. On the one hand, the kinetic parameters involved are often unknown and have to be estimated. With increasing size and complexity of signal transduction pathways, the estimation of missing kinetic data is not possible. On the other hand, ODEs based models do not support any explicit insights into possible (signal-) flows within the network. Moreover, a huge amount of qualitative data is available due to high-throughput techniques. In order to get information on the systems behaviour, qualitative analysis techniques have been developed. Applications of the known qualitative analysis methods concern mainly metabolic networks. Petri net theory provides a variety of established analysis techniques, which are also applicable to signal transduction models. In this context special properties have to be considered and new dedicated techniques have to be designed. METHODS: We apply Petri net theory to model and analyse signal transduction pathways first qualitatively before continuing with quantitative analyses. This paper demonstrates how to build systematically a discrete model, which reflects provably the qualitative biological behaviour without any knowledge of kinetic parameters. The mating pheromone response pathway in Saccharomyces cerevisiae serves as case study. RESULTS: We propose an approach for model validation of signal transduction pathways based on the network structure only. For this purpose, we introduce the new notion of feasible t-invariants, which represent minimal self-contained subnets being active under a given input situation. Each of these subnets stands for a signal flow in the system. We define maximal common transition sets (MCT-sets), which can be used for t-invariant examination and net decomposition into smallest biologically meaningful functional units. CONCLUSION: The paper demonstrates how Petri net analysis techniques can promote a deeper understanding of signal transduction pathways. The new concepts of feasible t-invariants and MCT-sets have been proven to be useful for model validation and the interpretation of the biological system behaviour. Whereas MCT-sets provide a decomposition of the net into disjunctive subnets, feasible t-invariants describe subnets, which generally overlap. This work contributes to qualitative modelling and to the analysis of large biological networks by their fully automatic decomposition into biologically meaningful modules.

Abstract Motivation: Because of the complexity of metabolic networks and their regulation, formal modelling is a useful method to improve the understanding of these systems. An essential step in network modelling is to validate the network model. Petri net theory provides algorithms and methods, which can be applied directly to metabolic network modelling and analysis in order to validate the model. The metabolism between sucrose and starch in the potato tuber is of great research interest. Even if the metabolism is one of the best studied in sink organs, it is not yet fully understood. Results: We provide an approach for model validation of metabolic networks using Petri net theory, which we demonstrate for the sucrose breakdown pathway in the potato tuber. We start with hierarchical modelling of the metabolic network as a Petri net and continue with the analysis of qualitative properties of the network. The results characterize the net structure and give insights into the complex net behaviour. Availability: Free availability of the Petri net editor PED, the animator PedVisor via http://www-dssz.informatik.tu-cottbus.de/~wwwdssz, and the analysis tool Integrated Net Analyser (INA) via http://www.informatik.hu-berlin.de/~starke/ina.html Contact: [email protected]

BACKGROUND: Structural and functional research often requires the computation of sets of protein structures based on certain properties of the proteins, such as sequence features, fold classification, or functional annotation. Compiling such sets using current web resources is tedious because the necessary data are spread over many different databases. To facilitate this task, we have created COLUMBA, an integrated database of annotations of protein structures. DESCRIPTION: COLUMBA currently integrates twelve different databases, including PDB, KEGG, Swiss-Prot, CATH, SCOP, the Gene Ontology, and ENZYME. The database can be searched using either keyword search or data source-specific web forms. Users can thus quickly select and download PDB entries that, for instance, participate in a particular pathway, are classified as containing a certain CATH architecture, are annotated as having a certain molecular function in the Gene Ontology, and whose structures have a resolution under a defined threshold. The results of queries are provided in both machine-readable extensible markup language and human-readable format. The structures themselves can be viewed interactively on the web. CONCLUSION: The COLUMBA database facilitates the creation of protein structure data sets for many structure-based studies. It allows to combine queries on a number of structure-related databases not covered by other projects at present. Thus, information on both many and few protein structures can be used efficiently. The web interface for COLUMBA is available at http://www.columba-db.de.

Protein Topology Graph Library (PTGL) is a database application for the representation and retrieval of protein topologies. Protein topologies are based on a graph-theoretical protein model at secondary structure level. Different views on protein topology are given by four linear notations for their characterization. Protein topologies can be derived at different description levels considering alpha- and beta-structures. The on-line search tool is based on an object-relational database and provides a query browser for data interrogation by string patterns, keyword queries and sequence similarity. Protein topologies are represented both as schematic diagrams and as three-dimensional images.

Abstract Motivation: Reconstructing and analyzing the metabolic map of microorganisms is an important challenge in bioinformatics. Pathway analysis of large metabolic networks meets with the problem of combinatorial explosion of pathways. Therefore, appropriate algorithms for an automated decomposition of these networks into smaller subsystems are needed. Results: A decomposition algorithm for metabolic networks based on the local connectivity of metabolites is presented. Interrelations of this algorithm with alternative methods proposed in the literature and the theory of small world networks are discussed. The applicability of our method is illustrated by an analysis of the metabolism of Mycoplasma pneumoniae , which is an organism of considerable medical interest. The decomposition gives rise to 19 subnetworks. Three of these are here discussed in biochemical terms: arginine degradation, the tetrahydrofolate system, and nucleotide metabolism. The interrelations of pathway analysis of biochemical networks with Petri net theory are outlined. Availability: Metatoolis available from ftp://mudshark.brookes.ac.uk/pub/software/ibmpc or http://www.bioinf.mdc-berlin.de/metabolic/. The program Separatorfor decomposing metabolic networks is available from http://www.bioinf.mdc-berlin.de/metabolic/. Supplementary information: http://www.bioinf.mdc-berlin.de/metabolic/metatool/http://www.bork.embl-heidelberg.de/Annot/MP/ (re-annotation of M. pneumoniae genome) Contact: [email protected]; [email protected]; [email protected]; [email protected]