Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.

PolyMage: Automatic Optimization for Image Processing Pipelines

This paper presents the design and implementation of PolyMage, a domain-specific language and compiler for image processing pipelines. An image processing pipeline can be viewed as a graph of interconnected stages which process images successively. Each stage typically performs one of point-wise, stencil, reduction or data-dependent operations on image pixels. Individual stages in a pipeline typically exhibit abundant data parallelism that can be exploited with relative ease. However, the stages also require high memory bandwidth preventing effective utilization of parallelism available on modern architectures. For applications that demand high performance, the traditional options are to use optimized libraries like OpenCV or to optimize manually. While using libraries precludes optimization across library routines, manual optimization accounting for both parallelism and locality is very tedious. The focus of our system, PolyMage, is on automatically generating high-performance implementations of image processing pipelines expressed in a high-level declarative language. Our optimization approach primarily relies on the transformation and code generation capabilities of the polyhedral compiler framework. To the best of our knowledge, this is the first model-driven compiler for image processing pipelines that performs complex fusion, tiling, and storage optimization automatically. Experimental results on a modern multicore system show that the performance achieved by our automatic approach is up to 1.81x better than that achieved through manual tuning in Halide, a state-of-the-art language and compiler for image processing pipelines. For a camera raw image processing pipeline, our performance is comparable to that of a hand-tuned implementation.

Identification of Specific DNA Binding Residues in the TCP Family of Transcription Factors in Arabidopsis

The TCP transcription factors control multiple developmental traits in diverse plant species. Members of this family share an similar to 60-residue-long TCP domain that binds to DNA. The TCP domain is predicted to form a basic helix-loop-helix ( bHLH) structure but shares little sequence similarity with canonical bHLH domain. This classifies the TCP domain as a novel class of DNA binding domain specific to the plant kingdom. Little is known about how the TCP domain interacts with its target DNA. We report biochemical characterization and DNA binding properties of a TCP member in Arabidopsis thaliana, TCP4. We have shown that the 58-residue domain of TCP4 is essential and sufficient for binding to DNA and possesses DNA binding parameters comparable to canonical bHLH proteins. Using a yeast-based random mutagenesis screen and site-directed mutants, we identified the residues important for DNA binding and dimer formation. Mutants defective in binding and dimerization failed to rescue the phenotype of an Arabidopsis line lacking the endogenous TCP4 activity. By combining structure prediction, functional characterization of the mutants, and molecular modeling, we suggest a possible DNA binding mechanism for this class of transcription factors.

Segregating Discourse Segments from Engineering Documents for Knowledge Acquisition

The broader goal of the research being described here is to automatically acquire diagnostic knowledge from documents in the domain of manual and mechanical assembly of aircraft structures. These documents are treated as a discourse used by experts to communicate with others. It therefore becomes possible to use discourse analysis to enable machine understanding of the text. The research challenge addressed in the paper is to identify documents or sections of documents that are potential sources of knowledge. In a subsequent step, domain knowledge will be extracted from these segments. The segmentation task requires partitioning the document into relevant segments and understanding the context of each segment. In discourse analysis, the division of a discourse into various segments is achieved through certain indicative clauses called cue phrases that indicate changes in the discourse context. However, in formal documents such language may not be used. Hence the use of a domain specific ontology and an assembly process model is proposed to segregate chunks of the text based on a local context. Elements of the ontology/model, and their related terms serve as indicators of current context for a segment and changes in context between segments. Local contexts are aggregated for increasingly larger segments to identify if the document (or portions of it) pertains to the topic of interest, namely, assembly. Knowledge acquired through such processes enables acquisition and reuse of knowledge during any part of the lifecycle of a product.

Immunological cross-reactivity of mycobacterial topoisomerase I and divergence from other bacteria

Mycobacterium smegmatis topoisomerase I exhibits several distinctive characteristics among all topoisomerases. The enzyme is devoid of Zn2+fingers found typically in other bacterial type I topoisomerases and binds DNA in a site-specific manner. Using polyclonal antibodies, we demonstrate the high degree of relatedness of the enzyme across mycobacteria but not other bacteria. This absence of cross-reactivity from other bacteria indicates that mycobacterial topoisomerase I has diverged from Escherichia coli and other bacteria. We have investigated further the immunological properties of the enzyme by raising a panel of monoclonal antibodies that recognises different antigenically active regions of the enzyme and binds it with widely varied affinity. Inhibition of a C-terminal domain-specific antibody binding by enzyme-specific and non-specific oligonucleotides suggests the possibility of using these monoclonal antibodies to probe the structure, function and in vivo role of the enzyme.

Relaxation Labeling with Learning Automata

Relaxation labeling processes are a class of mechanisms that solve the problem of assigning labels to objects in a manner that is consistent with respect to some domain-specific constraints. We reformulate this using the model of a team of learning automata interacting with an environment or a high-level critic that gives noisy responses as to the consistency of a tentative labeling selected by the automata. This results in an iterative linear algorithm that is itself probabilistic. Using an explicit definition of consistency we give a complete analysis of this probabilistic relaxation process using weak convergence results for stochastic algorithms. Our model can accommodate a range of uncertainties in the compatibility functions. We prove a local convergence result and show that the point of convergence depends both on the initial labeling and the constraints. The algorithm is implementable in a highly parallel fashion.

Tiling stencil computations to maximize parallelism

Most stencil computations allow tile-wise concurrent start, i.e., there always exists a face of the iteration space and a set of tiling hyperplanes such that all tiles along that face can be started concurrently. This provides load balance and maximizes parallelism. However, existing automatic tiling frameworks often choose hyperplanes that lead to pipelined start-up and load imbalance. We address this issue with a new tiling technique that ensures concurrent start-up as well as perfect load-balance whenever possible. We first provide necessary and sufficient conditions on tiling hyperplanes to enable concurrent start for programs with affine data accesses. We then provide an approach to find such hyperplanes. Experimental evaluation on a 12-core Intel Westmere shows that our code is able to outperform a tuned domain-specific stencil code generator by 4% to 27%, and previous compiler techniques by a factor of 2x to 10.14x.

The GAF Domain of the cGMP-Binding, cGMP-Specific Phosphodiesterase (PDE5) Is a Sensor and a Sink for cGMP

We describe here a novel sensor for cGMP based on the GAF domain of the cGMP-binding, cGMP-specific phosphodiesterase 5 (PDE5) using bioluminescence resonance energy transfer (BRET). The wild type GAFa domain, capable of binding cGMP with high affinity, and a mutant (GAFaF163A) unable to bind cGMP were cloned as fusions between GFP and Rluc for BRET2 assays. BRET2 ratios of the wild type GAFa fusion protein, but not GAFaF163A, increased in the presence of cGMP but not cAMP. Higher basal BRET2 ratios were observed in cells expressing the wild type GAFa domain than in cells expressing GAFaF163A. This was correlated with elevated basal intracellular levels of cGMP, indicating that the GAF domain could act as a sink for cGMP. The tandem GAF domains in full length PDE5 could also sequester cGMP when the catalytic activity of PDE5 was inhibited. Therefore, these results describe a cGMP sensor utilizing BRET2 technology and experimentally demonstrate the reservoir of cGMP that can be present in cells that express cGMP-binding GAF domain-containing proteins. PDE5 is the target for the anti-impotence drug sildenafil citrate; therefore, this GAF-BRET2 sensor could be used for the identification of novel compounds that inhibit cGMP binding to the GAF domain, thereby regulating PDE5 catalytic activity.

Differential Reaction Kinetics, Cleavage Complex Formation, and Nonamer Binding Domain Dependence Dictate the Structure-Specific and Sequence-Specific Nuclease Activity of RAGs

During V(D)J recombination, RAG (recombination-activating gene) complex cleaves DNA based on sequence specificity. Besides its physiological function, RAG has been shown to act as a structure-specific nuclease. Recently, we showed that the presence of cytosine within the single-stranded region of heteroduplex DNA is important when RAGs cleave on DNA structures. In the present study, we report that heteroduplex DNA containing a bubble region can be cleaved efficiently when present along with a recombination signal sequence (RSS) in cis or trans configuration. The sequence of the bubble region influences RAG cleavage at RSS when present in cis. We also find that the kinetics of RAG cleavage differs between RSS and bubble, wherein RSS cleavage reaches maximum efficiency faster than bubble cleavage. In addition, unlike RSS, RAG cleavage at bubbles does not lead to cleavage complex formation. Finally, we show that the ``nonamer binding region,'' which regulates RAG cleavage on RSS, is not important during RAG activity in non-B DNA structures. Therefore, in the current study, we identify the possible mechanism by which RAG cleavage is regulated when it acts as a structure-specific nuclease. (C) 2011 Elsevier Ltd. All rights reserved.

C2 domain is responsible for targeting rice phosphoinositide specific phospholipase C

Phosphoinositide-specific phospholipase C (PLC) is involved in Ca2+ mediated signalling events that lead to altered cellular status. Using various sequence-analysis methods, we identified two conserved motifs in known PLC sequences. The identified motifs are located in the C2 domain of plant PLCs and are not found in any other protein. These motifs are specifically found in the Ca2+ binding loops and form adjoining beta strands. Further, we identified certain conserved residues that are highly distinct from corresponding residues of animal PLCs. The motifs reported here could be used to annotate plant-specific phospholipase C sequences. Furthermore, we demonstrated that the C2 domain alone is capable of targeting PLC to the membrane in response to a Ca2+ signal. We also showed that the binding event results from a change in the hydrophobicity of the C2 domain upon Ca2+ binding. Bioinformatic analyses revealed that all PLCs from Arabidopsis and rice lack a transmembrane domain, myristoylation and GPI-anchor protein modifications. Our bioinformatic study indicates that plant PLCs are located in the cytoplasm, the nucleus and the mitochondria. Our results suggest that there are no distinct isoforms of plant PLCs, as have been proposed to exist in the soluble and membrane associated fractions. The same isoform could potentially be present in both subcellular fractions, depending on the calcium level of the cytosol. Overall, these data suggest that the C2 domain of PLC plays a vital role in calcium signalling.

Comparative kinomics of human and chimpanzee reveal unique kinship and functional diversity generated by new domain combinations

Background: Phosphorylation by protein kinases is a common event in many cellular processes. Further, many kinases perform specialized roles and are regulated by non-kinase domains tethered to kinase domain. Perturbation in the regulation of kinases leads to malignancy. We have identified and analysed putative protein kinases encoded in the genome of chimpanzee which is a close evolutionary relative of human. Result: The shared core biology between chimpanzee and human is characterized by many orthologous protein kinases which are involved in conserved pathways. Domain architectures specific to chimp/human kinases have been observed. Chimp kinases with unique domain architectures are characterized by deletion of one or more non-kinase domains in the human kinases. Interestingly, counterparts of some of the multi-domain human kinases in chimp are characterized by identical domain architectures but with kinase-like non-kinase domain. Remarkably, out of 587 chimpanzee kinases no human orthologue with greater than 95% sequence identity could be identified for 160 kinases. Variations in chimpanzee kinases compared to human kinases are brought about also by differences in functions of domains tethered to the catalytic kinase domain. For example, the heterodimer forming PB1 domain related to the fold of ubiquitin/Ras-binding domain is seen uniquely tethered to PKC-like chimpanzee kinase. Conclusion: Though the chimpanzee and human are evolutionary very close, there are chimpanzee kinases with no close counterpart in the human suggesting differences in their functions. This analysis provides a direction for experimental analysis of human and chimpanzee protein kinases in order to enhance our understanding on their specific biological roles.

Access path query language for relational database systems

Database management systems offer a very reliable and attractive data organization for fast and economical information storage and processing for diverse applications. It is much more important that the information should be easily accessible to users with varied backgrounds, professional as well as casual, through a suitable data sublanguage. The language adopted here (APPLE) is one such language for relational database systems and is completely nonprocedural and well suited to users with minimum or no programming background. This is supported by an access path model which permits the user to formulate completely nonprocedural queries expressed solely in terms of attribute names. The data description language (DDL) and data manipulation language (DML) features of APPLE are also discussed. The underlying relational database has been implemented with the help of the DATATRIEVE-11 utility for record and domain definition which is available on the PDP-11/35. The package is coded in Pascal and MACRO-11. Further, most of the limitations of the DATATRIEVE-11 utility have been eliminated in the interface package.

The Evolution of Guanylyl Cyclases as Multidomain Proteins: Conserved Features of Kinase-Cyclase Domain Fusions

Guanylyl cyclases (GCs) are enzymes that generate cyclic GMP and regulate different physiologic and developmental processes in a number of organisms. GCs possess sequence similarity to class III adenylyl cyclases (ACs) and are present as either membrane-bound receptor GCs or cytosolic soluble GCs. We sought to determine the evolution of GCs using a large-scale bioinformatic analysis and found multiple lineage-specific expansions of GC genes in the genomes of many eukaryotes. Moreover, a few GC-like proteins were identified in prokaryotes, which come fused to a number of different domains, suggesting allosteric regulation of nucleotide cyclase activity Eukaryotic receptor GCs are associated with a kinase homology domain (KHD), and phylogenetic analysis of these proteins suggest coevolution of the KHD and the associated cyclase domain as well as a conservation of the sequence and the size of the linker region between the KHD and the associated cyclase domain. Finally, we also report the existence of mimiviral proteins that contain putative active kinase domains associated with a cyclase domain, which could suggest early evolution of the fusion of these two important domains involved in signa transduction.

L2-stability of nonstationary feedback systems: Frequency-domain criteria

A frequency-domain positivity condition is derived for linear time-varying operators in2and is used to develop2stability criteria for linear and nonlinear feedback systems. These criteria permit the use of a very general class of operators in2with nonstationary kernels, as multipliers. More specific results are obtained by using a first-order differential operator with a time-varying coefficient as multiplier. Finally, by employing periodic multipliers, improved stability criteria are derived for the nonlinear damped Mathieu equation with a forcing function.

Genetic studies of the PRP17 gene of Saccharomyces cerevisiae: a domain essential for function maps to a nonconserved region of the protein

The PRP17 gene product is required for the second step of pre-mRNA splicing reactions. The C-terminal half of this protein bears four repeat units with homology to the beta transducin repeat. Missense mutations in three temperature-sensitive prp17 mutants map to a region in the N-terminal half of the protein. We have generated, in vitro, 11 missense alleles at the beta transducin repeat units and find that only one affects function in vivo. A phenotypically silent missense allele at the fourth repeat unit enhances the slow-growing phenotype conferred by an allele at the third repeat, suggesting an interaction between these domains. Although many missense mutations in highly conserved amino acids lack phenotypic effects, deletion analysis suggests an essential role for these units. Only mutations in the N-terminal nonconserved domain of PRP17 are synthetically lethal in combination with mutations in PRP16 and PRP18, two other gene products required for the second splicing reaction. A mutually allele-specific interaction between Prp17 and snr7, with mutations in U5 snRNA, was observed. We therefore suggest that the functional region of Prp17p that interacts with Prp18p, Prp16p, and U5 snRNA is the N terminal region of the protein.