Abstract

In recent studies it has been shown that graph representation of protein structures is capable of capturing the 3-dimensional fold of the protein very well, thus providing a computationally efficient approach for protein structure analysis. Centrality measures are generally used to identify the relative importance of a node in the network. Here we demonstrate a novel application of centrality analysis: to identify tandemly repeated structural motifs in 3-d protein structures. This is done by analyzing the profile of various centrality measures in the repeat region. The comparative analysis of five centrality measures based on local connectivity, shortest paths, principal eigen spectra and feedback centrality is presented on proteins containing contiguous ankyrin structural motifs to identify which centrality measure best captures the repetitive pattern of ankyrin. We observe that principal eigen spectra of the adjacency matrix and Katz status index, both exhibit a distinct profile for the ankyrin motif capturing its characteristic anti-parallel helix-turn-helix fold. No such conserved pattern was observed in the repeat regions of equivalent random networks, suggesting that the conserved pattern arises from the 3d fold of the structural motif.

Abstract

Repetition of a structural motif within protein is associated with a wide range of structural and functional roles. In most cases the repeating units are well conserved at the structural level while at the sequence level, they are mostly undetectable suggesting the need for structure-based methods. Since most known methods require a training dataset, de novo approach is desirable. Here, we propose an efficient graph-based approach for detecting structural repeats in proteins. In a protein structure represented as a graph, interactions between inter- and intra-repeat units are well captured by the eigen spectra of adjacency matrix of the graph. These conserved interactions give rise to similar connections and a unique profile of the principal eigen spectra for each repeating unit. The efficacy of the approach is shown on eight repeat families annotated in UniProt, comprising of both solenoid and nonsolenoid repeats with …

Abstract

Tandem repetition of structural motifs in proteins is frequently observed across all forms of life. Topology of repeating unit and its frequency of occurrence are associated to a wide range of structural and functional roles in diverse proteins, and defects in repeat proteins have been associated with a number of diseases. It is thus desirable to accurately identify specific repeat type and its copy number. Weak evolutionary constraints on repeat units and insertions/deletions between them make their identification difficult at the sequence level and structure based approaches are desired. The proposed graph spectral approach is based on protein structure represented as a graph for detecting one of the most frequently observed structural repeats, Ankyrin repeat.

Abstract

Let S be a set of n points in the plane. We present a method where, using O(n log2 n) time and space, S can be pre-processed into a data structure such that given an axis-parallel query rectangle q, we can report the radius of the smallest enclosing disk of the points lying in S ∩ q in O(log6 n) time per query

Abstract

We revisit the problem of anonymous communication where nodes communicate without revealing their identity. We propose its use in the choosing of a node as an anonymous leader and subsequent communication to and from this leader such that its identity is not revealed. We give indistinguishability definitions for anonymous leader and prove it to be secure in an arbitrary reliable network.

Abstract

We present output sensitive techniques for the generalized reporting versions of the planar range maxima problem and the planar range convex hull problem. Our solutions are in the pointer machine model, for orthogonal range queries on a static point set. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(logn + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log2 n + clogn) using O(n) space while for four-sided queries we answer queries in O(log3 n + clog2 n) using O(nlogn) space. For the planar range convex hull problem, we provide a solution that answers queries in O(log2 n + clogn) time, using O(nlog2 n) space.

Abstract

We propose a supervised learning technique defining significant frequent patterns for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Generalized Iterative Scaling (GIS) convergence algorithm for Maximum Entropy (ME) models. We have used the combinations of ME parameters and GIS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then order the predictive analytics output. Experiments are conducted on sparse numeric datasets. Results suggest that condensed representations of frequent patterns allow parametric models suitable for class association rule mining.

Abstract

We present here, TagMiner, a data mining approach for part-of-speech (POS) tagging, an important Natural language process-ing (NLP) classification task. It is a semi-supervised associative clas-sification method for POS tagging. Existing methods for building POS taggers require extensive domain and linguistic knowledge and resources.Our method uses combination of a small POS tagged corpus and a raw untagged text data as training data to build the classifier model using association rules. Our tagger works well with very little training dataalso. The use of semi-supervised learning provides the advantage of notrequiring a large high quality tagged corpus. These properties make it es-pecially suitable for resource poor languages. Our experiments on various resource-rich, resource-moderate and resource-poor languages show good performance without using any language specific linguistic information.We note that inclusion of such features in our method may further im-prove the performance. Results also show that for smaller training data sizes our tagger performs better than state-of-the-art CRF tagger using same features as our tagger.

Abstract

We propose a supervised learning technique for associative regression. Assuming frequent patterns quantify correlations in dataset, we constrain the Sequential Conditional Generalized Iterative Scaling (SCGIS) convergence algorithm for Maximum Entropy (ME) models. We also assume prior probabilities on the ME model as a control on the step size in SCGIS. We have used the combinations of ME parameters and SCGIS probabilities as discriminative weights to frequent patterns. The weighted frequent patterns then predict the associative regression values. Experiments have been conducted on sparse numeric datasets, to find the regression error of our proposal. Our technique is comparable to the standard regression algorithms. As a concept, the proposed associative regression is useful as a parametric model in class association rule mining.

Abstract

Studies on the emotion recognition task indicate that there is confusion in discrimination among higher activation states like ‘anger’ and ‘happy’. In this study, features related to excitation source of speech are examined for discriminating ‘anger’ and ‘happy’ emotions. The objective is to explore the features which are independent of lexical content, language, channel and speaker. The features like strength of excitation from zero frequency filtering method and spectral band magnitude energies from short-time spectral analysis are used. Experimental results show that these features can discriminate ‘anger’ and ‘happy’ emotion states to a good extent.