Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

Investigating physical properties of solid dosage forms during pharmaceutical processing : Process analytical applications of vibrational spectroscopy

In order to improve and continuously develop the quality of pharmaceutical products, the process analytical technology (PAT) framework has been adopted by the US Food and Drug Administration. One of the aims of PAT is to identify critical process parameters and their effect on the quality of the final product. Real time analysis of the process data enables better control of the processes to obtain a high quality product. The main purpose of this work was to monitor crucial pharmaceutical unit operations (from blending to coating) and to examine the effect of processing on solid-state transformations and physical properties. The tools used were near-infrared (NIR) and Raman spectroscopy combined with multivariate data analysis, as well as X-ray powder diffraction (XRPD) and terahertz pulsed imaging (TPI). To detect process-induced transformations in active pharmaceutical ingredients (APIs), samples were taken after blending, granulation, extrusion, spheronisation, and drying. These samples were monitored by XRPD, Raman, and NIR spectroscopy showing hydrate formation in the case of theophylline and nitrofurantoin. For erythromycin dihydrate formation of the isomorphic dehydrate was critical. Thus, the main focus was on the drying process. NIR spectroscopy was applied in-line during a fluid-bed drying process. Multivariate data analysis (principal component analysis) enabled detection of the dehydrate formation at temperatures above 45°C. Furthermore, a small-scale rotating plate device was tested to provide an insight into film coating. The process was monitored using NIR spectroscopy. A calibration model, using partial least squares regression, was set up and applied to data obtained by in-line NIR measurements of a coating drum process. The predicted coating thickness agreed with the measured coating thickness. For investigating the quality of film coatings TPI was used to create a 3-D image of a coated tablet. With this technique it was possible to determine coating layer thickness, distribution, reproducibility, and uniformity. In addition, it was possible to localise defects of either the coating or the tablet. It can be concluded from this work that the applied techniques increased the understanding of physico-chemical properties of drugs and drug products during and after processing. They additionally provided useful information to improve and verify the quality of pharmaceutical dosage forms

Properties of Ammonium Nitrate based fertilisers

The text is divided into three parts; Properties, Application and Safety of Ammonium Nitrate (AN) based fertilisers. In Properties, the structures and phase transitions of ammonium and potassium nitrate are reviewed. The consequences of phase transitions affect the proper use of fertilisers. Therefore the products must be stabilised against the volume changes and consequent loss of bulk density and hardness, formation of dust and finally caking of fertilisers. The effect of different stabilisers is discussed. Magnesium nitrate, ammonium sulphate and potassium nitrate are presented as a good compromise. In the Application part, the solid solutions in the systems (K+,NH4+)NO3- and (NH4+,K+)(Cl-,NO3-) are presented based on studies made with DSC and XRD. As there are clear limits for solute content in the solvent lattice, a number of disproportionation transitions exist in these process phases, e.g., N3 (solid solution isomorphous to NH4NO3-III) disproportionates to phases K3 (solid solution isomorphous to KNO3-III) and K2 (solid solution isomorphous to KNO3-II). In the crystallisation experiments, the formation of K3 depends upon temperature and the ratio K/(K+NH4). The formation of phases K3, N3, and K2 was modelled as a function of temperature and the mole ratios. In introducing chlorides, two distinct maxima for K3 were found. Confirmed with commercial potash samples, the variables affecting the reaction of potassium chloride with AN are the particle size, time, temperature, moisture content and amount of organic coating. The phase diagrams obtained by crystallisation studies were compared with a number of commercial fertilisers and, with regard to phase composition, the temperature and moisture content are critical when the formation and stability of solid solutions are considered. The temperature where the AN-based fertiliser is solidified affects the amount of compounds crystallised at that point. In addition, the temperature where the final moisture is evaporated affects the amount and type of solid solution formed at this temperature. The amount of remaining moisture affects the stability of the K3 phase. The K3 phase is dissolved by the moisture and recrystallised into the quantities of K3, which is stable at the temperature where the sample is kept. The remaining moisture should not be free; it should be bound as water in the final product. The temperatures during storage also affect the quantity of K3 phase. As presented in the figures, K3 phase is not stable at temperatu¬res below 30 °C. If the temperature is about 40 °C, the K3 phase can be formed due to the remaining moisture. In the Safety part, self-sustaining decomposition (SSD), oxidising and energetic properties of fertilisers are discussed. Based on the consequence analysis of SSD, early detection of decomposition in warehouses and proper temperature control in the manufacturing process is important. SSD and oxidising properties were found in compositions where K3 exists. It is assumed that potassium nitrate forms a solid matrix in which AN can decompose. The oxidising properties can be affected by the form of the product. Granular products are inherently less oxidising. Finally energetic properties are reviewed. The composition of the fertiliser has an importance based on theoretical calculations supported by experimental studies. Materials such as carbonates and sulphates act as diluents. An excess of ammonium ions acts as a fuel although this is debatable. Based on the experimental work, the physical properties have a major importance over the composition. A high bulk density is of key importance for detonation resistance.

Problems and Algorithms for Sequence Segmentations

The analysis of sequential data is required in many diverse areas such as telecommunications, stock market analysis, and bioinformatics. A basic problem related to the analysis of sequential data is the sequence segmentation problem. A sequence segmentation is a partition of the sequence into a number of non-overlapping segments that cover all data points, such that each segment is as homogeneous as possible. This problem can be solved optimally using a standard dynamic programming algorithm. In the first part of the thesis, we present a new approximation algorithm for the sequence segmentation problem. This algorithm has smaller running time than the optimal dynamic programming algorithm, while it has bounded approximation ratio. The basic idea is to divide the input sequence into subsequences, solve the problem optimally in each subsequence, and then appropriately combine the solutions to the subproblems into one final solution. In the second part of the thesis, we study alternative segmentation models that are devised to better fit the data. More specifically, we focus on clustered segmentations and segmentations with rearrangements. While in the standard segmentation of a multidimensional sequence all dimensions share the same segment boundaries, in a clustered segmentation the multidimensional sequence is segmented in such a way that dimensions are allowed to form clusters. Each cluster of dimensions is then segmented separately. We formally define the problem of clustered segmentations and we experimentally show that segmenting sequences using this segmentation model, leads to solutions with smaller error for the same model cost. Segmentation with rearrangements is a novel variation to the segmentation problem: in addition to partitioning the sequence we also seek to apply a limited amount of reordering, so that the overall representation error is minimized. We formulate the problem of segmentation with rearrangements and we show that it is an NP-hard problem to solve or even to approximate. We devise effective algorithms for the proposed problem, combining ideas from dynamic programming and outlier detection algorithms in sequences. In the final part of the thesis, we discuss the problem of aggregating results of segmentation algorithms on the same set of data points. In this case, we are interested in producing a partitioning of the data that agrees as much as possible with the input partitions. We show that this problem can be solved optimally in polynomial time using dynamic programming. Furthermore, we show that not all data points are candidates for segment boundaries in the optimal solution.

Computational Identification of Recessive Mutations in Cancers using High Throughput SNP-arrays

This thesis presents a highly sensitive genome wide search method for recessive mutations. The method is suitable for distantly related samples that are divided into phenotype positives and negatives. High throughput genotype arrays are used to identify and compare homozygous regions between the cohorts. The method is demonstrated by comparing colorectal cancer patients against unaffected references. The objective is to find homozygous regions and alleles that are more common in cancer patients. We have designed and implemented software tools to automate the data analysis from genotypes to lists of candidate genes and to their properties. The programs have been designed in respect to a pipeline architecture that allows their integration to other programs such as biological databases and copy number analysis tools. The integration of the tools is crucial as the genome wide analysis of the cohort differences produces many candidate regions not related to the studied phenotype. CohortComparator is a genotype comparison tool that detects homozygous regions and compares their loci and allele constitutions between two sets of samples. The data is visualised in chromosome specific graphs illustrating the homozygous regions and alleles of each sample. The genomic regions that may harbour recessive mutations are emphasised with different colours and a scoring scheme is given for these regions. The detection of homozygous regions, cohort comparisons and result annotations are all subjected to presumptions many of which have been parameterized in our programs. The effect of these parameters and the suitable scope of the methods have been evaluated. Samples with different resolutions can be balanced with the genotype estimates of their haplotypes and they can be used within the same study.

Prognostic molecular factors and algorithms in diffuse large B-cell lymphoma

Diffuse large B-cell lymphoma (DLBCL) is the most common of the non-Hodgkin lymphomas. As DLBCL is characterized by heterogeneous clinical and biological features, its prognosis varies. To date, the International Prognostic Index has been the strongest predictor of outcome for DLBCL patients. However, no biological characters of the disease are taken into account. Gene expression profiling studies have identified two major cell-of-origin phenotypes in DLBCL with different prognoses, the favourable germinal centre B-cell-like (GCB) and the unfavourable activated B-cell-like (ABC) phenotypes. However, results of the prognostic impact of the immunohistochemically defined GCB and non-GCB distinction are controversial. Furthermore, since the addition of the CD20 antibody rituximab to chemotherapy has been established as the standard treatment of DLBCL, all molecular markers need to be evaluated in the post-rituximab era. In this study, we aimed to evaluate the predictive value of immunohistochemically defined cell-of-origin classification in DLBCL patients. The GCB and non-GCB phenotypes were defined according to the Hans algorithm (CD10, BCL6 and MUM1/IRF4) among 90 immunochemotherapy- and 104 chemotherapy-treated DLBCL patients. In the chemotherapy group, we observed a significant difference in survival between GCB and non-GCB patients, with a good and a poor prognosis, respectively. However, in the rituximab group, no prognostic value of the GCB phenotype was observed. Likewise, among 29 high-risk de novo DLBCL patients receiving high-dose chemotherapy and autologous stem cell transplantation, the survival of non-GCB patients was improved, but no difference in outcome was seen between GCB and non-GCB subgroups. Since the results suggested that the Hans algorithm was not applicable in immunochemotherapy-treated DLBCL patients, we aimed to further focus on algorithms based on ABC markers. We examined the modified activated B-cell-like algorithm based (MUM1/IRF4 and FOXP1), as well as a previously reported Muris algorithm (BCL2, CD10 and MUM1/IRF4) among 88 DLBCL patients uniformly treated with immunochemotherapy. Both algorithms distinguished the unfavourable ABC-like subgroup with a significantly inferior failure-free survival relative to the GCB-like DLBCL patients. Similarly, the results of the individual predictive molecular markers transcription factor FOXP1 and anti-apoptotic protein BCL2 have been inconsistent and should be assessed in immunochemotherapy-treated DLBCL patients. The markers were evaluated in a cohort of 117 patients treated with rituximab and chemotherapy. FOXP1 expression could not distinguish between patients, with favourable and those with poor outcomes. In contrast, BCL2-negative DLBCL patients had significantly superior survival relative to BCL2-positive patients. Our results indicate that the immunohistochemically defined cell-of-origin classification in DLBCL has a prognostic impact in the immunochemotherapy era, when the identifying algorithms are based on ABC-associated markers. We also propose that BCL2 negativity is predictive of a favourable outcome. Further investigational efforts are, however, warranted to identify the molecular features of DLBCL that could enable individualized cancer therapy in routine patient care.

Physical Properties of Deep Drill Cores : Implications for Meteorite Impact Effects and Crustal Structures

Physical properties provide valuable information about the nature and behavior of rocks and minerals. The changes in rock physical properties generate petrophysical contrasts between various lithologies, for example, between shocked and unshocked rocks in meteorite impact structures or between various lithologies in the crust. These contrasts may cause distinct geophysical anomalies, which are often diagnostic to their primary cause (impact, tectonism, etc). This information is vital to understand the fundamental Earth processes, such as impact cratering and associated crustal deformations. However, most of the present day knowledge of changes in rock physical properties is limited due to a lack of petrophysical data of subsurface samples, especially for meteorite impact structures, since they are often buried under post-impact lithologies or eroded. In order to explore the uppermost crust, deep drillings are required. This dissertation is based on the deep drill core data from three impact structures: (i) the Bosumtwi impact structure (diameter 10.5 km, 1.07 Ma age; Ghana), (ii) the Chesapeake Bay impact structure (85 km, 35 Ma; Virginia, U.S.A.), and (iii) the Chicxulub impact structure (180 km, 65 Ma; Mexico). These drill cores have yielded all basic lithologies associated with impact craters such as post-impact lithologies, impact rocks including suevites and breccias, as well as fractured and unfractured target rocks. The fourth study case of this dissertation deals with the data of the Paleoproterozoic Outokumpu area (Finland), as a non-impact crustal case, where a deep drilling through an economically important ophiolite complex was carried out. The focus in all four cases was to combine results of basic petrophysical studies of relevant rocks of these crustal structures in order to identify and characterize various lithologies by their physical properties and, in this way, to provide new input data for geophysical modellings. Furthermore, the rock magnetic and paleomagnetic properties of three impact structures, combined with basic petrophysics, were used to acquire insight into the impact generated changes in rocks and their magnetic minerals, in order to better understand the influence of impact. The obtained petrophysical data outline the various lithologies and divide rocks into four domains. Based on target lithology the physical properties of the unshocked target rocks are controlled by mineral composition or fabric, particularly porosity in sedimentary rocks, while sediments result from diverse sedimentation and diagenesis processes. The impact rocks, such as breccias and suevites, strongly reflect the impact formation mechanism and are distinguishable from the other lithologies by their density, porosity and magnetic properties. The numerous shock features resulting from melting, brecciation and fracturing of the target rocks, can be seen in the changes of physical properties. These features include an increase in porosity and subsequent decrease in density in impact derived units, either an increase or a decrease in magnetic properties (depending on a specific case), as well as large heterogeneity in physical properties. In few cases a slight gradual downward decrease in porosity, as a shock-induced fracturing, was observed. Coupled with rock magnetic studies, the impact generated changes in magnetic fraction the shock-induced magnetic grain size reduction, hydrothermal- or melting-related magnetic mineral alteration, shock demagnetization and shock- or temperature-related remagnetization can be seen. The Outokumpu drill core shows varying velocities throughout the drill core depending on the microcracking and sample conditions. This is similar to observations by Kern et al., (2009), who also reported the velocity dependence on anisotropy. The physical properties are also used to explain the distinct crustal reflectors as observed in seismic reflection studies in the Outokumpu area. According to the seismic velocity data, the interfaces between the diopside-tremolite skarn layer and either serpentinite, mica schist or black schist are causing the strong seismic reflectivities.

Wood and fiber properties of Norway spruce and its suitability for thermomechanical pulping.

In the first part of the study, the selected wood and fiber properties were investigated in terms of their occurrence and variation in wood, as well as their relevance from the perspective of thermomechanical pulping process and related end-products. It was concluded that the most important factors were the fiber dimensions, juvenile wood content, and in some cases, the content of heartwood being associated with extremely dry wood with low permeability in spruce. With respect to the above properties, the following three pulpwood assortments of which pulping potential was assumed to vary were formed: wood from regeneration cuttings, first-thinnings wood, and sawmill chips. In the experimental part of the study the average wood and fiber characteristics and their variation were determined for each raw material group prior to pulping. Subsequently, each assortment - equaling about 1500 m3 roundwood - was pulped separately for a 24 h period, at constant process conditions. The properties of obtained newsgrade thermomechanical pulps were then determined. Thermomechanical pulping (TMP) from sawmill chips had the highest proportion of long fibers, smallest proportion of fines, and had generally the coarsest and longest fibers. TMP from first-thinnings wood was just the opposite, whereas that from regeneration cuttings fell in between the above two extremes. High proportion of dry heartwood in wood originating from regeneration cuttings produced a slightly elevated shives content. However, no differences were found in pulp specific energy consumption. The obtained pulp tear index was clearly best in TMP made from sawmill chips and poorest in pulp from first-thinnings wood, which had generally inferior strength properties. No dramatical differences in any of the strength properties were found between pulp from sawmill residual wood and regeneration cuttings. Pulp optical properties were superior in TMP from first-thinnings. Unexpectedly, no noticeable differences, which could be explained with fiber morphology, were found in sheet density, bulk, air permeance or roughness between the three pulps. The most important wood quality factors in this study were the fiber length, fiber cross-sectional dimensions and percentage juvenile wood. Differences found in the quality of TMP manufactured from the above spruce assortments suggest that they could be segregated and pulped separately to obtain specific product characteristics, i.e., for instance tailor-made end-products, and to minimize unnecessary variation in the raw material quality, and hence, pulp quality.

The potential of microbial ecological indicators to guide ecosophisticated management of hydrocarbon-contaminated soils

Soil is an unrenewable natural resource under increasing anthropogenic pressure. One of the main threats to soils, compromising their ability to provide us with the goods and ecosystem services we expect, is pollution. Oil hydrocarbons are the most common soil contaminants, and they disturb not just the biota but also the physicochemical properties of soils. Indigenous soil micro-organisms respond rapidly to changes in the soil ecosystem, and are chronically in direct contact with the hydrophobic pollutants on the soil surfaces. Soil microbial variables could thus serve as an intrinsically relevant indicator of soil quality, to be used in the ecological risk assessment of contaminated and remediated soils. Two contrasting studies were designed to investigate soil microbial ecological responses to hydrocarbons, together with parallel changes in soil physicochemical and ecotoxicological properties. The aim was to identify quantitative or qualitative microbiological variables that would be practicable and broadly applicable for the assessment of the quality and restoration of oil-polluted soil. Soil bacteria commonly react on hydrocarbons as a beneficial substrate, which lead to a positive response in the classical microbiological soil quality indicators; negative impacts were accurately reflected only after severe contamination. Hydrocarbon contaminants become less bioavailable due to weathering processes, and their potentially toxic effects decrease faster than the total concentration. Indigenous hydrocarbon degrader bacteria, naturally present in any terrestrial environment, use specific mechanisms to improve access to the hydrocarbon molecules adsorbed on soil surfaces. Thus when contaminants are unavailable even to the specialised degraders, they should pose no hazard to other biota either. Change in the ratio of hydrocarbon degrader numbers to total microbes was detected to predictably indicate pollutant effects and bioavailability. Also bacterial diversity, a qualitative community characteristic, decreased as a response to hydrocarbons. Stabilisation of community evenness, and community structure that reflected clean reference soil, indicated community recovery. If long-term temporal monitoring is difficult and appropriate clean reference soil unavailable, such comparison could possibly be based on DNA-based community analysis, reflecting past+present, and RNA-based community analysis, showing exclusively present conditions. Microbial ecological indicators cannot replace chemical oil analyses, but they are theoretically relevant and operationally practicable additional tools for ecological risk assessment. As such, they can guide ecologically informed and sustainable ecosophisticated management of oil-contaminated lands.