Some applications of an Implicit Duality Theorem to connections of structures of special types including Dirac and reciprocal structures

In this paper, we present some applications of an Implicit Duality Theorem which was originally a folklore result on Ideal Transformers in Electrical Network Theory. We show, among other things, that results on reciprocal networks (due to Tellegen (Proc. Inst. Radio Engrs. 14 (1953) 265), and Dirac Structures (due to van der Schaft (in: J.W. Polderman, H.L. Trentelman (Eds.), From Intelligent Control to Behavioural Systems. University of Groningen Press) follow as a consequence. These results have the form ‘interconnection of structures of a particular kind yields a structure of the same kind’. Also discussed is the question ‘given smaller structures of a given kind and a desired structure of the same kind, can the former be interconnected to yield the latter?’. We also indicate the range of possible generalizations of this result.     

Fast mining of frequent tree structures by hashing and indexing

Hierarchical semistructured data arise frequently in the Web, or in biological information processing applications. Semistructured objects describing the same type of information have similar but not identical structure. Usually they share some common ‘schema’. Finding the common schema of a collection of semistructured objects is a very important task and due to the huge amount of such data encountered, data mining techniques have been employed.In this paper, we study the problem of discovering frequently occurring structures in semistructured objects using the notion of association rules. We identify that discovering the frequent structures in the early phases of the mining procedure is the dominant cost and we provide a fast algorithm addressing this issue. We present experimental results, which demonstrate the superiority of the proposed algorithm and also its efficiency in reducing dramatically the processing cost.     

Entailment for measure based belief structures

We discuss the Dempster–Shafer belief structure on finite universes and note its use for modeling variables that have both probabilistic uncertainty as well as imprecision. We note for these structures the probability that the variable lies in a subset cannot be precisely known but only be known to an interval value. We discuss methods for deducing this uncertainty interval. We next discuss the issue of entailment of belief structures, inferring the validity of additional belief model of a variable from an already established belief model of the variable. We next discuss a more general belief structure were the underling uncertainty rather tha0n being based on a probability distribution is based on a general measure type of uncertainty. We then extend the concept of entailment to the case where the belief structures are these more general measure based belief structures. In order to accomplish this we must extend the idea of containment from classic Dempster–Shafer belief structures to measure based belief structures.     

Configuration structures, event structures and Petri nets

In this paper the correspondence between safe Petri nets and event structures, due to Nielsen, Plotkin and Winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. To this end we propose a more general form of event structure, matching the expressive power of such nets. These new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure.A configuration structure can also be considered logically, as a class of propositional models, or—equivalently—as a propositional theory in disjunctive normal from. Converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net.For a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets.     

Indexing hierarchical structures using graph spectra

Hierarchical image structures are abundant in computer vision and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a framework for indexing such representations that embeds the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel spectral characterization of a DAG, this topological signature allows us to efficiently retrieve a promising set of candidates from a database of models using a simple nearest-neighbor search. We establish the insensitivity of the signature to minor perturbation of graph structure due to noise, occlusion, or node split/merge. To accommodate large-scale occlusion, the DAG rooted at each nonleaf node of the query "votes" for model objects that share that "part," effectively accumulating local evidence in a model DAG's topological subspaces. We demonstrate the approach with a series of indexing experiments in the domain of view-based 3D object recognition using shock graphs.     

A nice labelling for tree-like event structures of degree 3

We address the problem of finding nice labellings for event structures of degree 3. We develop a minimum theory by which we prove that the index of an event structure of degree 3 is bounded by a linear function of the height. The main theorem of the paper states that event structures of degree 3 whose causality order is a tree have a nice labelling with 3 colors. We exemplify how to use this theorem to construct upper bounds for the index of other event structures of degree 3.     

True-concurrency probabilistic models: Branching cells and distributed probabilities for event structures

This paper is devoted to probabilistic models for concurrent systems under their true-concurrency semantics. Here we address probabilistic event structures. We consider a new class of event structures, called locally finite, that extend confusion-free event structure. In locally finite event structures, maximal configurations can be tiled with branching cells: branching cells are minimal and finite sub-structures capturing the choices performed while scanning a maximal configuration. The probabilistic event structures that we introduce have the property that “concurrent processes are independent in the probabilistic sense.”     

PSIST: A scalable approach to indexing protein structures using suffix trees

Approaches for indexing proteins and for fast and scalable searching for structures similar to a query structure have important applications such as protein structure and function prediction, protein classification and drug discovery. In this paper, we develop a new method for extracting local structural (or geometric) features from protein structures. These feature vectors are in turn converted into a set of symbols, which are then indexed using a suffix tree. For a given query, the suffix tree index can be used effectively to retrieve the maximal matches, which are then chained to obtain the local alignments. Finally, similar proteins are retrieved by their alignment score against the query. Our results show classification accuracy up to 50% and 92.9% at the topology and class level according to the CATH classification. These results outperform the best previous methods. We also show that PSIST is highly scalable due to the external suffix tree indexing approach it uses; it is able to index about 70,500 domains from SCOP in under an hour.     

Splicing on tree-like structures

In this paper, we provide a method to increase the power of splicing systems. We introduce the splicing systems on trees to be built as partially annealed single strands, which is a quite similar notion and a natural extension of splicing systems on strings. Trees are a common and useful data structure in computer science and have a biological counterpart such as molecular sequences with secondary structures, which are typical structures in RNA sequences. Splicing on trees involves (1) complete subtrees as axioms, (2) restriction operated on the annealed subsequences, (3) rules to substitute a complete subtree with another. We show that splicing systems on trees with finite sets of axioms and finite sets of rules can generate the class of context-free languages without the need of imposing multiplicity constraints.     

Computing general geometric structures on surfaces using Ricci flow

Systematically generalizing planar geometric algorithms to manifold domains is of fundamental importance in computer aided design field. This paper proposes a novel theoretic framework, geometric structure, to conquer this problem. In order to discover the intrinsic geometric structures of general surfaces, we developed a theoretic rigorous and practical efficient method, Discrete Variational Ricci flow.Different geometries study the invariants under the corresponding transformation groups. The same geometry can be defined on various manifolds, whereas the same manifold allows different geometries. Geometric structures allow different geometries to be defined on various manifolds, therefore algorithms based on the corresponding geometric invariants can be applied on the manifold domains directly.Surfaces have natural geometric structures, such as spherical structure, affine structure, projective structure, hyperbolic structure and conformal structure. Therefore planar algorithms based on these geometries can be defined on surfaces straightforwardly.Computing the general geometric structures on surfaces has been a long lasting open problem. We solve the problem by introducing a novel method based on discrete variational Ricci flow.We thoroughly explain both theoretical and practical aspects of the computational methodology for geometric structures based on Ricci flow, and demonstrate several important applications of geometric structures: generalizing Voronoi diagram algorithms to surfaces via Euclidean structure, cross global parametrization between high genus surfaces via hyperbolic structure, generalizing planar splines to manifolds via affine structure. The experimental results show that our method is rigorous and efficient and the framework of geometric structures is general and powerful.     

Optimization of vibrating structures to reduce radiated noise

In this work, we propose an approach for reducing radiated noise from ‘light’ fluid-loaded structures, such as, for example, vibrating structures in air. In this approach, we optimize the structure so as to minimize the dynamic compliance (defined as the input power) of the structure. We show that minimizing the dynamic compliance results in substantial reductions in the radiated sound power from the structure. The main advantage of this approach is that the redesign to minimize the dynamic compliance moves the natural frequencies of the structure away from the driving frequency thereby reducing the vibration levels of the structure, which in turn results in a reduction in the radiated sound power as an indirect benefit. Thus, the need for an acoustic and the associated sensitivity analysis is completely bypassed (although, in this work, we do carry out an acoustic analysis to demonstrate the reduction in sound power levels), making the strategy efficient compared to existing strategies in the literature which try to minimize some measure of noise directly. We show the effectiveness of the proposed approach by means of several examples involving both topology and stiffener optimization, for vibrating beam, plate and shell-type structures.     

Automatic inpainting by removing fence-like structures in RGBD images

Recent inpainting techniques usually require human interactions which are labor intensive and dependent on the user experiences. In this paper, we introduce an automatic inpainting technique to remove undesired fence-like structures from images. Specifically, the proposed technique works on the RGBD images which have recently become cheaper and easier to obtain using the Microsoft Kinect. The basic idea is to segment and remove the undesired fence-like structures by using both depth and color information, and then adapt an existing inpainting algorithm to fill the holes resulting from the structure removal. We found that it is difficult to achieve a satisfactory segmentation of such structures by only using the depth channel. In this paper, we use the depth information to help identify a set of foreground and background strokes, with which we apply a graph-cut algorithm on the color channels to obtain a more accurate segmentation for inpainting. We demonstrate the effectiveness of the proposed technique by experiments on a set of Kinect images.     

A program for predicting significant RNA secondary structures

We describe a program for the analysis of RNA secondary structure. There are two new features in this program. (i) To get vector speeds on a vector pipeline machine (such as Cray X-MP/24) we have vectorized the secondary structure dynamic algorithm. (ii) The statistical significance of a locally 'optimal' secondary structure is assessed by a Monte Carlo method. The results can be depicted graphically including profiles of the stability of local secondary structures and the distribution of the potentially significant secondary structures in the RNA molecules. Interesting regions where both the potentially significant secondary structures and 'open' structures (single-stranded coils) occur can be identified by the plots mentioned above. Furthermore, the speed of the vectorized code allows repeated Monte Carlo simulations with different overlapping window sizes. Thus, the optimal size of the significant secondary structure occurring in the interesting region can be assessed by repeating the Monte Carlo simulation. The power of the program is demonstrated in the analysis of local secondary structures of human T-cell lymphotrophic virus type III (HIV).     

Sample-based synthesis of two-scale structures with anisotropy

A vast majority of natural or synthetic materials are characterized by their anisotropic properties, such as stiffness. Such anisotropy is effected by the spatial distribution of the fine-scale structure and/or anisotropy of the constituent phases at a finer scale. In design, proper control of the anisotropy may greatly enhance the efficiency and performance of synthesized structures.We propose a sample-based two-scale structure synthesis approach that explicitly controls anisotropic effective material properties of the structure on the coarse scale by orienting sampled material neighborhoods at the fine scale. We first characterize the non-uniform orientations distribution of the sample structure by showing that the principal axes of an orthotropic material may be determined by the eigenvalue decomposition of its effective stiffness tensor. Such effective stiffness tensors can be efficiently estimated based on the two-point correlation functions of the fine-scale structures. Then we synthesize the two-scale structure by rotating fine-scale structures from the sample to follow a given target orientation field. The effectiveness of the proposed approach is demonstrated through examples in both 2D and 3D.     

Positioning system for particles in microfluidic structures

Fast continuous flow detection of biomolecules in lab-on-a-chip structures is a challenging task. Combining these molecules with small magnetic particles, the interaction between their stray field and, e.g., magneto-resistive sensors can be used to indirectly prove the biomolecules. To position the particles on top of a sensor array at the bottom of the flow channel, we propose a microfluidic structure of changing channel height combining hydrodynamic and gravitational effects. We present numerical calculations predicting an increase in the capture rate by more than 100% in comparison to a straight channel. We experimentally realize an optical analysis of the specific binding of biotin-functionalized Chemagen beads on a streptavidin-coated surface. To prove the binding is not due to the surface effects, a second uncoated bead species is employed.     

Data structures in Java for matrix computations

In this paper we show how to utilize Java's native arrays for matrix computations. The disadvantages of Java arrays used as a 2D array for dense matrix computation are discussed and ways to improve the performance are examined. We show how to create efficient dynamic data structures for sparse matrix computations using Java's native arrays. This data structure is unique for Java and shown to be more dynamic and efficient than the traditional storage schemes for large sparse matrices. Numerical testing indicates that this new data structure, called Java Sparse Array, is competitive with the traditional Compressed Row Storage scheme on matrix computation routines. Java gives increased flexibility without losing efficiency. Compared with other object‐oriented data structures Java Sparse Array is shown to have the same flexibility. Copyright © 2004 John Wiley & Sons, Ltd.     

The designability of protein structures

It has been noted that natural proteins adapt only a limited number of folds. Several researchers have investigated why and how nature has selected this small number of folds. Using simple models of protein folding, we demonstrate systematically that there is a "designability principle" behind nature's selection of protein folds. The designability of a structure (fold) is measured by the number of sequences that can design the structure--that is, sequences that possess the structure as their unique ground state. Structures differ drastically in terms of their designability. A small number of highly designable structures emerge with a number of associated sequences much larger than the average. These highly designable structures possess proteinlike secondary structures, motifs, and even tertiary symmetries. In addition, they are thermodynamically more stable and fold faster than other structures. These results suggest that protein structures are selected in nature because they are readily designed and stable against mutations, and that such a selection simultaneously leads to thermodynamic stability.     

Mask design compensation for sloped sidewall structures fabricated by X-ray lithography

We have investigated and report in this paper the factors influencing the deformation caused by the dependence between the absorbed X-ray energy on the resist and the shape of the absorber on the X-ray mask. Based on the measurement of errors that occurred during the transferring process between the 2-D shape of mask pattern and the resulting wall of the fabricated 3-D structure, we have developed newly useful graphical data on the absorbed X-ray energy, dosage, and shape of a microstructure. As a result, it is being reported as a method for compensation for the deformed shape after the fabrication of a quadruplets-microneedle. We have considered a number of factors affecting the deformation and finally realized that the effect of a dose–depth nonlinear curve is the most possible cause. Without the compensation of the mask design, we could observe the deformed shapes of the sloped sidewall on the exposed structures. Polymethylmethacrylate microneedle structures fabricated by X-ray lithography with an additional plane-pattern to cross-section transfers technique are directly influenced by the absorber on the X-ray mask pattern. The sidewall of the microneedle was improved by changing the mask pattern from a double right-triangular pattern to a double semi-circular pattern, modeled by comparing the results from a mask-pattern and the actual structure.