Petri nets have recently become widely accepted as a description method for biological pathways by researchers in computer science as well as those in biology. This paper gives an overview of Petri net formalisms to describe biological pathways and discusses their use in modelings and simulations for the systematic understandings of biological pathways. After reviewing the use of various types of Petri nets for the biological pathway modelings, we showed the examples that analyze fundamental properties of biological pathways using T-invariant, P-invariant, siphon, and trap. Applications of hybrid Petri nets for producing new biological hypotheses through simulations are also illustrated.

This paper reviews design aspects of computational discovery systems through the analysis of some successful discovery systems. We first review the concept of viewscope/view on data which provides an interpretation of raw data in a specific domain. Then we relate this concept to the KDD process described by Fayyad et al. (1996) and the developer's role in computational discovery due to Langley (1998). We emphasize that integration of human experts and discovery systems is a crucial problem in designing discovery systems and claim together with the analysis of discovery systems that the concept of viewscope/view gives a way for approaching this problem.

Let C{c1, , cm} be a family of subsets of a finite set S{1, , n}, a subset S of S is a co-hitting set if S contains no element of C as a subset. By using an O((log n)2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAN in time O(αβ(log(nm))2) using O(n2 m) processors, where αmax{|cii1, , n} and βmax{|djj1, , n} with dj{ci|jci}. This implies that if αβO((log(nm))k) then the problem is solvable in NC.

Through many researches on modeling and analyzing biological pathways, Petri net has recognized as a promising method for representing biological pathways. Recently, Matsuno et al. (2003) introduced hybrid functional Petri net (HFPN) for giving more intuitive and natural biological pathway modeling method than existing Petri nets. They also developed Genomic Object Net (GON) which employs the HFPN as a basic architecture. Many kinds of biological pathways have been modeled with the HFPN and simulated by the GON. This paper gives a new HFPN model of "cell cycle of fission yeast" with giving six basic HFPN components of typical biological reactions, and demonstrating the method how biological pathways can be modeled with these HFPN components. Simulation results by GON suggest a new hypothesis which will help biologist for performing further experiments.

The elementary formal system (EFS, for short) is a kind of logic program which directly manipulates character strings. This paper outlines in brief the authors' studies on algorithmic learning theory developed in the framework of EFS's. We define two important classes of EFS's and a new hierarchy of various language classes. Then we discuss EFS's as logic programs. We show that EFS's form a good framework for inductive inference of languages by presenting model inference system for EFS's in Shapiro's sense. Using the framework we also show that inductive inference from positive data and PAC-learning are both much more powerful than they have been believed. We illustrate an application of our theoretical results to Molecular Biology.

This paper discusses some problems in Molecular Biology for which learning paradigms are strongly desired. We also present a framework of knowledge discovery by PAC-learning paradigm together with its theory and practice developed in our work for discovery from amino acid sequences.

For two finite disjoint sets P and Q of strings over an alphabet Σ, an alphabet indexing for P, Q by an indexing alphabet Γ with |Γ||Σ| is a mapping :ΣΓ satisfying (P)(Q), where :Σ*Γ* is the homomorphism derived from . We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.

We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2nlogm) time with O(nm) processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in O(log2n) time with O(nm) processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.

This paper proposes a method to incorporate the concept of time for the inclusion of dynamics of signaling pathway in a Petri net model, i.e., to use timed Petri nets. Incorporation of delay times into a Petri net model makes it possible to conduct quantitative evaluation on a target signaling pathway. However, experimental data describing detailed reactions are not available in most cases. An algorithm given in this paper determines delay times of a timed Petri net only from the structural information of it. The suitability of this algorithm has been confirmed by the results of an application to the IL-1 signaling pathway.