Equivalence and reduction of expansive tree grammars.

The equivalence of nonterminals of an expansive tree grammar is considered. Algorithms are presented for constructing sets of equivalent nonterminals for an expansive tree grammar, for reducing the grammar, and for determining whether two grammars generate the same language.

Simulation of emission tomography using grid middleware for distributed computing.

SimSET is Monte Carlo simulation software for emission tomography. This paper describes a simple but effective scheme for parallel execution of SimSET using NetSolve, a client-server system for distributed computation. NetSolve (version 1.4.1) is "grid middleware" which enables a user (the client) to run specific computations remotely and simultaneously on a grid of networked computers (the servers). Since the servers do not have to be identical machines, computation may take place in a heterogeneous environment. To take advantage of diversity in machines and their workloads, a client-side scheduler was implemented for the Monte Carlo simulation. The scheduler partitions the total decay events by taking into account the inherent compute-speeds and recent average workloads, i.e., the scheduler assigns more decay events to processors expected to give faster service and fewer decay events to those expected to give slower service. When compute-speeds and sustained workloads are taken into account, the speed-up is essentially linear in the number of equivalent "maximum-service" processors. One modification in the SimSET code (version 2.6.2.3) was made to ensure that the total number of decay events specified by the user is maintained in the distributed simulation. No other modifications in the standard SimSET code were made. Each processor runs complete SimSET code for its assignment of decay events, independently of others running simultaneously. Empirical results are reported for simulation of a clinical-quality lung perfusion study.

Constrained Markov networks for automated analysis of G-banded chromosomes.

Automated analysis of chromosome band patterns using probabilistic Markov networks has been reported in previous work. Band patterns are represented as strings of symbols. Inferred from a set of learning strings, a Markov network is a model of intraband and interband relations in these strings. The inference is entirely data-driven and is accomplished using dynamic programming. This paper presents a new model of chromosome band patterns, the constrained Markov network, which is a special case of its predecessor. Substantial experimental evidence of the superiority of the new model over the old is given in terms of equal results in centromere finding and improved results in classification for the 22 autosomes. Furthermore, a method for simplification of constrained Markov networks is shown to be of considerable importance with respect to computational complexity.

Automatically inferred Markov network models for classification of chromosomal band pattern structures.

A structural pattern recognition approach to the analysis and classification of metaphase chromosome band patterns is presented. An operational method of representing band pattern profiles as sharp edged idealized profiles is outlined. These profiles are nonlinearly scaled to a few, but fixed number of "density" levels. Previous experience has shown that profiles of six levels are appropriate and that the differences between successive bands in these profiles are suitable for classification. String representations, which focuses on the sequences of transitions between local band pattern levels, are derived from such "difference profiles." A method of syntactic analysis of the band transition sequences by dynamic programming for optimal (maximal probability) string-to-network alignments is described. It develops automatic data-driven inference of band pattern models (Markov networks) per class, and uses these models for classification. The method does not use centromere information, but assumes the p-q-orientation of the band pattern profiles to be known a priori. It is experimentally established that the method can build Markov network models, which, when used for classification, show a recognition rate of about 92% on test data. The experiments used 200 samples (chromosome profiles) for each of the 22 autosome chromosome types and are designed to also investigate various classifier design problems. It is found that the use of a priori knowledge of Denver Group assignment only improved classification by 1 or 2%. A scheme for typewise normalization of the class relationship measures prove useful, partly through improvements on average results and partly through a more evenly distributed error pattern. The choice of reference of the p-q-orientation of the band patterns is found to be unimportant, and results of timing of the execution time of the analysis show that recent and efficient implementations can process one cell in less than 1 min on current standard hardware. A measure of divergence between data sets and Markov network models is shown to provide usable estimates of experimental classification performance.