1,720,972 research outputs found
Onthe shape of permutomino tiles
No full textIn this paper we explore the connections between two classes of polyominoes, namely the permutominoes and the pseudo-square polyominoes. A permutomino is a polyomino uniquely determined by a pair of permutations. Permutominoes, and in particular convex permutominoes, have been considered in various kinds of problems such as: enumeration, tomographical reconstruction, and algebraic characterization. On the other hand, pseudo-square polyominoes are a class of polyominoes tiling the plane by translation. The characterization of such objects has been given by Beauquier and Nivat, who proved that a polyomino tiles the plane by translation if and only if it is a pseudo-square or a pseudo-hexagon. In particular, a polyomino is pseudo-square if its boundary word may be factorized as XYX̂, where Xî denotes the path X traveled in the opposite direction. In this paper we relate the two concepts by considering the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XYX̂ is pseudo-square is prefix of a unique infinite word Y with period 4|X|N|X|E. Also, we show that XYX̂ are centrosymmetric, i.e. they are fixed by rotation of angle π. The proof of this fact is based on the concept of pseudoperiods, a natural generalization of periods. © 2012 Elsevier B.V. All rights reserved
Further steps on the reconstruction of convex polyominoes from orthogonal projections
Full text linkA remarkable family of discrete sets which has recently attracted the attention of the discrete geometry community is the family of convex polyominoes, that are the discrete counterpart of Euclidean convex sets, and combine the constraints of convexity and connectedness. In this paper we study the problem of their reconstruction from orthogonal projections, relying on the approach defined by Barcucci et al. (Theor Comput Sci 155(2):321–347, 1996). In particular, during the reconstruction process it may be necessary to expand a convex subset of the interior part of the polyomino, say the polyomino kernel, by adding points at specific positions of its contour, without losing its convexity. To reach this goal we consider convexity in terms of certain combinatorial properties of the boundary word encoding the polyomino. So, we first show some conditions that allow us to extend the kernel maintaining the convexity. Then, we provide examples where the addition of one or two points causes a loss of convexity, which can be restored by adding other points, whose number and positions cannot be determined a priori
An algebraic approach to the reconstruction of uniform hypergraphs from their degree sequence
Full text linkThe reconstruction of a (hyper)graph starting from its degree sequence is one of the most relevant among the inverse problems investigated in the field of graph theory. In case of graphs, a feasible solution can be quickly reached, while in case of hypergraphs Deza et al. (2018) proved that the problem is NP-hard even in the simple case of 3-uniform ones. This result opened a new research line consisting in the detection of instances for which a solution can be computed in polynomial time. In this work we deal with 3-uniform hypergraphs, and we study them from a different perspective, exploiting a connection of these objects with partially ordered sets. More precisely, we introduce a simple partially ordered set, whose ideals are in bijection with a subclass of 3-uniform hypergraphs. We completely characterize their degree sequences in case of principal ideals (here a simple fast reconstruction strategy follows), and we furthermore carry on a complete analysis of those degree sequences related to the ideals with two generators. We also consider unique hypergraphs in Dext, i.e., those hypergraphs that do not share their degree sequence with other non-isomorphic ones. We show that uniqueness holds in case of hypergraphs associated to principal ideals, and we provide some examples of hypergraphs in Dext where this property is lost
Connected Component Analysis of Dynamical Perturbation Contact Networks
Full text linkDescribing protein dynamical networks through amino acid contacts is a powerful way to analyze complex biomolecular systems. However, due to the size of the systems, identifying the relevant features of protein-weighted graphs can be a difficult task. To address this issue, we present the connected component analysis (CCA) approach that allows for fast, robust, and unbiased analysis of dynamical perturbation contact networks (DPCNs). We first illustrate the CCA method as applied to a prototypical allosteric enzyme, the imidazoleglycerol phosphate synthase (IGPS) enzyme from Thermotoga maritima bacteria. This approach was shown to outperform the clustering methods applied to DPCNs, which could not capture the propagation of the allosteric signal within the protein graph. On the other hand, CCA reduced the DPCN size, providing connected components that nicely describe the allosteric propagation of the signal from the effector to the active sites of the protein. By applying the CCA to the IGPS enzyme in different conditions, i.e., at high temperature and from another organism (yeast IGPS), and to a different enzyme, i.e., a protein kinase, we demonstrated how CCA of DPCNs is an effective and transferable tool that facilitates the analysis of protein-weighted networks
Tiling the plane with permutations
No full textA permutomino is a polyomino uniquely determined by a pair of permutations. Recently permutominoes, and in particular convex permutominoes have been studied by several authors concerning their analytical and bijective enumeration; tomographical reconstruction, and the algebraic characterization of the associated permutations [2,3]. On the other side, Beauquier and Nivat [5] introduced and gave a characterization of the class of pseudo-square polyominoes, i.e. polyominoes that tile the plane by translation: a polyomino is called pseudo-square if its boundary word may be factorized as XYX (X) over bar(Y) over bar. In this paper we consider the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XY (X) over bar(Y) over bar is pseudo-square is prefix of an infinite word Y-infinity with period 4 vertical bar X vertical bar(N)vertical bar X vertical bar(E). Some conjectures obtained through exhaustive search are also presented and discussed in the final section
Elucidating the Activation Mechanism of AMPK by Direct Pan-Activator PF-739
Full text linkAdenosine monophosphate-activated protein kinase (AMPK) is a key energy sensor regulating the cell metabolism in response to energy supply and demand. The evolutionary adaptation of AMPK to different tissues is accomplished through the expression of distinct isoforms that can form up to 12 heterotrimeric complexes, which exhibit notable differences in the sensitivity to direct activators. To comprehend the molecular factors of the activation mechanism of AMPK, we have assessed the changes in the structural and dynamical properties of β1- and β2-containing AMPK complexes formed upon binding to the pan-activator PF-739. The analysis revealed the molecular basis of the PF-739-mediated activation of AMPK and enabled us to identify distinctive features that may justify the slightly higher affinity towards the β1−isoform, such as the β1−Asn111 to β2−Asp111 substitution, which seems to be critical for modulating the dynamical sensitivity of β1- and β2 isoforms. The results are valuable in the design of selective activators to improve the tissue specificity of therapeutic treatment
Exploring Allosteric Pathways of a V-Type Enzyme with Dynamical Perturbation Networks
No full textElucidation of the allosteric pathways in proteins is a computational challenge that strongly benefits from combination of atomistic molecular dynamics (MD) simulations and coarse-grained analysis of the complex dynamical network of chemical interactions based on graph theory. Here, we introduce and assess the performances of the dynamical perturbation network analysis of allosteric pathways in a prototypical V-type allosteric enzyme. Dynamical atomic contacts obtained from MD simulations are used to weight the allosteric protein graph, which involves an extended network of contacts perturbed by the effector binding in the allosteric site. The outcome showed good agreement with previously reported theoretical and experimental extended studies and it provided recognition of new potential allosteric spots that can be exploited in future mutagenesis experiments. Overall, the dynamical perturbation network analysis proved to be a powerful computational tool, complementary to other network-based approaches that can assist the full exploitation of allosteric phenomena for advances in protein engineering and rational drug design
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
