Contributions to the Theory of Finite-State Based Grammars

This dissertation is a theoretical study of finite-state based grammars used in natural language processing. The study is concerned with certain varieties of finite-state intersection grammars (FSIG) whose parsers define regular relations between surface strings and annotated surface strings. The study focuses on the following three aspects of FSIGs: (i) Computational complexity of grammars under limiting parameters In the study, the computational complexity in practical natural language processing is approached through performance-motivated parameters on structural complexity. Each parameter splits some grammars in the Chomsky hierarchy into an infinite set of subset approximations. When the approximations are regular, they seem to fall into the logarithmic-time hierarchyand the dot-depth hierarchy of star-free regular languages. This theoretical result is important and possibly relevant to grammar induction. (ii) Linguistically applicable structural representations Related to the linguistically applicable representations of syntactic entities, the study contains new bracketing schemes that cope with dependency links, left- and right branching, crossing dependencies and spurious ambiguity. New grammar representations that resemble the Chomsky-Schützenberger representation of context-free languages are presented in the study, and they include, in particular, representations for mildly context-sensitive non-projective dependency grammars whose performance-motivated approximations are linear time parseable. (iii) Compilation and simplification of linguistic constraints Efficient compilation methods for certain regular operations such as generalized restriction are presented. These include an elegant algorithm that has already been adopted as the approach in a proprietary finite-state tool. In addition to the compilation methods, an approach to on-the-fly simplifications of finite-state representations for parse forests is sketched. These findings are tightly coupled with each other under the theme of locality. I argue that the findings help us to develop better, linguistically oriented formalisms for finite-state parsing and to develop more efficient parsers for natural language processing. Avainsanat: syntactic parsing, finite-state automata, dependency grammar, first-order logic, linguistic performance, star-free regular approximations, mildly context-sensitive grammars

U12-type Spliceosome: Localization and Effects of Splicing Efficiency on Gene Expression

The removal of non-coding sequences, introns, is an essential part of messenger RNA processing. In most metazoan organisms, the U12-type spliceosome processes a subset of introns containing highly conserved recognition sequences. U12-type introns constitute less than 0,5% of all introns and reside preferentially in genes related to information processing functions, as opposed to genes encoding for metabolic enzymes. It has previously been shown that the excision of U12-type introns is inefficient compared to that of U2-type introns, supporting the model that these introns could provide a rate-limiting control for gene expression. The low efficiency of U12-type splicing is believed to have important consequences to gene expression by limiting the production of mature mRNAs from genes containing U12-type introns. The inefficiency of U12-type splicing has been attributed to the low abundance of the components of the U12-type spliceosome in cells, but this hypothesis has not been proven. The aim of the first part of this work was to study the effect of the abundance of the spliceosomal snRNA components on splicing. Cells with a low abundance of the U12-type spliceosome were found to inefficiently process U12-type introns encoded by a transfected construct, but the expression levels of endogenous genes were not found to be affected by the abundance of the U12-type spliceosome. However, significant levels of endogenous unspliced U12-type intron-containing pre-mRNAs were detected in cells. Together these results support the idea that U12-type splicing may limit gene expression in some situations. The inefficiency of U12-type splicing has also promoted the idea that the U12-type spliceosome may control gene expression, limiting the mRNA levels of some U12-type intron-containing genes. While the identities of the primary target genes that contain U12-type introns are relatively well known, little has previously been known about the downstream genes and pathways potentially affected by the efficiency of U12-type intron processing. Here, the effects of U12-type splicing efficiency on a whole organism were studied in a Drosophila line with a mutation in an essential U12-type spliceosome component. Genes containing U12-type introns showed variable gene-specific responses to the splicing defect, which points to variation in the susceptibility of different genes to changes in splicing efficiency. Surprisingly, microarray screening revealed that metabolic genes were enriched among downstream effects, and that the phenotype could largely be attributed to one U12-type intron-containing mitochondrial gene. Gene expression control by the U12-type spliceosome could thus have widespread effects on metabolic functions in the organism. The subcellular localization of the U12-type spliceosome components was studied as a response to a recent dispute on the localization of the U12-type spliceosome. All components studied were found to be nuclear indicating that the processing of U12-type introns occurs within the nucleus, thus clarifying a question central to the field. The results suggest that the U12-type spliceosome can limit the expression of genes that contain U12-type introns in a gene-specific manner. Through its limiting role in pre-mRNA processing, the U12-type splicing activity can affect specific genetic pathways, which in the case of Drosophila are involved in metabolic functions.

Antioxidants, weight change and risk of type 2 diabetes

The incidence of type 2 diabetes has increased rapidly worldwide. Obesity is one of the most important modifiable risk factors of type 2 diabetes: weight gain increases and weight loss decreases the risk. However, the effects of weight fluctuation are unclear. Reactive oxygen species are presumably part of the complicated mechanism for the development of insulin resistance and beta-cell destruction in the pancreas. The association of antioxidants with the risk of incident type 2 diabetes has been studied in longitudinal prospective human studies, but so far there is no clear conclusion about protective effect of dietary or of supplementary antioxidants on diabetes risk. The present study examined 1) weight change and fluctuation as risk factors for incident type 2 diabetes; 2) the association of baseline serum alpha-tocopherol or beta-carotene concentration and dietary intake of antioxidants with the risk of type 2 diabetes; 3) the effect of supplementation with alpha-tocopherol or beta-carotene on the risk of incident type 2 diabetes; and on macrovascular complications and mortality among type 2 diabetics. This investigation was part of the Alpha-Tocopherol, Beta-Carotene Cancer Prevention (ATBC) Study, a randomized, double-blind, placebo-controlled prevention trial, which has undertaken to examine the effect of alpha-tocopherol and beta-carotene supplementation on the development of lung cancer, other cancers, and cardiovascular diseases in male smokers aged 50-69 years at baseline. Participants were assigned to receive either 50 mg alpha-tocopherol, 20mg beta-carotene, both, or placebo daily in a 2 x 2 factorial design experiment during 1985-1993. Cases of incident diabetes were identified through a nationwide register of drug reimbursements of the Social Insurance Institution. At baseline 1700 men had a history of diabetes. Among those (n = 27 379) with no diabetes at baseline 305 new cases of type 2 diabetes were recognized during the intervention period and 705 during the whole follow-up to 12.5 years. Weight gain and weight fluctuation measured over a three year period were independent risk factors for subsequent incident type 2 diabetes. Relative risk (RR) was 1.77 (95% confidence interval [CI] 1.44-2.17) for weight gain of at least 4 kg compared to those with a weight change of less than 4 kg. The RR in the highest weight fluctuation quintile compared to the lowest was 1.64 (95% CI 1.24-2.17). Dietary tocopherols and tocotrienols as well as dietary carotenoids, flavonols, flavones and vitamin C were not associated with the risk of type 2 diabetes. Baseline serum alpha-tocopherol and beta-carotene concentrations were not associated with the risk of incident diabetes. Neither alpha-tocopherol nor beta-carotene supplementation affected the risk of diabetes. The relative risks for participants who received alpha-tocopherol compared with nonrecipients and for participants who received beta-carotene compared with nonrecipients were 0.92 (95% CI 0.79-1.07) and 0.99 (95% CI 0.85-1.15), respectively. Furthermore, alpha-tocopherol or beta-carotene supplementation did not affect the risk of macrovascular complications or mortality of diabetic subjects during the 19 years follow-up time. In conclusion, in this study of older middle-aged male smokers, weight gain and weight fluctuation were independent risk factors for type 2 diabetes. Intake of antioxidants or serum alpha-tocopherol or beta-carotene concentrations were not associated with the risk of type 2 diabetes. Supplementation with of alpha-tocopherol or beta-carotene did not prevent type 2 diabetes. Neither did they prevent macrovascular complications, or mortality among diabetic subjects.