Search

The page rank of a webpage is a numerical estimate of its authority. In Google΄s PageRank algorithm the ranking is derived as the invariant probability distribution of a Markov chain random surfer model. The crucial point in this algorithm is the addition of a small probability transition for each pair of states to render the transition matrix irreducible and aperiodic. The same idea can be applied to P systems, and the resulting invariant probability distribution characterizes their dynamical behavior, analogous to recurrent states in deterministic dynamical systems. The modification made to the original P system gives rise to a new class of P systems with the property that their computations need to be robust against random mutations. Another application is the pathway identification problem, where a metabolite graph is constructed from information about biochemical reactions available in public databases. The invariant distribution of this graph, properly interpreted as a Markov chain, should allow to search pathways more efficiently than current algorithms. Such automatic pathway calculations can be used to derive appropriate P system models of metabolic processes. [ABSTRACT FROM AUTHOR]

In this paper we present an initial analysis of job arrivals in a production data-intensive Grid and investigate several traffic models to characterize the interarrival time processes. Our analysis focuses on the heavy-tail behavior and autocorrelation structures, and the modeling is carried out at three different levels: Grid, Virtual Organization (VO), and region. A set of m-state Markov modulated Poisson processes (MMPP) is investigated, while Poisson processes and hyperexponential renewal processes are evaluated for comparison studies. We apply the transportation distance metric from dynamical systems theory to further characterize the differences between the data trace and the simulated time series, and estimate errors by bootstrapping. The experimental results show that MMPPs with a certain number of states are successful to a certain extent in simulating the job traffic at different levels, fitting both the interarrival time distribution and the autocorrelation function. However, MMPPs are not able to match the autocorrelations for certain VOs, in which strong deterministic semi-periodic patterns are observed. These patterns are further characterized using different representations. Future work is needed to model both deterministic and stochastic components in order to better capture the correlation structure in the series. [ABSTRACT FROM AUTHOR]

The concept of breakpoint graph, known from the theory of sorting by reversal, has been successfully applied in the theory of gene assembly in ciliates. We further investigate its usage for gene assembly, and show that the graph allows for an efficient characterization of the possible orders of loop recombination operations (one of the three types of molecular operations that accomplish gene assembly) for a given gene during gene assembly. The characterization is based on spanning trees within a graph built upon the connected components in the breakpoint graph. We work in the abstract and more general setting of so-called legal strings. [ABSTRACT FROM AUTHOR]