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

Feature integration in human vision

The earliest stages of human cortical visual processing can be conceived as extraction of local stimulus features. However, more complex visual functions, such as object recognition, require integration of multiple features. Recently, neural processes underlying feature integration in the visual system have been under intensive study. A specialized mid-level stage preceding the object recognition stage has been proposed to account for the processing of contours, surfaces and shapes as well as configuration. This thesis consists of four experimental, psychophysical studies on human visual feature integration. In two studies, classification image a recently developed psychophysical reverse correlation method was used. In this method visual noise is added to near-threshold stimuli. By investigating the relationship between random features in the noise and observer s perceptual decision in each trial, it is possible to estimate what features of the stimuli are critical for the task. The method allows visualizing the critical features that are used in a psychophysical task directly as a spatial correlation map, yielding an effective "behavioral receptive field". Visual context is known to modulate the perception of stimulus features. Some of these interactions are quite complex, and it is not known whether they reflect early or late stages of perceptual processing. The first study investigated the mechanisms of collinear facilitation, where nearby collinear Gabor flankers increase the detectability of a central Gabor. The behavioral receptive field of the mechanism mediating the detection of the central Gabor stimulus was measured by the classification image method. The results show that collinear flankers increase the extent of the behavioral receptive field for the central Gabor, in the direction of the flankers. The increased sensitivity at the ends of the receptive field suggests a low-level explanation for the facilitation. The second study investigated how visual features are integrated into percepts of surface brightness. A novel variant of the classification image method with brightness matching task was used. Many theories assume that perceived brightness is based on the analysis of luminance border features. Here, for the first time this assumption was directly tested. The classification images show that the perceived brightness of both an illusory Craik-O Brien-Cornsweet stimulus and a real uniform step stimulus depends solely on the border. Moreover, the spatial tuning of the features remains almost constant when the stimulus size is changed, suggesting that brightness perception is based on the output of a single spatial frequency channel. The third and fourth studies investigated global form integration in random-dot Glass patterns. In these patterns, a global form can be immediately perceived, if even a small proportion of random dots are paired to dipoles according to a geometrical rule. In the third study the discrimination of orientation structure in highly coherent concentric and Cartesian (straight) Glass patterns was measured. The results showed that the global form was more efficiently discriminated in concentric patterns. The fourth study investigated how form detectability depends on the global regularity of the Glass pattern. The local structure was either Cartesian or curved. It was shown that randomizing the local orientation deteriorated the performance only with the curved pattern. The results give support for the idea that curved and Cartesian patterns are processed in at least partially separate neural systems.

The influence of HIV infection to the periodontium; a clinical, microbiological, and enzymological study

The main targets of human immunodeficiency virus (HIV) are CD4 receptors of CD4+ lymphocytes and many other cells such as monocytes/macrophages, megakaryocytes, peripheral blood dendritic cells, follicular dendritic cells (DC), epidermal Langerhans cells, and astrocytes. Infection and killing of CD4+ lymphocytes or false reaction of the body to HIV infection and the spontaneous apoptosis of CD4+ lymphocytes decrease CD4+ lymphocyte counts leading to immunosuppression, further disease progression, and appearance of opportunistic infections and malignancies. Oral manifestations are considered to be among the first signs of HIV infection. Enhanced degradation of extracellular matrix and basement membrane components in oral diseases including periodontitis is caused by Zn-dependent enzymes called matrix metalloproteinases (MMPs). The levels and degrees of activation of MMP-1, -2, -3, -7, -8, -9, -25, -26, tissue inhibitors of MMPs (TIMP)-1 and -2, and myeloperoxidase (MPO) and collagenolytic/gelatinolytic activities, and also Ig A, -G, and -M, total protein, and albumin levels in a two-year follow-up were studied from salivary samples. The expression of MMP-7, -8, -9, -25, and -26 immunoreactivities in gingival tissue specimens were studied. Healthy HIV-negative subjects served as controls. All studied clinical periodontal parameters and microbiological evaluation of the periodontopathogens showed that periodontal health of the HIV-positive patients was moderately decreased in comparison to the healthy controls. The levels of Candida in the periodontal pockets and salivary MPO increased with the severity of HIV infection. Immunoreactivities and levels of MMPs and TIMPs, and MMP activities (collagenase, gelatinase) were enhanced in the HIV-positive patient salivary samples relative to the healthy controls regardless of the phase of HIV infection. However, these parameters did not reflect periodontal status in a similar way as in the generally healthy periodontitis patients. Salivary total protein, albumin, IgA, -G, and -M levels were significantly higher in all phases of HIV infection compared to the controls, and salivary total protein, IgG and IgM levels remained higher after two years follow-up, partly correlating with the disease progression and which may reflect the leakage of serum components into the mouth and thus a decreased mucosal barrier. Salivary analyses of MMPs and TIMPs with immunohistochemical analyses showed that HIV infection could predispose to periodontal destruction when compared with healthy controls or the body s defence reactions associated with HIV infection may have been reflected or mediated by MMPs.

Rhizoctonia -Scots pine interactions: detection, impact on seedling performance and host defence gene response

Rhizoctonia spp. are ubiquitous soil inhabiting fungi that enter into pathogenic or symbiotic associations with plants. In general Rhizoctonia spp. are regarded as plant pathogenic fungi and many cause root rot and other plant diseases which results in considerable economic losses both in agriculture and forestry. Many Rhizoctonia strains enter into symbiotic mycorrhizal associations with orchids and some hypovirulent strains are promising biocontrol candidates in preventing host plant infection by pathogenic Rhizoctonia strains. This work focuses on uni- and binucleate Rhizoctonia (respectively UNR and BNR) strains belonging to the teleomorphic genus Ceratobasidium, but multinucleate Rhizoctonia (MNR) belonging to teleomorphic genus Thanatephorus and ectomycorrhizal fungal species, such as Suillus bovinus, were also included in DNA probe development work. Strain specific probes were developed to target rDNA ITS (internal transcribed spacer) sequences (ITS1, 5.8S and ITS2) and applied in Southern dot blot and liquid hybridization assays. Liquid hybridization was more sensitive and the size of the hybridized PCR products could be detected simultaneously, but the advantage in Southern hybridization was that sample DNA could be used without additional PCR amplification. The impacts of four Finnish BNR Ceratorhiza sp. strains 251, 266, 268 and 269 were investigated on Scot pine (Pinus sylvestris) seedling growth, and the infection biology and infection levels were microscopically examined following tryphan blue staining of infected roots. All BNR strains enhanced early seedling growth and affected the root architecture, while the infection levels remained low. The fungal infection was restricted to the outer cortical regions of long roots and typical monilioid cells detected with strain 268. The interactions of pathogenic UNR Ceratobasidium bicorne strain 1983-111/1N, and endophytic BNR Ceratorhiza sp. strain 268 were studied in single or dual inoculated Scots pine roots. The fungal infection levels and host defence-gene activity of nine transcripts [phenylalanine ammonia lyase (pal1), silbene synthase (STS), chalcone synthase (CHS), short-root specific peroxidase (Psyp1), antimicrobial peptide gene (Sp-AMP), rapidly elicited defence-related gene (PsACRE), germin-like protein (PsGER1), CuZn- superoxide dismutase (SOD), and dehydrin-like protein (dhy-like)] were measured from differentially treated and un-treated control roots by quantitative real time PCR (qRT-PCR). The infection level of pathogenic UNR was restricted in BNR- pre-inoculated Scots pine roots, while UNR was more competitive in simultaneous dual infection. The STS transcript was highly up-regulated in all treated roots, while CHS, pal1, and Psyp1 transcripts were more moderately activated. No significant activity of Sp-AMP, PsACRE, PsGER1, SOD, or dhy-like transcripts were detected compared to control roots. The integrated experiments presented, provide tools to assist in the future detection of these fungi in the environment and to understand the host infection biology and defence, and relationships between these interacting fungi in roots and soils. This study further confirms the complexity of the Rhizoctonia group both phylogenetically and in their infection biology and plant host specificity. The knowledge obtained could be applied in integrated forestry nursery management programmes.

Functional genes and gene array analysis as tools for monitoring hydrocarbon biodegradation

Bioremediation, which is the exploitation of the intrinsic ability of environmental microbes to degrade and remove harmful compounds from nature, is considered to be an environmentally sustainable and cost-effective means for environmental clean-up. However, a comprehensive understanding of the biodegradation potential of microbial communities and their response to decontamination measures is required for the effective management of bioremediation processes. In this thesis, the potential to use hydrocarbon-degradative genes as indicators of aerobic hydrocarbon biodegradation was investigated. Small-scale functional gene macro- and microarrays targeting aliphatic, monoaromatic and low molecular weight polyaromatic hydrocarbon biodegradation were developed in order to simultaneously monitor the biodegradation of mixtures of hydrocarbons. The validity of the array analysis in monitoring hydrocarbon biodegradation was evaluated in microcosm studies and field-scale bioremediation processes by comparing the hybridization signal intensities to hydrocarbon mineralization, real-time polymerase chain reaction (PCR), dot blot hybridization and both chemical and microbiological monitoring data. The results obtained by real-time PCR, dot blot hybridization and gene array analysis were in good agreement with hydrocarbon biodegradation in laboratory-scale microcosms. Mineralization of several hydrocarbons could be monitored simultaneously using gene array analysis. In the field-scale bioremediation processes, the detection and enumeration of hydrocarbon-degradative genes provided important additional information for process optimization and design. In creosote-contaminated groundwater, gene array analysis demonstrated that the aerobic biodegradation potential that was present at the site, but restrained under the oxygen-limited conditions, could be successfully stimulated with aeration and nutrient infiltration. During ex situ bioremediation of diesel oil- and lubrication oil-contaminated soil, the functional gene array analysis revealed inefficient hydrocarbon biodegradation, caused by poor aeration during composting. The functional gene array specifically detected upper and lower biodegradation pathways required for complete mineralization of hydrocarbons. Bacteria representing 1 % of the microbial community could be detected without prior PCR amplification. Molecular biological monitoring methods based on functional genes provide powerful tools for the development of more efficient remediation processes. The parallel detection of several functional genes using functional gene array analysis is an especially promising tool for monitoring the biodegradation of mixtures of hydrocarbons.

Prognostic markers in head and neck carcinoma

Head and neck squamous cell carcinoma (HNSCC) is the sixth most common cancer worldwide. Well-known risk factors include tobacco smoking and alcohol consumption. Overall survival has improved, but is still low especially in developing countries. One reason for this is the often advanced stage of the disease at the time of diagnosis, but also lack of reliable prognostic tools to enable individualized patient treatment to improve outcome. To date, the TNM classification still serves as the best disease evaluation criterion, although it does not take into account the molecular basis of the tumor. The need for surrogate molecular markers for more accurate disease prediction has increased research interests in this field. We investigated the prevalence, physical status, and viral load of human papillomavirus (HPV) in HNSCC to determine the impact of HPV on head and neck carcinogenesis. The prevalence and genotyping of HPV were assessed with an SPF10 PCR microtiter plate-based hybridization assay (DEIA), followed by a line probe-based genotyping assay. More than half of the patients had HPV DNA in their tumor specimens. Oncogenic HPV-16 was the most common type, and coinfections with other oncogenic and benign associated types also existed. HPV-16 viral load was unevenly distributed among different tumor sites; the tonsils harbored significantly greater amounts of virus than other sites. Episomal location of HPV-16 was associated with large tumors, and both integrated and mixed forms of viral DNA were detected. In this series, we could not show that the presence of HPV DNA correlated with survival. In addition, we investigated the prevalence and genotype of HPV in laryngeal carcinoma patients in a prospective Nordic multicenter study based on fresh-frozen laryngeal tumor samples to determine whether the tumors were HPV-associated. These patients were also examined and interviewed at diagnosis for known risk factors, such as tobacco smoking and alcohol consumption, and for several other habituations to elucidate their effects on patient survival. HPV analysis was performed with the same protocols as in the first study. Only 4% of the specimens harbored HPV DNA. Heavy drinking was associated with poor survival. Heavy drinking patients were also younger than nonheavy drinkers and had a more advanced stage of disease at diagnosis. Heavy drinkers had worse oral hygiene than nonheavy drinkers; however, poor oral hygiene did not have prognostic significance. History of chronic laryngitis, gastroesophageal reflux disease, and orogenital sex contacts were rare in this series. To clarify why vocal cord carcinomas seldom metastasize, we determined tumor lymph vessel (LVD) and blood vessel (BVD) densities in HNSCC patients. We used a novel lymphatic vessel endothelial marker (LYVE-1 antibody) to locate the lymphatic vessels in HNSCC samples and CD31 to detect the blood microvessels. We found carcinomas of the vocal cords to harbor less lymphatic and blood microvessels than carcinomas arising from sites other than vocal cords. The lymphatic and blood microvessel densities did not correlate with tumor size. High BVD was strongly correlated with high LVD. Neither BVD nor LVD showed any association with survival in our series. The immune system plays an important role in tumorigenesis, as neoplastic cells have to escape the cytotoxic lymphocytes in order to survive. Several candidate HLA class II alleles have been reported to be prognostic in cervical carcinomas, an epithelial malignancy resembling HNSCC. These alleles may have an impact on head and neck carcinomas as well. We determined HLA-DRB1* and -DQB1* alleles in HNSCC patients. Healthy organ donors served as controls. The Inno-LiPA reverse dot-blot kit was used to identify alleles in patient samples. No single haplotype was found to be predictive of either the risk for head and neck cancer, or the clinical course of the disease. However, alleles observed to be prognostic in cervical carcinomas showed a similar tendency in our series. DRB1*03 was associated with node-negative disease at diagnosis. DRB1*08 and DRB1*13 were associated with early-stage disease; DRB1*04 had a lower risk for tumor relapse; and DQB1*03 and DQB1*0502 were more frequent in controls than in patients. However, these associations reached only borderline significance in our HNSCC patients.

Excimer laser refractive surgery : corneal wound healing and clinical results

Although the first procedure in a seeing human eye using excimer laser was reported in 1988 (McDonald et al. 1989, O'Connor et al. 2006) just three studies (Kymionis et al. 2007, O'Connor et al. 2006, Rajan et al. 2004) with a follow-up over ten years had been published when this thesis was started. The present thesis aims to investigate 1) the long-term outcomes of excimer laser refractive surgery performed for myopia and/or astigmatism by photorefractive keratectomy (PRK) and laser-in situ- keratomileusis (LASIK), 2) the possible differences in postoperative outcomes and complications when moderate-to-high astigmatism is treated with PRK or LASIK, 3) the presence of irregular astigmatism that depend exclusively on the corneal epithelium, and 4) the role of corneal nerve recovery in corneal wound healing in PRK enhancement. Our results revealed that in long-term the number of eyes that achieved uncorrected visual acuity (UCVA)≤0.0 and ≤0.5 (logMAR) was higher after PRK than after LASIK. Postoperative stability was slightly better after PRK than after LASIK. In LASIK treated eyes the incidence of myopic regression was more pronounced when the intended correction was over >6.0 D and in patients aged <30 years.Yet the intended corrections in our study were higher for LASIK than for PRK eyes. No differences were found in percentages of eyes with best corrected visual acuity (BCVA) or loss of two or more lines of visual acuity between PRK and LASIK in the long-term. The postoperative long-term outcomes of PRK with two different delivery systems broad beam and scanning laser were compared and revealed no differences. Postoperative outcomes of moderate-to-high astigmatism yielded better results in terms of UCVA and less compromise or loss of two more lines of BCVA after LASIK that after PRK.Similar stability for both procedures was revealed. Vector analysis showed that LASIK outcomes tended to be more accurate than PRK outcomes, yet no statistically differences were found. Irregular astigmatism secondary to recurrent corneal erosion due to map-dot-fingerprint was successfully treated with phototherapeutic keratectomy (PTK). Preoperative videokeratographies (VK) showed irregular astigmatism. However, postoperatively, all eyes showed a regular pattern. No correlation was found between pre- and postoperative VK patterns. Postoperative outcomes of late PRK in eyes originally subjected to LASIK showed that all (7/7) eyes achieved UCVA ≤0.5 at last follow-up (range 3 — 11 months), and no eye lost lines of BCVA. Postoperatively all eyes developed and initial mild haze (0.5 — 1) into the first month. Yet, at last follow-up 5/7 eyes showed a haze of 0.5 and this was no longer evident in 2/7 eyes. Based on these results, we demonstrated that the long-term outcomes after PRK and LASIK were safe and efficient, with similar stability for both procedures. The PRK outcomes were similar when treated by broad-beam or scanning slit laser. LASIK was better than PRK to correct moderate-to-high astigmatism, yet both procedures showed a tendency of undercorrection. Irregular astigmatism was proven to be able to depend exclusively from the corneal epithelium. If this kind of astigmatism is present in the cornea and a customized PRK/LASIK correction is done based on wavefront measurements an irregular astigmatism may be produced rather than treated. Corneal sensory nerve recovery should have an important role in the modulation of the corneal wound healing and post-operative anterior stromal scarring. PRK enhancement may be an option in eyes with previous LASIK after a sufficient time interval that in at least 2 years.