A Dependency Parsing Approach to Biomedical Text Mining

Biomedical research is currently facing a new type of challenge: an excess of information, both in terms of raw data from experiments and in the number of scientific publications describing their results. Mirroring the focus on data mining techniques to address the issues of structured data, there has recently been great interest in the development and application of text mining techniques to make more effective use of the knowledge contained in biomedical scientific publications, accessible only in the form of natural human language. This thesis describes research done in the broader scope of projects aiming to develop methods, tools and techniques for text mining tasks in general and for the biomedical domain in particular. The work described here involves more specifically the goal of extracting information from statements concerning relations of biomedical entities, such as protein-protein interactions. The approach taken is one using full parsing—syntactic analysis of the entire structure of sentences—and machine learning, aiming to develop reliable methods that can further be generalized to apply also to other domains. The five papers at the core of this thesis describe research on a number of distinct but related topics in text mining. In the first of these studies, we assessed the applicability of two popular general English parsers to biomedical text mining and, finding their performance limited, identified several specific challenges to accurate parsing of domain text. In a follow-up study focusing on parsing issues related to specialized domain terminology, we evaluated three lexical adaptation methods. We found that the accurate resolution of unknown words can considerably improve parsing performance and introduced a domain-adapted parser that reduced the error rate of theoriginal by 10% while also roughly halving parsing time. To establish the relative merits of parsers that differ in the applied formalisms and the representation given to their syntactic analyses, we have also developed evaluation methodology, considering different approaches to establishing comparable dependency-based evaluation results. We introduced a methodology for creating highly accurate conversions between different parse representations, demonstrating the feasibility of unification of idiverse syntactic schemes under a shared, application-oriented representation. In addition to allowing formalism-neutral evaluation, we argue that such unification can also increase the value of parsers for domain text mining. As a further step in this direction, we analysed the characteristics of publicly available biomedical corpora annotated for protein-protein interactions and created tools for converting them into a shared form, thus contributing also to the unification of text mining resources. The introduced unified corpora allowed us to perform a task-oriented comparative evaluation of biomedical text mining corpora. This evaluation established clear limits on the comparability of results for text mining methods evaluated on different resources, prompting further efforts toward standardization. To support this and other research, we have also designed and annotated BioInfer, the first domain corpus of its size combining annotation of syntax and biomedical entities with a detailed annotation of their relationships. The corpus represents a major design and development effort of the research group, with manual annotation that identifies over 6000 entities, 2500 relationships and 28,000 syntactic dependencies in 1100 sentences. In addition to combining these key annotations for a single set of sentences, BioInfer was also the first domain resource to introduce a representation of entity relations that is supported by ontologies and able to capture complex, structured relationships. Part I of this thesis presents a summary of this research in the broader context of a text mining system, and Part II contains reprints of the five included publications.

Bayesian Estimation of Noise

In mathematical modeling the estimation of the model parameters is one of the most common problems. The goal is to seek parameters that fit to the measurements as well as possible. There is always error in the measurements which implies uncertainty to the model estimates. In Bayesian statistics all the unknown quantities are presented as probability distributions. If there is knowledge about parameters beforehand, it can be formulated as a prior distribution. The Bays’ rule combines the prior and the measurements to posterior distribution. Mathematical models are typically nonlinear, to produce statistics for them requires efficient sampling algorithms. In this thesis both Metropolis-Hastings (MH), Adaptive Metropolis (AM) algorithms and Gibbs sampling are introduced. In the thesis different ways to present prior distributions are introduced. The main issue is in the measurement error estimation and how to obtain prior knowledge for variance or covariance. Variance and covariance sampling is combined with the algorithms above. The examples of the hyperprior models are applied to estimation of model parameters and error in an outlier case.

Conservation Laws in Cellular Automata

Conservation laws in physics are numerical invariants of the dynamics of a system. In cellular automata (CA), a similar concept has already been defined and studied. To each local pattern of cell states a real value is associated, interpreted as the “energy” (or “mass”, or . . . ) of that pattern.The overall “energy” of a configuration is simply the sum of the energy of the local patterns appearing on different positions in the configuration. We have a conservation law for that energy, if the total energy of each configuration remains constant during the evolution of the CA. For a given conservation law, it is desirable to find microscopic explanations for the dynamics of the conserved energy in terms of flows of energy from one region toward another. Often, it happens that the energy values are from non-negative integers, and are interpreted as the number of “particles” distributed on a configuration. In such cases, it is conjectured that one can always provide a microscopic explanation for the conservation laws by prescribing rules for the local movement of the particles. The onedimensional case has already been solved by Fuk´s and Pivato. We extend this to two-dimensional cellular automata with radius-0,5 neighborhood on the square lattice. We then consider conservation laws in which the energy values are chosen from a commutative group or semigroup. In this case, the class of all conservation laws for a CA form a partially ordered hierarchy. We study the structure of this hierarchy and prove some basic facts about it. Although the local properties of this hierarchy (at least in the group-valued case) are tractable, its global properties turn out to be algorithmically inaccessible. In particular, we prove that it is undecidable whether this hierarchy is trivial (i.e., if the CA has any non-trivial conservation law at all) or unbounded. We point out some interconnections between the structure of this hierarchy and the dynamical properties of the CA. We show that positively expansive CA do not have non-trivial conservation laws. We also investigate a curious relationship between conservation laws and invariant Gibbs measures in reversible and surjective CA. Gibbs measures are known to coincide with the equilibrium states of a lattice system defined in terms of a Hamiltonian. For reversible cellular automata, each conserved quantity may play the role of a Hamiltonian, and provides a Gibbs measure (or a set of Gibbs measures, in case of phase multiplicity) that is invariant. Conversely, every invariant Gibbs measure provides a conservation law for the CA. For surjective CA, the former statement also follows (in a slightly different form) from the variational characterization of the Gibbs measures. For one-dimensional surjective CA, we show that each invariant Gibbs measure provides a conservation law. We also prove that surjective CA almost surely preserve the average information content per cell with respect to any probability measure.

Formal Power Analysis of Systems-on-Chip

The design methods and languages targeted to modern System-on-Chip designs are facing tremendous pressure of the ever-increasing complexity, power, and speed requirements. To estimate any of these three metrics, there is a trade-off between accuracy and abstraction level of detail in which a system under design is analyzed. The more detailed the description, the more accurate the simulation will be, but, on the other hand, the more time consuming it will be. Moreover, a designer wants to make decisions as early as possible in the design flow to avoid costly design backtracking. To answer the challenges posed upon System-on-chip designs, this thesis introduces a formal, power aware framework, its development methods, and methods to constraint and analyze power consumption of the system under design. This thesis discusses on power analysis of synchronous and asynchronous systems not forgetting the communication aspects of these systems. The presented framework is built upon the Timed Action System formalism, which offer an environment to analyze and constraint the functional and temporal behavior of the system at high abstraction level. Furthermore, due to the complexity of System-on-Chip designs, the possibility to abstract unnecessary implementation details at higher abstraction levels is an essential part of the introduced design framework. With the encapsulation and abstraction techniques incorporated with the procedure based communication allows a designer to use the presented power aware framework in modeling these large scale systems. The introduced techniques also enable one to subdivide the development of communication and computation into own tasks. This property is taken into account in the power analysis part as well. Furthermore, the presented framework is developed in a way that it can be used throughout the design project. In other words, a designer is able to model and analyze systems from an abstract specification down to an implementable specification.

Causation and dominance : a study of Finnish causative verbs expressing social dominance

En väsentlig fråga inom såväl lingvistiska som kognitiva teorier är, hur språket beskriver kausala relationer. I finskan finns det en speciell typ av kausativa verb avledda med suffixet (U)ttA som används för att uttrycka att handlingen i fråga utförs av någon annan än subjektreferenten, t.ex. Maija haetuttaa Matilla kirjastosta kirjan ’Maija låter Matti hämta boken från biblioteket’ och Matti juoksuttaa Maijan kaupunkiin ’Matti låter Maija springa till staden’. Syftet med denna avhandling var att med exempel av sociala dominansens kausativer undersöka ordbildningens natur samt begreppet ’socialt förorsakande’. För att beskriva avledningars regelbundna argumentstruktur i form av kopplingen mellan syntaxen och semantiken upprättades deras prototypiska strukturer. Dessa verb har emellertid också specifika användningsområden som framhäver variationer i sociala relationer. Säregna egenskaper hos den sociala dominansens kausativer inkluderades i undersökningen och definierades som konstruktioner. Konstruktionerna omfattar speciella syntaktiska och/eller semantiska element och utöver det också pragmatiska värderande implikationer. Uppbyggnaden av den sociala dimensionen hos de undersökta verben består av egenskaper förbundna med typen av förorsakande, argumentens agentiva egenskaper (aktivitet eller passivitet, dominans, kontroll, viljestyrdhet och ansvarighet) samt konventionaliserade attityder och tolkningar. Ett exempel på en s.k. 'tolkningskonstruktion’ är den negativa dominansens uttryck som i avhandlingen kallas Maktmissbrukskonstruktionen. Denna konstruktion inkluderar talarens starkt kritiska hållning till den uttryckta situationen, t.ex. Asiakas juoksuttaa lentoemäntää ’Kunden låter flygvärdinnan springa’. Dessa konstruktioner fyller en viktig funktion i språklig kommunikation: att beskriva avvikande av sociala normer och att foga expressivitet till budskapet. Metodologiskt kombinerar denna avhandling teorier som baseras på det aktuella språkbruket och teoretisk lingvistisk analys. Verbens samt konstruktionernas konceptuella lexikala struktur och prototypstrukturerna analyserades med hjälp av den konceptuella semantikens verktyg, som har utvecklats av Jackendoff, Nikanne och Pörn.

Modeling of electrolyte sorption – from phase equilibria to dynamic separation systems

In this thesis, general approach is devised to model electrolyte sorption from aqueous solutions on solid materials. Electrolyte sorption is often considered as unwanted phenomenon in ion exchange and its potential as an independent separation method has not been fully explored. The solid sorbents studied here are porous and non-porous organic or inorganic materials with or without specific functional groups attached on the solid matrix. Accordingly, the sorption mechanisms include physical adsorption, chemisorption on the functional groups and partition restricted by electrostatic or steric factors. The model is tested in four Cases Studies dealing with chelating adsorption of transition metal mixtures, physical adsorption of metal and metalloid complexes from chloride solutions, size exclusion of electrolytes in nano-porous materials and electrolyte exclusion of electrolyte/non-electrolyte mixtures. The model parameters are estimated using experimental data from equilibrium and batch kinetic measurements, and they are used to simulate actual single-column fixed-bed separations. Phase equilibrium between the solution and solid phases is described using thermodynamic Gibbs-Donnan model and various adsorption models depending on the properties of the sorbent. The 3-dimensional thermodynamic approach is used for volume sorption in gel-type ion exchangers and in nano-porous adsorbents, and satisfactory correlation is obtained provided that both mixing and exclusion effects are adequately taken into account. 2-Dimensional surface adsorption models are successfully applied to physical adsorption of complex species and to chelating adsorption of transition metal salts. In the latter case, comparison is also made with complex formation models. Results of the mass transport studies show that uptake rates even in a competitive high-affinity system can be described by constant diffusion coefficients, when the adsorbent structure and the phase equilibrium conditions are adequately included in the model. Furthermore, a simplified solution based on the linear driving force approximation and the shrinking-core model is developed for very non-linear adsorption systems. In each Case Study, the actual separation is carried out batch-wise in fixed-beds and the experimental data are simulated/correlated using the parameters derived from equilibrium and kinetic data. Good agreement between the calculated and experimental break-through curves is usually obtained indicating that the proposed approach is useful in systems, which at first sight are very different. For example, the important improvement in copper separation from concentrated zinc sulfate solution at elevated temperatures can be correctly predicted by the model. In some cases, however, re-adjustment of model parameters is needed due to e.g. high solution viscosity.

Quantitative refinement of reaction-based biomodels

In the field of molecular biology, scientists adopted for decades a reductionist perspective in their inquiries, being predominantly concerned with the intricate mechanistic details of subcellular regulatory systems. However, integrative thinking was still applied at a smaller scale in molecular biology to understand the underlying processes of cellular behaviour for at least half a century. It was not until the genomic revolution at the end of the previous century that we required model building to account for systemic properties of cellular activity. Our system-level understanding of cellular function is to this day hindered by drastic limitations in our capability of predicting cellular behaviour to reflect system dynamics and system structures. To this end, systems biology aims for a system-level understanding of functional intraand inter-cellular activity. Modern biology brings about a high volume of data, whose comprehension we cannot even aim for in the absence of computational support. Computational modelling, hence, bridges modern biology to computer science, enabling a number of assets, which prove to be invaluable in the analysis of complex biological systems, such as: a rigorous characterization of the system structure, simulation techniques, perturbations analysis, etc. Computational biomodels augmented in size considerably in the past years, major contributions being made towards the simulation and analysis of large-scale models, starting with signalling pathways and culminating with whole-cell models, tissue-level models, organ models and full-scale patient models. The simulation and analysis of models of such complexity very often requires, in fact, the integration of various sub-models, entwined at different levels of resolution and whose organization spans over several levels of hierarchy. This thesis revolves around the concept of quantitative model refinement in relation to the process of model building in computational systems biology. The thesis proposes a sound computational framework for the stepwise augmentation of a biomodel. One starts with an abstract, high-level representation of a biological phenomenon, which is materialised into an initial model that is validated against a set of existing data. Consequently, the model is refined to include more details regarding its species and/or reactions. The framework is employed in the development of two models, one for the heat shock response in eukaryotes and the second for the ErbB signalling pathway. The thesis spans over several formalisms used in computational systems biology, inherently quantitative: reaction-network models, rule-based models and Petri net models, as well as a recent formalism intrinsically qualitative: reaction systems. The choice of modelling formalism is, however, determined by the nature of the question the modeler aims to answer. Quantitative model refinement turns out to be not only essential in the model development cycle, but also beneficial for the compilation of large-scale models, whose development requires the integration of several sub-models across various levels of resolution and underlying formal representations.

Geochemistry and water quality of Lake Qarun, Egypt

Water geochemistry is a very important tool for studying the water quality in a given area. Geology and climate are the major natural factors controlling the chemistry of most natural waters. Anthropogenic impacts are the secondary sources of contamination in natural waters. This study presents the first integrative approach to the geochemistry and water quality of surface waters and Lake Qarun in the Fayoum catchment, Egypt. Moreover, geochemical modeling of Lake Qarun was firstly presented. The Nile River is the main source of water to the Fayoum watershed. To investigate the quality and geochemistry of this water, water samples from irrigation canals, drains and Lake Qarun were collected during the period 2010‒2013 from the whole Fayoum drainage basin to address the major processes and factors governing the evolution of water chemistry in the investigation area. About 34 physicochemical quality parameters, including major ions, oxygen isotopes, trace elements, nutrients and microbiological parameters were investigated in the water samples. Multivariable statistical analysis was used to interpret the interrelationship between the different studied parameters. Geochemical modeling of Lake Qarun was carried out using Hardie and Eugster’s evolutionary model and a model simulated by PHREEQC software. The crystallization sequence during evaporation of Lake Qarun brine was also studied using a Jänecke phase diagram involving the system Na‒K‒Mg‒ Cl‒SO4‒H2O. The results show that the chemistry of surface water in the Fayoum catchment evolves from Ca- Mg-HCO3 at the head waters to Ca‒Mg‒Cl‒SO4 and eventually to Na‒Cl downstream and at Lake Qarun. The main processes behind the high levels of Na, SO4 and Cl in downstream waters and in Lake Qarun are dissolution of evaporites from Fayoum soils followed by evapoconcentration. This was confirmed by binary plots between the different ions, Piper plot, Gibb’s plot and δ18O results. The modeled data proved that Lake Qarun brine evolves from drainage waters via an evaporation‒crystallization process. Through the precipitation of calcite and gypsum, the solution should reach the final composition "Na–Mg–SO4–Cl". As simulated by PHREEQC, further evaporation of lake brine can drive halite to precipitate in the final stages of evaporation. Significantly, the crystallization sequence during evaporation of the lake brine at the concentration ponds of the Egyptian Salts and Minerals Company (EMISAL) reflected the findings from both Hardie and Eugster’s evolutionary model and the PHREEQC simulated model. After crystallization of halite at the EMISAL ponds, the crystallization sequence during evaporation of the residual brine (bittern) was investigated using a Jänecke phase diagram at 35 °C. This diagram was more useful than PHREEQC for predicting the evaporation path especially in the case of this highly concentrated brine (bittern). The predicted crystallization path using a Jänecke phase diagram at 35 °C showed that halite, hexahydrite, kainite and kieserite should appear during bittern evaporation. Yet the actual crystallized mineral salts were only halite and hexahydrite. The absence of kainite was due to its metastability while the absence of kieserite was due to opposed relative humidity. The presence of a specific MgSO4.nH2O phase in ancient evaporite deposits can be used as a paleoclimatic indicator. Evaluation of surface water quality for agricultural purposes shows that some irrigation waters and all drainage waters have high salinities and therefore cannot be used for irrigation. Waters from irrigation canals used as a drinking water supply show higher concentrations of Al and suffer from high levels of total coliform (TC), fecal coliform (FC) and fecal streptococcus (FS). These waters cannot be used for drinking or agricultural purposes without treatment, because of their high health risk. Therefore it is crucial that environmental protection agencies and the media increase public awareness of this issue, especially in rural areas.

Politbyroon oopperat

Kirjallisuusarvostelu

Formal modelling for digital media distribution

Human beings have always strived to preserve their memories and spread their ideas. In the beginning this was always done through human interpretations, such as telling stories and creating sculptures. Later, technological progress made it possible to create a recording of a phenomenon; first as an analogue recording onto a physical object, and later digitally, as a sequence of bits to be interpreted by a computer. By the end of the 20th century technological advances had made it feasible to distribute media content over a computer network instead of on physical objects, thus enabling the concept of digital media distribution. Many digital media distribution systems already exist, and their continued, and in many cases increasing, usage is an indicator for the high interest in their future enhancements and enriching. By looking at these digital media distribution systems, we have identified three main areas of possible improvement: network structure and coordination, transport of content over the network, and the encoding used for the content. In this thesis, our aim is to show that improvements in performance, efficiency and availability can be done in conjunction with improvements in software quality and reliability through the use of formal methods: mathematical approaches to reasoning about software so that we can prove its correctness, together with the desirable properties. We envision a complete media distribution system based on a distributed architecture, such as peer-to-peer networking, in which different parts of the system have been formally modelled and verified. Starting with the network itself, we show how it can be formally constructed and modularised in the Event-B formalism, such that we can separate the modelling of one node from the modelling of the network itself. We also show how the piece selection algorithm in the BitTorrent peer-to-peer transfer protocol can be adapted for on-demand media streaming, and how this can be modelled in Event-B. Furthermore, we show how modelling one peer in Event-B can give results similar to simulating an entire network of peers. Going further, we introduce a formal specification language for content transfer algorithms, and show that having such a language can make these algorithms easier to understand. We also show how generating Event-B code from this language can result in less complexity compared to creating the models from written specifications. We also consider the decoding part of a media distribution system by showing how video decoding can be done in parallel. This is based on formally defined dependencies between frames and blocks in a video sequence; we have shown that also this step can be performed in a way that is mathematically proven correct. Our modelling and proving in this thesis is, in its majority, tool-based. This provides a demonstration of the advance of formal methods as well as their increased reliability, and thus, advocates for their more wide-spread usage in the future.