Definitions and nomenclature of nucleic acid structure parameters

At an EMBO Workshop on DNA Curvature and Bending, held at Churchill College, Cambridge, on 10-15 September 1988, two sessions were scheduled on definitions of parameters used to describe the geometry of nucleic acid chains and helices, and a common nomenclature for these parameters. The most widely used library of helix analysis programs, HELIB (Fratini et al., 1982; Dickerson, 1985) suffers from the fact that the translations and rotations as defined are not fully independent and depend to a certain extent upon the choice of overall helix axis. Several research groups have been engaged independently in developing alternative programs for the geometrical analysis of polynucleotide chains, but with different definitions of quantities calculated and with widely different nomenclature even when the same parameter was involved.

Concept of "Crossover Point" and its Application on Threshold Voltage Definition for Undoped-Body Transistors

As the conventional MOSFET's scaling is approaching the limit imposed by short channel effects, Double Gate (DG) MOS transistors are appearing as the most feasible candidate in terms of technology in sub-45nm technology nodes. As the short channel effect in DG transistor is controlled by the device geometry, undoped or lightly doped body is used to sustain the channel. There exits a disparity in threshold voltage calculation criteria of undoped-body symmetric double gate transistors which uses two definitions, one is potential based and the another is charge based definition. In this paper, a novel concept of "crossover point'' is introduced, which proves that the charge-based definition is more accurate than the potential based definition.The change in threshold voltage with body thickness variation for a fixed channel length is anomalous as predicted by potential based definition while it is monotonous for charge based definition.The threshold voltage is then extracted from drain currant versus gate voltage characteristics using linear extrapolation and "Third Derivative of Drain-Source Current'' method or simply "TD'' method. The trend of threshold voltage variation is found same in both the cases which support charge-based definition.

Concept of Crossover point and its application on Threshold Voltage definition for Undoped-Body Transistors

As the conventional MOSFETs scaling is approaching the limit imposed by short channel effects, Double Gate (DG) MOS transistors are appearing as the most feasible andidate in terms of technology in sub-45nm technology nodes. As the short channel effect in DG transistor is controlled by the device geometry, undoped or lightly doped body, is used to sustain the channel. There exits a disparity in threshold voltage calculation criteria of undoped-body symmetric double gate transistors which uses two definitions, one is potential based and the another is charge based definition. In this paper, a novel concept of "crossover point" is introduced, which proves that the charge-based definition is more accurate than the potential based definition. The change in threshold voltage with body thickness variation for a fixed channel length is anomalous as predicted by, potential based definition while it is monotonous for change based definition. The threshold voltage is then extracted from drain currant versus gate voltage characteristics using linear extrapolation and "Third Derivative of Drain-Source Current" method or simply "TD" method. The trend of threshold voltage variation is found some in both the cases which support charge-based definition.

Justifying threshold voltage definition for undoped body transistors through ``crossover point'' concept

Two different definitions, one is potential based and the other is charge based, are used in the literatures to define the threshold voltage of undoped body symmetric double gate transistors. This paper, by introducing a novel concept of crossover point, proves that the charge based definition is more accurate than the potential based definition. It is shown that for a given channel length the potential based definition predicts anomalous change in threshold voltage with body thickness variation while the charge based definition results in monotonous change. The threshold voltage is then extracted from drain current versus gate voltage characteristics using linear extrapolation, transconductance and match-point methods. In all the three cases it is found that trend of threshold voltage variation support the charge based definition.

Recognition And Top-Down Generation Of Beta-Acyclic Database Schemes

Database schemes can be viewed as hypergraphs with individual relation schemes corresponding to the edges of a hypergraph. Under this setting, a new class of "acyclic" database schemes was recently introduced and was shown to have a claim to a number of desirable properties. However, unlike the case of ordinary undirected graphs, there are several unequivalent notions of acyclicity of hypergraphs. Of special interest among these are agr-, beta-, and gamma-, degrees of acyclicity, each characterizing an equivalence class of desirable properties for database schemes, represented as hypergraphs. In this paper, two complementary approaches to designing beta-acyclic database schemes have been presented. For the first part, a new notion called "independent cycle" is introduced. Based on this, a criterion for beta-acyclicity is developed and is shown equivalent to the existing definitions of beta-acyclicity. From this and the concept of the dual of a hypergraph, an efficient algorithm for testing beta-acyclicity is developed. As for the second part, a procedure is evolved for top-down generation of beta-acyclic schemes and its correctness is established. Finally, extensions and applications of ideas are described.

On various types of decoupling for time-varying system

This paper deals with the problem of decoupling a class of linear time-varying multi-variable systems, based on the defining property that the impulse response matrix of a decoupled system is diagonal. Depending on the properties of the coefficient matrices of the vector differential equation of the open-loop system, the system may be uniformly or totally decoupled. The necessary and sufficient conditions that permit a system to be uniformly or totally decoupled by state variable feedback are given. The main contribution of this paper is the precise definition of these two classes of decoupling and a rigorous derivation of the necessary and sufficient conditions which show the necessity of requiring that the system be of constant ordered rank with respect to observability. A simple example illustrates the importance of having several definitions of decoupling. Finally, the results are specialized to the case of time invariant systems.

Wigner distributions for finite-state systems without redundant phase-point operators

We set up Wigner distributions for N-state quantum systems following a Dirac-inspired approach. In contrast to much of the work in this study, requiring a 2N x 2N phase space, particularly when N is even, our approach is uniformly based on an N x N phase-space grid and thereby avoids the necessity of having to invoke a `quadrupled' phase space and hence the attendant redundance. Both N odd and even cases are analysed in detail and it is found that there are striking differences between the two. While the N odd case permits full implementation of the marginal property, the even case does so only in a restricted sense. This has the consequence that in the even case one is led to several equally good definitions of the Wigner distributions as opposed to the odd case where the choice turns out to be unique.

A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science," pp. 514-519), which states that circled plus P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci.47, 85-93).

On the Decidability of Model-Checking Information Flow Properties

Current standard security practices do not provide substantial assurance about information flow security: the end-to-end behavior of a computing system. Noninterference is the basic semantical condition used to account for information flow security. In the literature, there are many definitions of noninterference: Non-inference, Separability and so on. Mantel presented a framework of Basic Security Predicates (BSPs) for characterizing the definitions of noninterference in the literature. Model-checking these BSPs for finite state systems was shown to be decidable in [8]. In this paper, we show that verifying these BSPs for the more expressive system model of pushdown systems is undecidable. We also give an example of a simple security property which is undecidable even for finite-state systems: the property is a weak form of non-inference called WNI, which is not expressible in Mantel’s BSP framework.

Holistic Schema Mappings for XML-on-RDBMS

When hosting XML information on relational backends, a mapping has to be established between the schemas of the information source and the target storage repositories. A rich body of recent literature exists for mapping isolated components of XML Schema to their relational counterparts, especially with regard to table configurations. In this paper, we present the Elixir system for designing industrial-strength mappings for real-world applications. Specifically, it produces an information-preserving holistic mapping that transforms the complete XML world-view (XML schema with constraints, XML documents XQuery queries including triggers and views) into a full-scale relational mapping (table definitions, integrity constraints, indices, triggers and views) that is tuned to the application workload. A key design feature of Elixir is that it performs all its mapping-related optimizations in the XML source space, rather than in the relational target space. Further, unlike the XML mapping tools of commercial database systems, which rely heavily on user inputs, Elixir takes a principled cost-based approach to automatically find an efficient relational mapping. A prototype of Elixir is operational and we quantitatively demonstrate its functionality and efficacy on a variety of real-life XML schemas.

Minimal Triangulations of Manifolds

Finding vertex-minimal triangulations of closed manifolds is a very difficult problem. Except for spheres and two series of manifolds, vertex-minimal triangulations are known for only few manifolds of dimension more than 2 (see the table given at the end of Section 5). In this article, we present a brief survey on the works done in last 30 years on the following:(i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers n and d, construction of n-vertex triangulations of different d-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of vertices.In Section 1, we have given all the definitions which are required for the remaining part of this article. A reader can start from Section 2 and come back to Section 1 as and when required. In Section 2, we have presented a very brief history of triangulations of manifolds. In Section 3,we have presented examples of several vertex-minimal triangulations. In Section 4, we have presented some interesting results on triangulations of manifolds. In particular, we have stated the Lower Bound Theorem and the Upper Bound Theorem. In Section 5, we have stated several results on minimal triangulations without proofs. Proofs are available in the references mentioned there. We have also presented some open problems/conjectures in Sections 3 and 5.

Population crunch in India: is it urban or still rural?

The article attempts to present analysis based on the provisional results of the Census 2011. While there is no doubt that the human social organization of the country is undergoing a transition, the nature of growth however is subject to the lens through which this is viewed. Noting the dichotomy of urban and rural definitions, we question the rationality of the ‘urban’ definition and its relevance.

Pattern-growth based frequent serial episode discovery

Frequent episode discovery is a popular framework for pattern discovery from sequential data. It has found many applications in domains like alarm management in telecommunication networks, fault analysis in the manufacturing plants, predicting user behavior in web click streams and so on. In this paper, we address the discovery of serial episodes. In the episodes context, there have been multiple ways to quantify the frequency of an episode. Most of the current algorithms for episode discovery under various frequencies are apriori-based level-wise methods. These methods essentially perform a breadth-first search of the pattern space. However currently there are no depth-first based methods of pattern discovery in the frequent episode framework under many of the frequency definitions. In this paper, we try to bridge this gap. We provide new depth-first based algorithms for serial episode discovery under non-overlapped and total frequencies. Under non-overlapped frequency, we present algorithms that can take care of span constraint and gap constraint on episode occurrences. Under total frequency we present an algorithm that can handle span constraint. We provide proofs of correctness for the proposed algorithms. We demonstrate the effectiveness of the proposed algorithms by extensive simulations. We also give detailed run-time comparisons with the existing apriori-based methods and illustrate scenarios under which the proposed pattern-growth algorithms perform better than their apriori counterparts. (C) 2013 Elsevier B.V. All rights reserved.

The relationship between classification of multi-domain proteins using an alignment-free approach and their functions: a case study with immunoglobulins

Establishing functional relationships between multi-domain protein sequences is a non-trivial task. Traditionally, delineating functional assignment and relationships of proteins requires domain assignments as a prerequisite. This process is sensitive to alignment quality and domain definitions. In multi-domain proteins due to multiple reasons, the quality of alignments is poor. We report the correspondence between the classification of proteins represented as full-length gene products and their functions. Our approach differs fundamentally from traditional methods in not performing the classification at the level of domains. Our method is based on an alignment free local matching scores (LMS) computation at the amino-acid sequence level followed by hierarchical clustering. As there are no gold standards for full-length protein sequence classification, we resorted to Gene Ontology and domain-architecture based similarity measures to assess our classification. The final clusters obtained using LMS show high functional and domain architectural similarities. Comparison of the current method with alignment based approaches at both domain and full-length protein showed superiority of the LMS scores. Using this method we have recreated objective relationships among different protein kinase sub-families and also classified immunoglobulin containing proteins where sub-family definitions do not exist currently. This method can be applied to any set of protein sequences and hence will be instrumental in analysis of large numbers of full-length protein sequences.

CLAP: A web-server for automatic classification of proteins with special reference to multi-domain proteins

Background: The function of a protein can be deciphered with higher accuracy from its structure than from its amino acid sequence. Due to the huge gap in the available protein sequence and structural space, tools that can generate functionally homogeneous clusters using only the sequence information, hold great importance. For this, traditional alignment-based tools work well in most cases and clustering is performed on the basis of sequence similarity. But, in the case of multi-domain proteins, the alignment quality might be poor due to varied lengths of the proteins, domain shuffling or circular permutations. Multi-domain proteins are ubiquitous in nature, hence alignment-free tools, which overcome the shortcomings of alignment-based protein comparison methods, are required. Further, existing tools classify proteins using only domain-level information and hence miss out on the information encoded in the tethered regions or accessory domains. Our method, on the other hand, takes into account the full-length sequence of a protein, consolidating the complete sequence information to understand a given protein better. Results: Our web-server, CLAP (Classification of Proteins), is one such alignment-free software for automatic classification of protein sequences. It utilizes a pattern-matching algorithm that assigns local matching scores (LMS) to residues that are a part of the matched patterns between two sequences being compared. CLAP works on full-length sequences and does not require prior domain definitions. Pilot studies undertaken previously on protein kinases and immunoglobulins have shown that CLAP yields clusters, which have high functional and domain architectural similarity. Moreover, parsing at a statistically determined cut-off resulted in clusters that corroborated with the sub-family level classification of that particular domain family. Conclusions: CLAP is a useful protein-clustering tool, independent of domain assignment, domain order, sequence length and domain diversity. Our method can be used for any set of protein sequences, yielding functionally relevant clusters with high domain architectural homogeneity. The CLAP web server is freely available for academic use at http://nslab.mbu.iisc.ernet.in/clap/.