On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Border basis detection is NP-complete

Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Grobner bases termed as Grobner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.

Tectono-geomorphic and environmental set-up deduced during deposition of Mio-Pleistocene sediments in NW Himalaya, India

Detailed pedofacies characterization along-with lithofacies investigations of the Mio-Pleistocene Siwalik sediments exposed in the Ramnagar sub-basin have been studied so as to elucidate variability in time and space of fluvial processes and the role of intra- and extra-basinal controls on fluvial sedimentation during the evolution of the Himalayan foreland basin (HFB). Dominance of multiple, moderately to strongly developed palaeosol assemblages during deposition of Lower Siwalik (similar to 12-10.8 Ma) sediments suggest that the HFB was marked by Upland set-up of Thomas et al. (2002). Activity of intra-basinal faults on the uplands and deposition of terminal fans at different times caused the development of multiple soils. Further, detailed pedofacies along-with lithofacies studies indicate prevalence of stable tectonic conditions and development of meandering streams with broad floodplains. However, the Middle Siwalik (similar to 10.8-4.92 Ma) sub-group is marked by multistoried sandstones and minor mudstone and mainly weakly developed palaeosols, indicating deposition by large braided rivers in the form of megafans in a Lowland set-up of Thomas et al. (2002). Significant change in nature and size of rivers from the Lower to Middle Siwalik at similar to 10 Ma is found almost throughout of the basin from Kohat Plateau (Pakistan) to Nepal because the Himalayan orogeny witnessed its greatest tectonic upheaval at this time leading to attainment of great heights by the Himalaya, intensification of the monsoon, development of large rivers systems and a high rate of sedimentation, hereby a major change from the Upland set-up to the Lowland set-up over major parts of the HFB. An interesting geomorphic environmental set-up prevailed in the Ramnagar sub-basin during deposition of the studied Upper Siwalik (similar to 4.92 to <1.68 Ma) sediments as observed from the degree of pedogenesis and the type of palaeosols. In general, the Upper Siwalik sub-group in the Ramnagar sub-basin is subdivided from bottom to top into the Purmandal sandstone (4.92-4.49 Ma), Nagrota (4.49-1.68 Ma) and Boulder Conglomerate (<1.68 Ma) formations on the basis of sedimentological characters and change in dominant lithology. Presence of mudstone, a few thin gravel beds and dominant sandstone lithology with weakly to moderately developed palaeosols in the Purmandal sandstone Fm. indicates deposition by shallow braided fluvial streams. The deposition of mudstone dominant Nagrota Fm. with moderately to some well developed palaeosols and a zone of gleyed palaeosols with laminated mudstones and thin sandstones took place in an environment marked by numerous small lakes, water-logged regions and small streams in an environment just south of the Piedmont zone, perhaps similar to what is happening presently in the Upland region/the Upper Gangetic plain. This area is locally called the `Trai region' (Pascoe, 1964). Deposition of Boulder Conglomerate Fm. took place by gravelly braided river system close to the Himalayan Ranges. Activity along the Main Boundary Fault led to progradation of these environments distal-ward and led to development of on the whole a coarsening upward sequence. (C) 2014 Elsevier B.V. All rights reserved.

The Molecular Basis of Lysine Acetylation: Addition, Removal, and Recognition

Acetyltransferases and deacetylases catalyze the addition and removal, respectively, of acetyl groups to the epsilon-amino group of protein lysine residues. This modification can affect the function of a protein through several means, including the recruitment of specific binding partners called acetyl-lysine readers. Acetyltransferases, deacetylases, and acetyl-lysine readers have emerged as crucial regulators of biological processes and prominent targets for the treatment of human disease. This work describes a combination of structural, biochemical, biophysical, cell-biological, and organismal studies undertaken on a set of proteins that cumulatively include all steps of the acetylation process: the acetyltransferase MEC-17, the deacetylase SIRT1, and the acetyl-lysine reader DPF2. Tubulin acetylation by MEC-17 is associated with stable, long-lived microtubule structures. We determined the crystal structure of the catalytic domain of human MEC-17 in complex with the cofactor acetyl-CoA. The structure in combination with an extensive enzymatic analysis of MEC-17 mutants identified residues for cofactor and substrate recognition and activity. A large, evolutionarily conserved hydrophobic surface patch distal to the active site was shown to be necessary for catalysis, suggesting that specificity is achieved by interactions with the alpha-tubulin substrate that extend outside of the modified surface loop. Experiments in C. elegans showed that while MEC-17 is required for touch sensitivity, MEC-17 enzymatic activity is dispensible for this behavior. SIRT1 deacetylates a wide range of substrates, including p53, NF-kappaB, FOXO transcription factors, and PGC-1-alpha, with roles in cellular processes ranging from energy metabolism to cell survival. SIRT1 activity is uniquely controlled by a C-terminal regulatory segment (CTR). Here we present crystal structures of the catalytic domain of human SIRT1 in complex with the CTR in an apo form and in complex with a cofactor and a pseudo-substrate peptide. The catalytic domain adopts the canonical sirtuin fold. The CTR forms a beta-hairpin structure that complements the beta-sheet of the NAD^+-binding domain, covering an essentially invariant, hydrophobic surface. A comparison of the apo and cofactor bound structures revealed conformational changes throughout catalysis, including a rotation of a smaller subdomain with respect to the larger NAD^+-binding subdomain. A biochemical analysis identified key residues in the active site, an inhibitory role for the CTR, and distinct structural features of the CTR that mediate binding and inhibition of the SIRT1 catalytic domain. DPF2 represses myeloid differentiation in acute myelogenous leukemia. Finally, we solved the crystal structure of the tandem PHD domain of human DPF2. We showed that DPF2 preferentially binds H3 tail peptides acetylated at Lys14, and binds H4 tail peptides with no preference for acetylation state. Through a structural and mutational analysis we identify the molecular basis of histone recognition. We propose a model for the role of DPF2 in AML and identify the DPF2 tandem PHD finger domain as a promising novel target for anti-leukemia therapeutics.

Using Level Sets as the basis for a scalable, parallel geometry engine and mesh generation system

The background to this review paper is research we have performed over recent years aimed at developing a simulation system capable of handling large scale, real world applications implemented in an end-to-end parallel, scalable manner. The particular focus of this paper is the use of a Level Set solid modeling geometry kernel within this parallel framework to enable automated design optimization without topological restrictions and on geometries of arbitrary complexity. Also described is another interesting application of Level Sets: their use in guiding the export of a body-conformal mesh from our basic cut-Cartesian background octree - mesh - this permits third party flow solvers to be deployed. As a practical demonstrations meshes of guaranteed quality are generated and flow-solved for a B747 in full landing configuration and an automated optimization is performed on a cooled turbine tip geometry. Copyright © 2009 by W.N.Dawes.

Structured precision modelling with Cholesky basis superposition for speech recognition

Structured precision modelling is an important approach to improve the intra-frame correlation modelling of the standard HMM, where Gaussian mixture model with diagonal covariance are used. Previous work has all been focused on direct structured representation of the precision matrices. In this paper, a new framework is proposed, where the structure of the Cholesky square root of the precision matrix is investigated, referred to as Cholesky Basis Superposition (CBS). Each Cholesky matrix associated with a particular Gaussian distribution is represented as a linear combination of a set of Gaussian independent basis upper-triangular matrices. Efficient optimization methods are derived for both combination weights and basis matrices. Experiments on a Chinese dictation task showed that the proposed approach can significantly outperformed the direct structured precision modelling with similar number of parameters as well as full covariance modelling. © 2011 IEEE.

Automated 3D Structure Inference of Civil Infrastructure Using a Stereo Camera Set

The commercial far-range (>10m) infrastructure spatial data collection methods are not completely automated. They need significant amount of manual post-processing work and in some cases, the equipment costs are significant. This paper presents a method that is the first step of a stereo videogrammetric framework and holds the promise to address these issues. Under this method, video streams are initially collected from a calibrated set of two video cameras. For each pair of simultaneous video frames, visual feature points are detected and their spatial coordinates are then computed. The result, in the form of a sparse 3D point cloud, is the basis for the next steps in the framework (i.e., camera motion estimation and dense 3D reconstruction). A set of data, collected from an ongoing infrastructure project, is used to show the merits of the method. Comparison with existing tools is also shown, to indicate the performance differences of the proposed method in the level of automation and the accuracy of results.

an efficient method to generate feasible paths for basis path testing

Basis path testing is a very powerful structural testing criterion. The number of test paths equals to the cyclomatic complexity of program defined by McCabe. Traditional test generation methods select the paths either without consideration of the constraints of variables or interactively. In this note, an efficient method is presented to generate a set of feasible basis paths. The experiments show that this method can generate feasible basis paths for real-world C programs automatically in acceptable time.

Error-driven active learning in growing radial basis function networks for early robot learning

Q. Meng and M.H. Lee, 'Error-driven active learning in growing radial basis function networks for early robot learning', 2006 IEEE International Conference on Robotics and Automation (IEEE ICRA 2006), 2984-90, Orlando, Florida, USA.

Structural basis for the platelet-collagen interaction - The smallest motif within collagen that recognizes and activates platelet glycoprotein VI contains two glycine-proline-hydroxyproline triplets

Collagen-related peptide is a selective agonist for the platelet collagen receptor Glycoprotein VI. The triple helical peptide contains ten GPO triplets/strand (single letter amino acid nomenclature, where O is hydroxyproline) and so over-represents GPO compared with native collagen sequence. To investigate the ability of Glycoprotein VI to recognize GPO triplets in a setting more representative of the collagens, we synthesized a set of triple helical peptides containing fewer GPO triplets, varying their number and spacing within an inert (GPP)(n) backbone. The adhesion of recombinant human Glycoprotein VI ectodomain, like that of human platelets, to these peptides increased with their GPO content, and platelet adhesion was abolished by the specific anti-Glycoprotein VI-blocking antibody, 10B12. Platelet aggregation and protein tyrosine phosphorylation were induced only by cross-linked peptides and only those that contained two or more GPO triplets. Such peptides were less potent than cross-linked collagen-related peptide. Our data suggest that both the sequences GPOGPO and GPO center dot center dot center dot center dot center dot center dot center dot center dot center dot GPO represent functional Glycoprotein VI recognition motifs within collagen. Furthermore, we propose that the (GPO)(4) motif can support simultaneous binding of two glycoprotein VI molecules, in either a parallel or anti-parallel stacking arrangement, which could play an important role in activation of signaling.

Structural basis for the inhibition of the essential Plasmodium falciparum M1 neutral aminopeptidase

Plasmodium falciparum parasites are responsible for the major global disease malaria, which results in > 2 million deaths each year. With the rise of drug-resistant malarial parasites, novel drug targets and lead compounds are urgently required for the development of new therapeutic strategies. Here, we address this important problem by targeting the malarial neutral aminopeptidases that are involved in the terminal stages of hemoglobin digestion and essential for the provision of amino acids used for parasite growth and development within the erythrocyte. We characterize the structure and substrate specificity of one such aminopeptidase, PfA-M1, a validated drug target. The X-ray crystal structure of PfA-M1 alone and in complex with the generic inhibitor, bestatin, and a phosphinate dipeptide analogue with potent in vitro and in vivo antimalarial activity, hPheP[CH2] Phe, reveals features within the protease active site that are critical to its function as an aminopeptidase and can be exploited for drug development. These results set the groundwork for the development of antimalarial therapeutics that target the neutral aminopeptidases of the parasite.

A novel radial basis function neural network principal component analysis scheme for PMU-based wide-area power system monitoring

A novel model-based principal component analysis (PCA) method is proposed in this paper for wide-area power system monitoring, aiming to tackle one of the critical drawbacks of the conventional PCA, i.e. the incapability to handle non-Gaussian distributed variables. It is a significant extension of the original PCA method which has already shown to outperform traditional methods like rate-of-change-of-frequency (ROCOF). The ROCOF method is quick for processing local information, but its threshold is difficult to determine and nuisance tripping may easily occur. The proposed model-based PCA method uses a radial basis function neural network (RBFNN) model to handle the nonlinearity in the data set to solve the no-Gaussian issue, before the PCA method is used for islanding detection. To build an effective RBFNN model, this paper first uses a fast input selection method to remove insignificant neural inputs. Next, a heuristic optimization technique namely Teaching-Learning-Based-Optimization (TLBO) is adopted to tune the nonlinear parameters in the RBF neurons to build the optimized model. The novel RBFNN based PCA monitoring scheme is then employed for wide-area monitoring using the residuals between the model outputs and the real PMU measurements. Experimental results confirm the efficiency and effectiveness of the proposed method in monitoring a suite of process variables with different distribution characteristics, showing that the proposed RBFNN PCA method is a reliable scheme as an effective extension to the linear PCA method.

Towards Possibilistic Fuzzy Answer Set Programming

Fuzzy answer set programming (FASP) is a generalization of answer set programming to continuous domains. As it can not readily take uncertainty into account, however, FASP is not suitable as a basis for approximate reasoning and cannot easily be used to derive conclusions from imprecise information. To cope with this, we propose an extension of FASP based on possibility theory. The resulting framework allows us to reason about uncertain information in continuous domains, and thus also about information that is imprecise or vague. We propose a syntactic procedure, based on an immediate consequence operator, and provide a characterization in terms of minimal models, which allows us to straightforwardly implement our framework using existing FASP solvers.

Fourier-Matrizen und Ringe mit Basis

Bei der Bestimmung der irreduziblen Charaktere einer Gruppe vom Lie-Typ entwickelte Lusztig eine Theorie, in der eine sogenannte Fourier-Transformation auftaucht. Dies ist eine Matrix, die nur von der Weylgruppe der Gruppe vom Lie-Typ abhängt. Anhand der Eigenschaften, die eine solche Fourier- Matrix erfüllen muß, haben Geck und Malle ein Axiomensystem aufgestellt. Dieses ermöglichte es Broue, Malle und Michel füur die Spetses, über die noch vieles unbekannt ist, Fourier-Matrizen zu bestimmen. Das Ziel dieser Arbeit ist eine Untersuchung und neue Interpretation dieser Fourier-Matrizen, die hoffentlich weitere Informationen zu den Spetses liefert. Die Werkzeuge, die dabei entstehen, sind sehr vielseitig verwendbar, denn diese Matrizen entsprechen gewissen Z-Algebren, die im Wesentlichen die Eigenschaften von Tafelalgebren besitzen. Diese spielen in der Darstellungstheorie eine wichtige Rolle, weil z.B. Darstellungsringe Tafelalgebren sind. In der Theorie der Kac-Moody-Algebren gibt es die sogenannte Kac-Peterson-Matrix, die auch die Eigenschaften unserer Fourier-Matrizen besitzt. Ein wichtiges Resultat dieser Arbeit ist, daß die Fourier-Matrizen, die G. Malle zu den imprimitiven komplexen Spiegelungsgruppen definiert, die Eigenschaft besitzen, daß die Strukturkonstanten der zugehörigen Algebren ganze Zahlen sind. Dazu müssen äußere Produkte von Gruppenringen von zyklischen Gruppen untersucht werden. Außerdem gibt es einen Zusammenhang zu den Kac-Peterson-Matrizen: Wir beweisen, daß wir durch Bildung äußerer Produkte von den Matrizen vom Typ A(1)1 zu denen vom Typ C(1) l gelangen. Lusztig erkannte, daß manche seiner Fourier-Matrizen zum Darstellungsring des Quantendoppels einer endlichen Gruppe gehören. Deswegen ist es naheliegend zu versuchen, die noch ungeklärten Matrizen als solche zu identifizieren. Coste, Gannon und Ruelle untersuchen diesen Darstellungsring. Sie stellen eine Reihe von wichtigen Fragen. Eine dieser Fragen beantworten wir, nämlich inwieweit rekonstruiert werden kann, zu welcher endlichen Gruppe gegebene Matrizen gehören. Den Darstellungsring des getwisteten Quantendoppels berechnen wir für viele Beispiele am Computer. Dazu müssen unter anderem Elemente aus der dritten Kohomologie-Gruppe H3(G,C×) explizit berechnet werden, was bisher anscheinend in noch keinem Computeralgebra-System implementiert wurde. Leider ergibt sich hierbei kein Zusammenhang zu den von Spetses herrührenden Matrizen. Die Werkzeuge, die in der Arbeit entwickelt werden, ermöglichen eine strukturelle Zerlegung der Z-Ringe mit Basis in bekannte Anteile. So können wir für die meisten Matrizen der Spetses Konstruktionen angeben: Die zugehörigen Z-Algebren sind Faktorringe von Tensorprodukten von affinen Ringe Charakterringen und von Darstellungsringen von Quantendoppeln.