Computational Consequences of Agreement and Ambiguity in Natural Language

The computer science technique of computational complexity analysis can provide powerful insights into the algorithm-neutral analysis of information processing tasks. Here we show that a simple, theory-neutral linguistic model of syntactic agreement and ambiguity demonstrates that natural language parsing may be computationally intractable. Significantly, we show that it may be syntactic features rather than rules that can cause this difficulty. Informally, human languages and the computationally intractable Satisfiability (SAT) problem share two costly computional mechanisms: both enforce agreement among symbols across unbounded distances (Subject-Verb agreement) and both allow ambiguity (is a word a Noun or a Verb?).

Incremental Verification of Timing Constraints for Real-Time Systems

Testing constraints for real-time systems are usually verified through the satisfiability of propositional formulae. In this paper, we propose an alternative where the verification of timing constraints can be done by counting the number of truth assignments instead of boolean satisfiability. This number can also tell us how “far away” is a given specification from satisfying its safety assertion. Furthermore, specifications and safety assertions are often modified in an incremental fashion, where problematic bugs are fixed one at a time. To support this development, we propose an incremental algorithm for counting satisfiability. Our proposed incremental algorithm is optimal as no unnecessary nodes are created during each counting. This works for the class of path RTL. To illustrate this application, we show how incremental satisfiability counting can be applied to a well-known rail-road crossing example, particularly when its specification is still being refined.

Over Expression of the CMP-sialic Acid Transporter in Chinese Hamster Ovary Cells Leads to Increased Sialylation

Most glyco-engineering approaches used to improve quality of recombinant glycoproteins involve the manipulation of glycosyltransferase and/or glycosidase expression. We investigated whether the over expression of nucleotide sugar transporters, particularly the CMP-sialic acid transporter (CMP-SAT), would be a means to improve the sialylation process in CHO cells. We hypothesized that increasing the expression of the CMP-SAT in the cells would increase the transport of the CMP-sialic acid in the Golgi lumen, hence increasing the intra-lumenal CMP-sialic acid pool, and resulting in a possible increase in sialylation extent of proteins being produced. We report the construction of a CMP-SAT expression vector which was used for transfection into CHO-IFNγ, a CHO cell line producing human IFNγ. This resulted in approximately 2 to 5 times increase in total CMP-SAT expression in some of the positive clones as compared to untransfected CHO-IFNγ, as determined using real-time PCR analysis. This in turn concurred with a 9.6% to 16.3% percent increase in site sialylation. This engineering approach has thus been identified as a novel means of improving sialylation in recombinant glycoprotein therapeutics. This strategy can be utilized feasibly on its own, or in combination with existing sialylation improvement strategies. It is believed that such multi-prong approaches are required to effectively manipulate the complex sialylation process, so as to bring us closer to the goal of producing recombinant glycoproteins of high and consistent sialylation from mammalian cells.