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.

Mining Sequential Data – in Search of Segmental Structures

Segmentation is a data mining technique yielding simplified representations of sequences of ordered points. A sequence is divided into some number of homogeneous blocks, and all points within a segment are described by a single value. The focus in this thesis is on piecewise-constant segments, where the most likely description for each segment and the most likely segmentation into some number of blocks can be computed efficiently. Representing sequences as segmentations is useful in, e.g., storage and indexing tasks in sequence databases, and segmentation can be used as a tool in learning about the structure of a given sequence. The discussion in this thesis begins with basic questions related to segmentation analysis, such as choosing the number of segments, and evaluating the obtained segmentations. Standard model selection techniques are shown to perform well for the sequence segmentation task. Segmentation evaluation is proposed with respect to a known segmentation structure. Applying segmentation on certain features of a sequence is shown to yield segmentations that are significantly close to the known underlying structure. Two extensions to the basic segmentation framework are introduced: unimodal segmentation and basis segmentation. The former is concerned with segmentations where the segment descriptions first increase and then decrease, and the latter with the interplay between different dimensions and segments in the sequence. These problems are formally defined and algorithms for solving them are provided and analyzed. Practical applications for segmentation techniques include time series and data stream analysis, text analysis, and biological sequence analysis. In this thesis segmentation applications are demonstrated in analyzing genomic sequences.

Computational Techniques for Haplotype Inference and for Local Alignment Significance

This thesis which consists of an introduction and four peer-reviewed original publications studies the problems of haplotype inference (haplotyping) and local alignment significance. The problems studied here belong to the broad area of bioinformatics and computational biology. The presented solutions are computationally fast and accurate, which makes them practical in high-throughput sequence data analysis. Haplotype inference is a computational problem where the goal is to estimate haplotypes from a sample of genotypes as accurately as possible. This problem is important as the direct measurement of haplotypes is difficult, whereas the genotypes are easier to quantify. Haplotypes are the key-players when studying for example the genetic causes of diseases. In this thesis, three methods are presented for the haplotype inference problem referred to as HaploParser, HIT, and BACH. HaploParser is based on a combinatorial mosaic model and hierarchical parsing that together mimic recombinations and point-mutations in a biologically plausible way. In this mosaic model, the current population is assumed to be evolved from a small founder population. Thus, the haplotypes of the current population are recombinations of the (implicit) founder haplotypes with some point--mutations. HIT (Haplotype Inference Technique) uses a hidden Markov model for haplotypes and efficient algorithms are presented to learn this model from genotype data. The model structure of HIT is analogous to the mosaic model of HaploParser with founder haplotypes. Therefore, it can be seen as a probabilistic model of recombinations and point-mutations. BACH (Bayesian Context-based Haplotyping) utilizes a context tree weighting algorithm to efficiently sum over all variable-length Markov chains to evaluate the posterior probability of a haplotype configuration. Algorithms are presented that find haplotype configurations with high posterior probability. BACH is the most accurate method presented in this thesis and has comparable performance to the best available software for haplotype inference. Local alignment significance is a computational problem where one is interested in whether the local similarities in two sequences are due to the fact that the sequences are related or just by chance. Similarity of sequences is measured by their best local alignment score and from that, a p-value is computed. This p-value is the probability of picking two sequences from the null model that have as good or better best local alignment score. Local alignment significance is used routinely for example in homology searches. In this thesis, a general framework is sketched that allows one to compute a tight upper bound for the p-value of a local pairwise alignment score. Unlike the previous methods, the presented framework is not affeced by so-called edge-effects and can handle gaps (deletions and insertions) without troublesome sampling and curve fitting.

Computationally Efficient Methods for MDL-Optimal Density Estimation and Data Clustering

The Minimum Description Length (MDL) principle is a general, well-founded theoretical formalization of statistical modeling. The most important notion of MDL is the stochastic complexity, which can be interpreted as the shortest description length of a given sample of data relative to a model class. The exact definition of the stochastic complexity has gone through several evolutionary steps. The latest instantation is based on the so-called Normalized Maximum Likelihood (NML) distribution which has been shown to possess several important theoretical properties. However, the applications of this modern version of the MDL have been quite rare because of computational complexity problems, i.e., for discrete data, the definition of NML involves an exponential sum, and in the case of continuous data, a multi-dimensional integral usually infeasible to evaluate or even approximate accurately. In this doctoral dissertation, we present mathematical techniques for computing NML efficiently for some model families involving discrete data. We also show how these techniques can be used to apply MDL in two practical applications: histogram density estimation and clustering of multi-dimensional data.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Confronting Confucian Understandings of the Christian Doctrine of Salvation : A systematic theological analysis of the basic problems in the Confucian-Christian dialogue

The aim of the present study is to analyze Confucian understandings of the Christian doctrine of salvation in order to find the basic problems in the Confucian-Christian dialogue. I will approach the task via a systematic theological analysis of four issues in order to limit the thesis to an appropriate size. They are analyzed in three chapters as follows: 1. The Confucian concept concerning the existence of God. Here I discuss mainly the issue of assimilation of the Christian concept of God to the concepts of Sovereign on High (Shangdi) and Heaven (Tian) in Confucianism. 2. The Confucian understanding of the object of salvation and its status in Christianity. 3. The Confucian understanding of the means of salvation in Christianity. Before beginning this analysis it is necessary to clarify the vast variety of controversies, arguments, ideas, opinions and comments expressed in the name of Confucianism; thus, clear distinctions among different schools of Confucianism are given in chapter 2. In the last chapter I will discuss the results of my research in this study by pointing out the basic problems that will appear in the analysis. The results of the present study provide conclusions in three related areas: the tacit differences in the ways of thinking between Confucians and Christians, the basic problems of the Confucian-Christian dialogue, and the affirmative elements in the dialogue. In addition to a summary, a bibliography and an index, there are also eight appendices, where I have introduced important background information for readers to understand the present study.

Viimeinen matka : Toimintatutkimus kirkollisen hautauskentän professiostruktuurista

This study is a qualitative examination of the professional structure of the ecclesias-tical funeral field. The research material is based on 13 funeral cases in the archdio-cese. The researcher participated in all the funerals and memorial events, interviewed the closest survivors, the officials of the funeral agency and the ecclesiastical actors. The material was collected by means of observation and recording of the interviews, and was later transcribed and analyzed. The actors in this study are the survivors, the funeral agencies and the church. The survivors act as the buyers and users of the products (funeral services) who require both the funeral agencies and the church to assist them with the problems that the death has caused. The numbers of actions related to the death and to the funerals - the rituals of death - are placed on the action field, which in this study is called the funeral field. In this field, the researchquestion focused space and power, and the actions on the funeral field are highly ritualized. The theoretical model comes from Pierre Bourdieu. The study showed an action structure on the funeral field in which the survivors first contacted a funeral agency, which then contacted the other actors of the field, re-served the date and place for the funeral, and organised the funeral arrangements. The funeral agencies arranged an opportunity for the survivors to have a last look at the deceased when he or she was placed in the coffin, and they held a moment of the prayer (if desired) before removing the deceased from the hospital's chapel. The sur-vivors contacted the pastor of the funeral much later. The pastor also participated in the memorial event. The survivors contacted the church musician through via pastor. In some cases, the survivors had neither met nor even seen the musician prior to the actual funeral service. Still, the music was of great importance to the survivors. In the research interviews, tensions emerged to some extent between the funeral agencies and the ecclesiastical actors; these actors attempted to resolve these tensions through organising negotiations. In the beginning of the 20th century, the family took an active part in the preparations of the deceased and in the arrangements of the funerals, whereas this study showed that these days, survivors often transfer the preparations to the funeral agencies. The professional side of the funeral field has grown. The funeral agencies can be seen as providers of full services that act on the survivors' behalf, aspiring to high individu-ality and aiming to fulfil the survivors' wishes. In practise, the role of the church in carrying out the last journey was reduced in the research cases to the actual funeral. In several cases, the pastor or the cantor of the funeral had never before seen the per-son in the coffin at any stage of life or death. The proportion of cremations in funeral cases has increased rapidly, however, special issues related to these cremations (such as the possibility of holding a funeral service for the already cremated deceased) have seen little consideration in the church. In the church's liturgies on funeral rites, cremation is frequently overlooked. The pastors or the cantors did not participate in either the burial of the funeral urn or in the scattering of the deceased's ashes. The verger took care of it. The parishes had no adopted standard practices for cremations, yet in each case for the survivors that moment was crucial.

Spirituality of Finnish peacekeepers

The previous academic research on Finnish peacekeeping has clarified the operative and historical aspects of Finnish peacekeeping lacking the view of an individual who does the actual peacekeeping work. This research is based on the underlying theoretical assumption of human beings possessing different kinds of talents and intelligences creating a holistic entity. In this broad perspective spirituality was explored as an umbrella concept, as a holistic ability or talent, that can be explored as the deepest aspect of defining what it means to be human. The theoretical framework incorporated the concept of an intelligence, which is defined in Gardner's theory of multiple intelligences as the ability to solve problems, or to create products, that are valued within one or more cultural settings (Gardner, 1993, x). The viability of this theory was studied in the sample of Finnish peacekeepers. Spirituality in the theoretical and conceptual horizon was viewed as an extension of Gardner's theory of intelligences as one potential Gardnerian intelligence candidate. In addition to Gardner's theory, spirituality was explored as sensitivity which includes capacities such as sensing awareness, sensing mystery and sensing value (Hay, 1998). Also the practical aspects of spirituality were taken in account as shown in our everyday lives giving us the direction and influencing our social responsibilities and concerns (Bradford, 1995). Spirituality was explored also involving the element of the peacekeepers' community, the element of personal moral orientations and in the domain of religion and coping. The purpose of this research aimed in two dimensions. First, the aim was to outline the intelligence profile and the spiritual sensitivity profile of peacekeepers. Second, the aim was to understand qualitatively the nature of peacekeepers' spirituality The research interests were studied with different kinds of peacekeepers. Applying the mixed methods approach the research was conducted in two phases: first the former SFOR peacekeepers (N=6) were interviewed and the data was analysed. Inspired by the primary findings of these interviews, the data for the case-study of one peacekeeper was collected in co-operation with one former SFOR peacekeeper (N=1). In the second phase the data was collected from KFOR peacekeepers through the quantitative MI-Survey and the spiritual sensitivity survey (N=195). The quantitative method was used to outline the intelligence profile and the spiritual sensitivity profile of peacekeepers (N=195). In the mixed methods approach this method highlighted the general overview of intelligence traits and spiritual sensitivity of peacekeepers. In the mixed methods approach the qualitative method including interviews (N=6) and a case-study of one peacekeeper (N=1) increased subjective, qualitative information of spirituality of peacekeepers. The intelligence profile of peacekeepers highlighted the bodily-kinesthetic and interpersonal dimensions as the practical and social aspects of peacekeepers. Strong inter-item dependencies in the intrapersonal intelligence profile meant that peacekeepers possess a self-reflection and self-knowledge component and they reflect on deep psychological and philosophical issues. Regarding the spiritual sensitivity, peacekeepers found awareness-sensing, mystery-sensing, value-sensing and community-sensing important. The community-sensing emphasised a strong will to advance peace and to help people who are in need: things that are close to the heart of the peacekeepers. These results depicted practicality, being socially capable, and reflecting one's inner world as essential to peacekeepers. Moreover, spirituality as peacekeepers' moral endeavour became clearer because the sub-model of their community-sensing described morally charged destinations: advancing peace and helping people in need. In the qualitative findings peacekeepers articulated justice orientation and rule-following characterising the nature of peacekeepers' moral attitude and moral call (Kohlberg, 1969). An ethic of care (Gilligan, 1982) describes mainly female moral orientation, but the findings revealed that an ethic of care is also an important agent supporting strongly male peacekeepers in their aim to carry out qualitatively good peacekeeping work. The moral endeavour was voiced, when the role of religion in coping meant the assessment of the a way of life, a way of conduct, a way of being truthful to one's own values in confusing surroundings. The practical level of spiritual and religious contemplation was voiced as morally charged inner motivation to fulfil one's duties and at the same time to cope with various peacekeeping challenges. The results of different data sets were combined and interpreted as the moral endeavour, which characterises peacekeepers' spirituality. As the combining result, the perspective of peacekeepers' spirituality is considered moral or at least morally charged.

Cow’s milk related gastrointestinal symptoms in adults

The purpose of this study was to evaluate subjective food-related gastrointestinal symptoms and their relation to cow’s milk by determining the genotype of adult-type hypolactasia, measuring antibodies against milk protein, and screening the most common cause for secondary hypolactasia, namely coeliac disease. The whole study group comprised 1900 adults who gave a blood sample for the study when they attended a health care centre laboratory for various reasons. Of these 1885 (99%) completed a questionnaire on food-related gastrointestinal symptoms. Study No. I evaluated the prevalence of adult-type hypolactasia and its correlation to self-reported milk induced gastrointestinal symptoms. The testing for hypolactasia was done by determination of the C/T-13910 genotypes of the study subjects. The results show that patients with the C/C-13910 genotype associated with adult type hypolactasia consume less milk than those with C/T-13910 and T/T-13910 genotypes. Study No. II evaluated the prevalence and clinical characteristics of undiagnosed coeliac disease in the whole study population with transglutaminase and endomysium antibodies and their correlation with gastrointestinal symptoms. The prevalence of coeliac disease was 2 %, which is surprisingly high. Serum transglutaminase and endomysium antibodies are valuable tools for recognising an undiagnosed coeliac disease in outpatient clinics. In the study No. III the evaluation of milk protein IgE related hypersensitivity was carried out by stratifying all 756 study subjects with milk related problems and randomly choosing 100 age and sex matched controls with no such symptoms from the rest of the original study group. In the study No. IV 400 serum samples were randomly selected for analyzing milk protein related IgA and IgG antibodies and their correlation to milk related GI-symptoms. The measurement of milk protein IgA, IgE or IgG (studies No. III and IV) did not correlate clearly to milk induced symptoms and gave no clinically significant information; hence their measurement is not encouraged in outpatient clinics. In conclusion, adult type hypolactasia is often considered the reason for gastrointestinal symptoms in adults and determination of the C/T-13910 genotypes is a practical way of diagnosing adult type hypolactasia in an outpatient setting. Undiagnosed coeliac disease, should be actively screened and diagnosed in order to apply a gluten free diet and avoid the GI-symptoms and nutritional deficiencies. Cow’s milk hypersensitivity in the adult population is difficult to diagnose since the mechanism in which it is mediated is still unclear. Measuring of cow’s milk protein specific antibodies IgE, IgA or IgG do not correlate with subjective milk-related GI-symptoms.

Supistamista, rationalisointia vai kehittämistä? : Valtiovarainministeriön järjestelyosaston järjestämän henkilöstökoulutus- ja tutkimustoiminnan rakentuminen osaksi valtionhallintoa vuosina 1943-1971

The study examines the personnel training and research activities carried out by the Organization and Methods Division of the Ministry of Finance and their becoming a part and parcel of the state administration in 1943-1971. The study is a combination of institutional and ideological historical research in recent history on adult education, using a constructionist approach. Material salient to the study comes from the files of the Organization and Methods Division in the National Archives, parliamentary documents, committee reports, and the magazines. The concentrated training and research activities arranged by the Organization and Methods Division, became a part and parcel of the state administration in the midst of controversial challenges and opportunities. They served to solve social problems which beset the state administration as well as contextual challenges besetting rationalization measures, and organizational challenges. The activities were also affected by a dependence on decision-makers, administrative units, and civil servants organizations, by different views on rationalization and the holistic nature of reforms, as well as by the formal theories that served as resources. It chose long-term projects which extended to the political decision-makers and administrative units turf, and which were intended to reform the structures of the state administration and to rationalize the practices of the administrative units. The crucial questions emerged in opposite pairs (a constitutional state vs. the ideology of an administratively governed state, a system of national boards vs. a system of government through ministries, efficiency of work vs. pleasantness of work, centralized vs. decentralized rationalization activities) which were not solvable problems but impossible questions with no ultimate answers. The aim and intent of the rationalization of the state administration (the reform of the central, provincial, and local governments) was to facilitate integrated management and to render a greater amount of work by approaching management procedures scientifically and by clarifying administrative instances and their respon-sibilities in regards to each other. The means resorted to were organizational studies and committee work. In the rationalization of office work and finance control, the idea was to effect savings in administrative costs and to pare down those costs as well as to rationalize and heighten those functions by developing the institution of work study practitioners in order to coordinate employer and employee relationships and benefits (the training of work study practitioners, work study, and a two-tier work study practitioner organization). A major part of the training meant teaching and implementing leadership skills in practice, which, in turn, meant that the learning environment was the genuine work community and efforts to change it. In office rationalization, the solution to regulate the relations between the employer and the employees was the co-existence of the technical and biological rationalization and the human resource administration and the accounting and planning systems at the turn of the 1960s and 1970s. The former were based on the school of scientific management and human relations, the latter on system thinking, which was a combination of the former two. In the rationalization of the state administration, efforts were made to find solutions to stabilize management ideologies and to arrange the relationships of administrative systems in administrative science - among other things, in the Hoover Committee and the Simon decision making theory, and, in the 1960s, in system thinking. Despite the development-related vocabulary, the practical work was advanced rationalization. It was said that the practical activities of both the state administration and the administrative units depended on professional managers who saw to production results and human relations. The pedagogic experts hired to develop training came up with a training system, based on the training-technological model where the training was made a function of its own. The State Training Center was established and the training office of the Organization and Methods Division became the leader and coordinator of personnel training.