Despite the unprecedented growth in our understanding of cell biology, it still remains challenging to connect it to experimental data obtained with cells and tissues' physiopathological status under precise circumstances. This knowledge gap often results in difficulties in designing validation experiments, which are usually labor-intensive, expensive to perform, and hard to interpret. Here we propose PHENSIM, a computational tool using a systems biology approach to simulate how cell phenotypes are affected by the activation/inhibition of one or multiple biomolecules, and it does so by exploiting signaling pathways. Our tool's applications include predicting the outcome of drug administration, knockdown experiments, gene transduction, and exposure to exosomal cargo. Importantly, PHENSIM enables the user to make inferences on well-defined cell lines and includes pathway maps from three different model organisms. To assess our approach's reliability, we built a benchmark from transcriptomics data gathered from NCBI GEO and performed four case studies on known biological experiments. Our results show high prediction accuracy, thus highlighting the capabilities of this methodology. PHENSIM standalone Java application is available at https://github.com/alaimos/phensim, along with all data and source codes for benchmarking. A web-based user interface is accessible at https://phensim.tech/.

Mastering the dynamics of social influence requires separating, in a database of information propagation traces, the genuine causal processes from temporal correlation, i.e., homophily and other spurious causes. However, most studies to characterize social influence, and, in general, most data-science analyses focus on correlations, statistical independence, or conditional independence. Only recently, there has been a resurgence of interest in "causal data science,'' e.g., grounded on causality theories. In this paper we adopt a principled causal approach to the analysis of social influence from information-propagation data, rooted in the theory of probabilistic causation. Our approach consists of two phases. In the first one, in order to avoid the pitfalls of misinterpreting causation when the data spans a mixture of several subtypes ("Simpson's paradox''), we partition the set of propagation traces into groups, in such a way that each group is as less contradictory as possible in terms of the hierarchical structure of information propagation. To achieve this goal, we borrow the notion of "agony'' and define the Agony-bounded Partitioning problem, which we prove being hard, and for which we develop two efficient algorithms with approximation guarantees. In the second phase, for each group from the first phase, we apply a constrained MLE approach to ultimately learn a minimal causal topology. Experiments on synthetic data show that our method is able to retrieve the genuine causal arcs w.r.t. a ground-truth generative model. Experiments on real data show that, by focusing only on the extracted causal structures instead of the whole social graph, the effectiveness of predicting influence spread is significantly improved.

Malware detection and classification is critical for the security of IT infrastructure. Legacy detection of malware has been highly reliant on static signatures, so malware authors have evolved code polymorphic techniques to counteract these tools, thus rendering static malware detectors ineffective. While malware writers may easily use code rewriting techniques to scramble binary images; malware processes at runtime still must conduct a sequence of operational steps to achieve its design goal, indicating an approach based on behavioral analysis where the captured invariants form a new type of forensic fingerprint. Moreover these operational steps are constrained to occur within the computers' or mobile devices' abstract system interface - a finite basis of activities that submit to effective monitoring with a variety of tools. In this work, we propose a formalism for expressing these behaviors, learning them and analyzing them to form automated malware analysis tools. Thus motivated by a need to detect and classify malware, we root its foundation in formal verification, as well as methodology from statistical and machine learning. Specifically using trace data from malware we leverage formal verification methods (such as probabilistic model checking) to construct classifiers and evaluate their efficacy in supervised learning and cross-fold validation experiments. The results inform how a fully automated reasoning mechanism may be applied to unknown software by posing its system trace as a query to various classifiers as hypothesis testing, the outputs informing belief of membership. Finally, we demonstrate the method and results on real malware data.

In this paper, we present a case study of visual analytics of a Malware Distribution Network (MDN), a connected set of maliciously compromised domains used to disseminate malicious software to victimize computers and users. We formally define the graph of an MDN to visualize top-level-domain (TLD) data collected from Google Safe Browsing reports in a temporal manner characterizing the topological structure. From the collected data, we were able to identify and label a TLD's role in malware distribution. The visual analytics provided insights on the topological structure of MDNs over time including highly connected and persistent TLDs and subnetworks.

MOTIVATION: We introduce TRanslational ONCOlogy (TRONCO), an open-source R package that implements the state-of-the-art algorithms for the inference of cancer progression models from (epi)genomic mutational profiles. TRONCO can be used to extract population-level models describing the trends of accumulation of alterations in a cohort of cross-sectional samples, e.g. retrieved from publicly available databases, and individual-level models that reveal the clonal evolutionary history in single cancer patients, when multiple samples, e.g. multiple biopsies or single-cell sequencing data, are available. The resulting models can provide key hints for uncovering the evolutionary trajectories of cancer, especially for precision medicine or personalized therapy. AVAILABILITY AND IMPLEMENTATION: TRONCO is released under the GPL license, is hosted at http://bimib.disco.unimib.it/ (Software section) and archived also at bioconductor.org. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

UNLABELLED: We devise a novel inference algorithm to effectively solve the cancer progression model reconstruction problem. Our empirical analysis of the accuracy and convergence rate of our algorithm, CAncer PRogression Inference (CAPRI), shows that it outperforms the state-of-the-art algorithms addressing similar problems. MOTIVATION: Several cancer-related genomic data have become available (e.g. The Cancer Genome Atlas, TCGA) typically involving hundreds of patients. At present, most of these data are aggregated in a cross-sectional fashion providing all measurements at the time of diagnosis. Our goal is to infer cancer 'progression' models from such data. These models are represented as directed acyclic graphs (DAGs) of collections of 'selectivity' relations, where a mutation in a gene A 'selects' for a later mutation in a gene B. Gaining insight into the structure of such progressions has the potential to improve both the stratification of patients and personalized therapy choices. RESULTS: The CAPRI algorithm relies on a scoring method based on a probabilistic theory developed by Suppes, coupled with bootstrap and maximum likelihood inference. The resulting algorithm is efficient, achieves high accuracy and has good complexity, also, in terms of convergence properties. CAPRI performs especially well in the presence of noise in the data, and with limited sample sizes. Moreover CAPRI, in contrast to other approaches, robustly reconstructs different types of confluent trajectories despite irregularities in the data. We also report on an ongoing investigation using CAPRI to study atypical Chronic Myeloid Leukemia, in which we uncovered non trivial selectivity relations and exclusivity patterns among key genomic events. AVAILABILITY AND IMPLEMENTATION: CAPRI is part of the TRanslational ONCOlogy R package and is freely available on the web at: http://bimib.disco.unimib.it/index.php/Tronco CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this paper, we study Copy Number Variation (CNV) data. The underlying process generating CNV segments is generally assumed to be memory-less, giving rise to an exponential distribution of segment lengths. In this paper, we provide evidence from cancer patient data, which suggests that this generative model is too simplistic, and that segment lengths follow a power-law distribution instead. We conjecture a simple preferential attachment generative model that provides the basis for the observed power-law distribution. We then show how an existing statistical method for detecting cancer driver genes can be improved by incorporating the power-law distribution in the null model.

There are many examples of problems in pattern analysis for which it is often possible to obtain systematic characterizations, if in addition a small number of useful features or parameters of the image are known a priori or can be estimated reasonably well. Often the relevant features of a particular pattern analysis problem are easy to enumerate, as when statistical structures of the patterns are well understood from the knowledge of the domain. We study a problem from molecular image analysis, where such a domain-dependent understanding may be lacking to some degree and the features must be inferred via machine-learning techniques. In this paper, we propose a rigorous, fully-automated technique for this problem. We are motivated by an application of atomic force microscopy (AFM) image processing needed to solve a central problem in molecular biology, aimed at obtaining the complete transcription profile of a single cell, a snapshot that shows which genes are being expressed and to what degree. Reed et al (Single molecule transcription profiling with AFM, Nanotechnology, 18:4, 2007) showed the transcription profiling problem reduces to making high-precision measurements of biomolecule backbone lengths, correct to within 20-25 bp (6-7.5 nm). Here we present an image processing and length estimation pipeline using AFM that comes close to achieving these measurement tolerances. In particular, we develop a biased length estimator on trained coefficients of a simple linear regression model, biweighted by a Beaton-Tukey function, whose feature universe is constrained by James-Stein shrinkage to avoid overfitting. In terms of extensibility and addressing the model selection problem, this formulation subsumes the models we studied.

MOTIVATION: Currently, re-sequencing approaches use multiple modules serially to interpret raw sequencing data from next-generation sequencing platforms, while remaining oblivious to the genomic information until the final alignment step. Such approaches fail to exploit the full information from both raw sequencing data and the reference genome that can yield better quality sequence reads, SNP-calls, variant detection, as well as an alignment at the best possible location in the reference genome. Thus, there is a need for novel reference-guided bioinformatics algorithms for interpreting analog signals representing sequences of the bases ({A, C, G, T}), while simultaneously aligning possible sequence reads to a source reference genome whenever available. RESULTS: Here, we propose a new base-calling algorithm, TotalReCaller, to achieve improved performance. A linear error model for the raw intensity data and Burrows-Wheeler transform (BWT) based alignment are combined utilizing a Bayesian score function, which is then globally optimized over all possible genomic locations using an efficient branch-and-bound approach. The algorithm has been implemented in soft- and hardware [field-programmable gate array (FPGA)] to achieve real-time performance. Empirical results on real high-throughput Illumina data were used to evaluate TotalReCaller's performance relative to its peers-Bustard, BayesCall, Ibis and Rolexa-based on several criteria, particularly those important in clinical and scientific applications. Namely, it was evaluated for (i) its base-calling speed and throughput, (ii) its read accuracy and (iii) its specificity and sensitivity in variant calling. AVAILABILITY: A software implementation of TotalReCaller as well as additional information, is available at: http://bioinformatics.nyu.edu/wordpress/projects/totalrecaller/ CONTACT: [email protected].

MOTIVATION: Mired by its connection to a well-known -complete combinatorial optimization problem-namely, the Shortest Common Superstring Problem (SCSP)-historically, the whole-genome sequence assembly (WGSA) problem has been assumed to be amenable only to greedy and heuristic methods. By placing efficiency as their first priority, these methods opted to rely only on local searches, and are thus inherently approximate, ambiguous or error prone, especially, for genomes with complex structures. Furthermore, since choice of the best heuristics depended critically on the properties of (e.g. errors in) the input data and the available long range information, these approaches hindered designing an error free WGSA pipeline. RESULTS: We dispense with the idea of limiting the solutions to just the approximated ones, and instead favor an approach that could potentially lead to an exhaustive (exponential-time) search of all possible layouts. Its computational complexity thus must be tamed through a constrained search (Branch-and-Bound) and quick identification and pruning of implausible overlays. For his purpose, such a method necessarily relies on a set of score functions (oracles) that can combine different structural properties (e.g. transitivity, coverage, physical maps, etc.). We give a detailed description of this novel assembly framework, referred to as Scoring-and-Unfolding Trimmed Tree Assembler (SUTTA), and present experimental results on several bacterial genomes using next-generation sequencing technology data. We also report experimental evidence that the assembly quality strongly depends on the choice of the minimum overlap parameter k. AVAILABILITY AND IMPLEMENTATION: SUTTA's binaries are freely available to non-profit institutions for research and educational purposes at http://www.bioinformatics.nyu.edu.

Accurate computational prediction of protein functions increasingly relies on network-inspired models for the protein function transfer. This task can become challenging for proteins isolated in their own network or those with poor or uncharacterized neighborhoods. Here, we present a novel probabilistic chain-graph-based approach for predicting protein functions that builds on connecting networks of two (or more) different species by links of high interspecies sequence homology. In this way, proteins are able to "exchange" functional information with their neighbors-homologs from a different species. The knowledge of interspecies relationships, such as the sequence homology, can become crucial in cases of limited information from other sources of data, including the protein-protein interactions or cellular locations of proteins. We further enhance our model to account for the Gene Ontology dependencies by linking multiple but related functional ontology categories within and across multiple species. The resulting networks are of significantly higher complexity than most traditional protein network models. We comprehensively benchmark our method by applying it to two largest protein networks, the Yeast and the Fly. The joint Fly-Yeast network provides substantial improvements in precision, accuracy, and false positive rate over networks that consider either of the sources in isolation. At the same time, the new model retains the computational efficiency similar to that of the simpler networks.

This paper addresses the protein classification problem, andexplores how its accuracy can be improved by using information fromtime-course gene expression data. The methods are tested on datafrom the most deadly species of the parasite responsible for malariainfections, Plasmodium falciparum. Even though avaccination for Malaria infections has been under intense study formany years, more than half of Plasmodiumproteins still remain uncharacterized and therefore are exemptedfrom clinical trials. The task is further complicated by arapid life cycle of the parasite, thus making precisetargeting of the appropriate proteins for vaccination a technicalchallenge. We propose to integrate protein-protein interactions (PPIs),sequence similarity, metabolic pathway, andgene expression, to produce a suitable set of predicted proteinfunctions for P.falciparum. Further,we treat gene expression data withrespect to various changes that occur during the five phases of theintraerythrocytic developmental cycle (IDC) (as determinedby our segmentation algorithm) ofP.falciparum and show that this analysis yields asignificantly improved protein function prediction, e.g., whencompared to analysis based on Pearson correlation coefficients seenin the data. The algorithm is able to assign ``meaningful''functions to 628 out of 1439 previously unannotated proteins, whichare first-choice candidates for experimental vaccine research.

We propose a novel approach for predicting protein functions of an organism by coupling sequence homology and PPI data between two (or more) species with multi-functional Gene Ontology information into a single computational model. Instead of using a network of one organism in isolation, we join networks of different species by inter-species sequence homology links of sufficient similarity. As a consequence, the knowledge of a protein's function is acquired not only from one species' network alone, but also through homologous links to the networks of different species. We apply our method to two largest protein networks, Yeast (Saccharomyces cerevisiae) and Fly (Drosophila melanogaster). Our joint Fly-Yeast network displays statistically significant improvements in precision, accuracy, and false positive rate over networks that consider either of the sources in isolation, while retaining the computational efficiency of the simpler models.

Determining candidates' views on important issues is critical in deciding whom to support and vote for; but finding their statements and votes on an issue can be laborious. In this paper we present PSST, (Political Statement and Support Tracker), a search engine to facilitate analysis of political statements and votes over time. We show that prior tools for text analysis can be combined with minimal manual processing to provide a first step in the full automation of this process.

UNLABELLED: We present a fast, versatile and adaptive-multiscale algorithm for analyzing a wide-variety of DNA microarray data. Its primary application is in normalization of array data as well as subsequent identification of 'enriched targets', e.g. differentially expressed genes in expression profiling arrays and enriched sites in ChIP-on-chip experimental data. We show how to accommodate the unique characteristics of ChIP-on-chip data, where the set of 'enriched targets' is large, asymmetric and whose proportion to the whole data varies locally. SUPPLEMENTARY INFORMATION: Supplementary figures, related preprint, free software as well as our raw DNA microarray data with PCR validations are available at http://www.math.umn.edu/~lerman/supp/bioinfo06 as well as Bioinformatics online.

ajor advances in genome science and molecular technologies provide new opportunities at the interface between basic biological research and medical practice.The unprecedented completeness, accuracy, and volume of genomic and molecular data necessitate a new kind of computational biology for translational research.Key challenges are standardization of data capture and communication, organization of easily accessible repositories, and algorithms for integrated analysis based on heterogeneous sources of information.Also required are new ways of using complementary clinical and biological data, such as computational methods for predicting disease phenotype from molecular and genetic profiling.New combined experimental and computational methods hold the promise of more accurate diagnosis and prognosis as well as more effective prevention and therapy.

We present a noise sensitivity analysis of the differential optimal structure from motion problem. Given optical flow measurements for a set of feature points, we formulate a least squares cost function based on a more reasonable additive isotropic model of measurement noise, normalized by depth, that also leads to statistically consistent estimates of the shape and motion parameters. A cyclic coordinate descent algorithm is developed, and its performance examined through experiments.

We present an unusual algorithm involving classification trees---CARTwheels---where two trees are grown in opposite directions so that they are joined at their leaves. This approach finds application in a new data mining task we formulate, called redescription mining. A redescription is a shift-of-vocabulary, or a different way of communicating information about a given subset of data; the goal of redescription mining is to find subsets of data that afford multiple descriptions. We highlight the importance of this problem in domains such as bioinformatics, which exhibit an underlying richness and diversity of data descriptors (e.g., genes can be studied in a variety of ways). CARTwheels exploits the duality between class partitions and path partitions in an induced classification tree to model and mine redescriptions. It helps integrate multiple forms of characterizing datasets, situates the knowledge gained from one dataset in the context of others, and harnesses high-level abstractions for uncovering cryptic and subtle features of data. Algorithm design decisions, implementation details, and experimental results are presented.

A special case of the dynamic finger conjecture is proved; this special case introduces a number of useful techniques.

Given a set of m molecules, derived from K homologous clones, we wish to partition these molecules into K populations, each giving rise to distinct ordered restriction maps, thus providing simple means for stuclying biological variations.With the emergence of single molecule methods, such as optical mapping, that wn create individual ordered restriction maps reliably and with high throughput, it becomes interesting to study the related algorithmic problems-In particular, we provide a complete computational complezity analysis of the "Kpopulations"problem as well as some simple polynomial heuristics, while ezposing the relations among various error sources that the optical mapping approach may need to cope with.We believe that these results will be of interest to computational biologists in devising better algorithms, to biochemists in understanding the tradeoffs among the error sources andfinally, to biologists in creating reliable protocols for population study.

Current moIecuIar bioIogy techniques were deveIoped primarily for characterization of single genes, not entire genomes, and, as such, are not ideally suited to high resolution analysis of complex traits and the moiecular genetics of very large populations.Despite rapid progress in the human genome project effort, there is little doubt that radicaIIy new conceptual approaches are needed before routine whole genome-based analyses can be undertaken by both basic research and clinical laboratories.Physical mapping of genomes, using restriction endonucleases, has played a major role in the identification and characterizing various loci, for example, by aiding clone contig formation and by characterizing genetic lesions.Restriction maps provide precise genomic distances, unlike ordered sequencebased landmarks such as Sequence Tagged Sites (ST%), that are essential for optimizing the efficiency of sequencing efforts, and for determining the spatial relationships of specific loci.When compared to tedious hybridization-based fingerprinting approaches, ordered restriction maps offer relatively unambiguous clone characterization that is useful in contig formation, establishment of minimal tiling paths for sequencing, and preliminary characterization of sequence lesions.In addition, such maps provide a useful scaffold for sequence assembly, often critical in the final sequence finishing stage.Despite the broad applications of restriction maps, the associated techniques for their generation have changed little over the last ten years, primarily because they still utilize electrophoretic analysis.To help overcome these shortcomings, our laboratory developed the first practical non-electrophoretic genomic mapping approach, Optical Mapping, to meet this need.Optical Mapping is a single molecule methodology for the rapid production of ordered restriction

There are many large system problems that are hard to model exactly or in a computationally tractable fashion. Examples include the mapping of human DNA, speech recognition, and automated learning in computer chess. Traditional artificial intelligence solution techniques for such problems rely on a combination of custom encoding of expert knowledge and heuristic search. They take much time to hand craft and then often are unable to take advantage of faster computers as they become available. In this context, the authors explore the advantage of using statistical search techniques in which the knowledge is encoded in some form of statistical model whose parameters are automatically adjusted or trained with domain data. The benefits are faster development times, greater solution accuracy (compared to hand crafted solutions) and the ability to allow the problem size and desired solution accuracy to be scaled up with computational resources. They apply this approach to certain critical computational problems in mapping the human genome. They use a Bayesian model to provide the best solution accuracy as a function of the number of parameters. Heuristic search techniques derived from artificial intelligence are used to search the model space in an efficient manner in the average case.

Describes the Complex Adaptive Financial Environment (CAFE/spl acute/), a simulator for complex adaptive systems implemented in Java. CAFE/spl acute/'s object-oriented design makes it suitable for many types of simulation. We give an example of a market simulation where food is traded for gold and explore the effects of adding several kinds of speculators to the system. This paper describes the software structure and design of CAFE/spl acute/, building upon the object-oriented and distributed features of the Java programming language. Although the primary application for this system is in the computational finance area, we envision a much more general usage.

We address the problem of the synthesis of controller programs for a variety of robotics and manufacturing tasks. The problem we choose for the test and illustrative purposes is the standard "walking machine problem", a representative instance of a real hybrid problem with both logical/discrete and continuous properties and strong mutual influence without any reasonable separation. We aim to produce a "compiler technology" for this class of problems in a manner analogous to the development of the so-called "silicon compilers" for the VLSI technology. To cope with the difficulties inherent to the problem, we resort to a novel approach that combines many key ideas from a variety of disciplines, namely discrete event supervisory systems, Petri nets approaches and temporal logic.

Considers the problem of grasping an unknown polygonal flat object using a parallel jaw gripper. The authors propose to equip a standard gripper with several light-beam sensors (close to each jaw) and describe a reactive grasping algorithm. This is done by probing the object to locate a good grasp position, and then grasping, without moving the object significantly. The goal is to do as little motion as possible to find a grasp. This algorithm can be viewed in, a competitive framework, where the authors' algorithm is competing against any algorithm which already knows the object.>

The preemptive scheduling of sporadic tasks on a uniprocessor is considered. A task may arrive at any time, and is characterized by a value that reflects its importance, an execution time that is the amount of processor time needed to completely execute the task, and a deadline by which the task is to complete execution. The goal is to maximize the sum of the values of the completed tasks. An online scheduling algorithm that achieves optimal performance when the system is underloaded and provides a nontrivial performance guarantee when the system is overloaded is designed. The algorithm is implemented using simple data structures to run at a cost of O(log n) time per task, where n bounds the number of tasks in the system at any instant. Upper bounds on the best performance guarantee obtainable by an online algorithm in a variety of settings are derived.>

With an increasing interest in manufacturing towards computer-assisted production in small batch sizes, researchers have begun to focus on the design, analysis and planning algorithms for workholding (also called fixturing), calibration and tool-path generation. The author focuses on the problem of workholding and reviews how various qualitative and quantative approaches of grasping theory can be applied to this problem mutatis mutandis. However, the problems in workholding differ from robot-hand grasping problems in two fundamental ways; the accuracy and ambient force (resulting from fluctuating cutting loads) requirements are rather stringent, and the available fixtures are geometrically more specialized as compared to robot-hands. These differences lead to further interesting questions.>

The authors study the performance of online algorithms in environments where no value is obtained for the partial execution of a request. They prove that no online scheduling algorithm can have a competitive factor greater than 0.25 times the optimal. They further refine this bound by considering the effect of the loading factor. Other models of task systems (for example, tasks systems consisting of many types of task requests), are considered. Similar upper bounds on the competitive factor that can be made by online scheduling algorithms in these environments are proved. It is shown that the performance bound of 0.25 is tight by means of a simple online uniprocessor scheduling algorithm has a competitive factor of 1/4. The authors extend the discussion to systems with dual processors. They show that the upper bound for the dual-processor online scheduling problem is 1/2 if all tasks have the same value density. This bound is tight if the tasks all also have zero laxity.>

We describe NC algorithms for doing exact arithmetic with real algebraic numbers in the sign-coded representation introduced by Coste and Roy [CoR 1988]. We present polynomial sized circuits of depth Ο(log3 N) for the monadic operations -α, 1/α, as well as α + r, α · r, and sgn(α - r), where r is rational and α is real algebraic. We also present polynomial sized circuits of depth Ο(log7 N) for the dyadic operations α+β, α·β, and sgn(α - β), where α and β are both real algebraic. Our algorithms employ a strengthened form of the NC polynomial-consistency algorithm of Ben-Or, Kozen, and Reif [BKR 1986].

We prove the following quantitative form of a classical theorem of Steinitz: Let m be sufficiently large.If the convex huh of a subset S of Euclidean d-space contains a unit bMl then there is a subset of S with at most m points whose convex huh contains a ball with the same center and having residual radius 1 -3dThe case m = 2d was first considered by B~r£ny, Katchalski and Pach (1982).We also show an upper bound on the achievable residual radius of This quantitative Steinitz's theorem has applications in computing the efficiency of closure grasps by an m-fingered robot hand.The theorem also raises some new problems in eom-putationM geometry; we present some efficient algorithms for these problems, especially in the plane.

An overview is presented of research done in the area of dextrous manipulation. The main issue has been how to control mechanical hands so that they can perform manipulation task with the same dexterity and sensitivity as the human hands. To achieve sophisticated algorithms for grasping, compliance control, and manipulation, the nature of the contact wrenches, twists, and compliance of the fingers have to be well understood. Here emphasis is on the area of dextrous manipulation encompassed by static grasping. The two main approaches to the problems of grasping reviewed are those motivated by a study of human hands and those motivated by the physical and mechanical properties of grasps such as contact types, number of fingers required to achieve grasp, equilibrium, stability and compliance.>

Verifying the correctness of sequential circuits has been an important problem for a long time. But lack of any formal and efficient method of verification has prevented the creation of practical design aids for this purpose. Since all the known techniques of simulation and prototype testing are time consuming and not very reliable, there is an acute need for such tools. In this paper we describe an automatic verification system for sequential circuits in which specifications are expressed in a propositional temporal logic. In contrast to most other mechanical verification systems, our system does not require any user assistance and is quite fast—experimental results show that state machines with several hundred states can be checked for correctness in a matter of seconds!

Path expressions were originally proposed by Campbell and Habermann [1] as a mechanism for process synchronization at the monitor level in software. Not unexpectedly, they also provide a useful notation for specifying the behavior of asynchronous circuits. Motivated by this potential application we investigate how to directly translate path expressions into hardware.

An efficient algorithm for the All-Bidirectional-Edges Problem is presented. The All-Bidirectional-Edges Problem is to find an edge-labelling of an undirected network, G = (V,E), with a source and a sink, such that an edge [u,v] /spl epsi/ E is labelled (u,v) or (v,u) (or both) depending on the existence of a (simple) path from the source to sink that visits the vertices u and v, in the order u,v or v,u, respectively. The algorithm presented works by partitioning the graph into a set of bridges and analyzing them recursively. The time complexity of the algorithm is shown to be O(\E\ . \V\). The problem arises naturally in the context of the simulation of in MOS transistor network, in which a transistor may operate as a unilateral or a bilateral device, depending on the voltages at its source and drain nodes. For efficient simulation, it is required to detect the set of transistors that may operate as bilateral devices. Also, this algorithm can be used in order to detect all the sneak paths in a network of pass transistor.