Browsing by Subject "REFINEMENT"

Sort by: Order: Results:

Now showing items 1-5 of 5
  • Baumeister, Dorothea; Järvisalo, Matti; Neugebauer, Daniel; Niskanen, Andreas; Rothe, Jörg (2021)
    A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.
  • De Colibus, Luigi; Roine, Elina; Walter, Thomas S.; Ilca, Serban L.; Wang, Xiangxi; Wang, Nan; Roseman, Alan M.; Bamford, Dennis; Huiskonen, Juha T.; Stuart, David (2019)
    Many of the largest known viruses belong to the PRD1-adeno structural lineage characterised by conserved pseudo-hexameric capsomers composed of three copies of a single major capsid protein (MCP). Here, by high-resolution cryo-EM analysis, we show that a class of archaeal viruses possess hetero-hexameric MCPs which mimic the PRD1-adeno lineage trimer. These hetero-hexamers are built from heterodimers and utilise a jigsaw-puzzle system of pegs and holes, and underlying minor capsid proteins, to assemble the capsid laterally from the 5-fold vertices. At these vertices proteins engage inwards with the internal membrane vesicle whilst 2-fold symmetric horn-like structures protrude outwards. The horns are assembled from repeated globular domains attached to a central spine, presumably facilitating multimeric attachment to the cell receptor. Such viruses may represent precursors of the main PRD1-adeno lineage, similarly engaging cell-receptors via 5-fold spikes and using minor proteins to define particle size.
  • Oliinyk, Olena S.; Shemetov, Anton A.; Pletnev, Sergei; Shcherbakova, Daria M.; Verkhusha, Vladislav V. (2019)
    From a single domain of cyanobacteriochrome (CBCR) we developed a near-infrared (NIR) fluorescent protein (FP), termed miRFP670nano, with excitation at 645 nm and emission at 670 nm. This is the first CBCR-derived NIR FP evolved to efficiently bind endogenous biliverdin chromophore and brightly fluoresce in mammalian cells. miRFP670nano is a monomer with molecular weight of 17 kDa that is 2-fold smaller than bacterial phytochrome (BphP)-based NIR FPs and 1.6-fold smaller than GFP-like FPs. Crystal structure of the CBCR-based NIR FP with biliverdin reveals a molecular basis of its spectral and biochemical properties. Unlike BphP-derived NIR FPs, miRFP670nano is highly stable to denaturation and degradation and can be used as an internal protein tag. miRFP670nano is an effective FRET donor for red-shifted NIR FPs, enabling engineering NIR FRET biosensors spectrally compatible with GFP-like FPs and blue-green optogenetic tools. miRFP670nano unlocks a new source of diverse CBCR templates for NIR FPs.
  • Karki, Sudeep; Shkumatov, Alexander V.; Bae, Sungwon; Kim, Hyeonho; Ko, Jaewon; Kajander, Tommi (2020)
    Synaptic adhesion molecules play an important role in the formation, maintenance and refinement of neuronal connectivity. Recently, several leucine rich repeat (LRR) domain containing neuronal adhesion molecules have been characterized including netrin G-ligands, SLITRKs and the synaptic adhesion-like molecules (SALMs). Dysregulation of these adhesion molecules have been genetically and functionally linked to various neurological disorders. Here we investigated the molecular structure and mechanism of ligand interactions for the postsynaptic SALM3 adhesion protein with its presynaptic ligand, receptor protein tyrosine phosphatase sigma (PTP sigma). We solved the crystal structure of the dimerized LRR domain of SALM3, revealing the conserved structural features and mechanism of dimerization. Furthermore, we determined the complex structure of SALM3 with PTP sigma using small angle X-ray scattering, revealing a 2:2 complex similar to that observed for SALM5. Solution studies unraveled additional flexibility for the complex structure, but validated the uniform mode of action for SALM3 and SALM5 to promote synapse formation. The relevance of the key interface residues was further confirmed by mutational analysis with cellular binding assays and artificial synapse formation assays. Collectively, our results suggest that SALM3 dimerization is a pre-requisite for the SALM3-PTP sigma complex to exert synaptogenic activity.
  • Beyer, Hannes M.; Virtanen, Salla; Aranko, A. Sesilja; Mikula, Kornelia M.; Lountos, George T.; Wlodawer, Alexander; Ollila, O.H. Samuli; Iwai, Hideo (2020)
    Protein splicing catalyzed by inteins utilizes many different combinations of amino-acid types at active sites. Inteins have been classified into three classes based on their characteristic sequences. We investigated the structural basis of the protein splicing mechanism of class 3 inteins by determining crystal structures of variants of a class 3 intein from Mycobacterium chimaera and molecular dynamics simulations, which suggested that the class 3 intein utilizes a different splicing mechanism from that of class 1 and 2 inteins. The class 3 intein uses a bond cleavage strategy reminiscent of proteases but share the same Hedgehog/INTein (HINT) fold of other intein classes. Engineering of class 3 inteins from a class 1 intein indicated that a class 3 intein would unlikely evolve directly from a class 1 or 2 intein. The HINT fold appears as structural and functional solution for trans-peptidyl and trans-esterification reactions commonly exploited by diverse mechanisms using different combinations of amino-acid types for the active-site residues.