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.

Implementation of placement and routing algorithms for computer aided design of printed circuit boards

The Printed Circuit Board (PCB) layout design is one of the most important and time consuming phases during equipment design process in all electronic industries. This paper is concerned with the development and implementation of a computer aided PCB design package. A set of programs which operate on a description of the circuit supplied by the user in the form of a data file and subsequently design the layout of a double-sided PCB has been developed. The algorithms used for the design of the PCB optimise the board area and the length of copper tracks used for the interconnections. The output of the package is the layout drawing of the PCB, drawn on a CALCOMP hard copy plotter and a Tektronix 4012 storage graphics display terminal. The routing density (the board area required for one component) achieved by this package is typically 0.8 sq. inch per IC. The package is implemented on a DEC 1090 system in Pascal and FORTRAN and SIGN(1) graphics package is used for display generation.

Estimation of Execution Times of Process Control Algorithms on Microcomputers

An important question which has to be answered in evaluting the suitability of a microcomputer for a control application is the time it would take to execute the specified control algorithm. In this paper, we present a method of obtaining closed-form formulas to estimate this time. These formulas are applicable to control algorithms in which arithmetic operations and matrix manipulations dominate. The method does not require writing detailed programs for implementing the control algorithm. Using this method, the execution times of a variety of control algorithms on a range of 16-bit mini- and recently announced microcomputers are calculated. The formulas have been verified independently by an analysis program, which computes the execution time bounds of control algorithms coded in Pascal when they are run on a specified micro- or minicomputer.

Genetics of T cell co-stimulatory receptors -CD28, CTLA4, ICOS and PDCD1 in immunity and transplantation

Co-stimulatory signals are essential for the activation of naïve T cells and productive immune response. Naïve T cells receive first, antigen-specific signal through T cell receptor. Co-stimulatory receptors provide the second signal which can be either activating or inhibitory. The balance between signals determines the outcome of an immune response. CD28 is crucial for T cell activation; whereas cytotoxic T lymphocyte associated antigen 4 (CTLA4) mediates critical inhibitory signal. Inducible co-stimulator (ICOS) augments cytokine expression and plays role in immunoglobulin class switching. Programmed cell death 1 (PDCD1) acts as negative regulator of T cell proliferation and cytokine responses. The co-stimulatory receptor pathways are potentially involved in self-tolerance and thus, they provide a promising therapeutic strategy for autoimmune diseases and transplantation. The genes encoding CD28, CTLA4 and ICOS are located adjacently in the chromosome region 2q33. The PDCD1 gene maps further, to the region 2q37. CTLA4 and PDCD1 are associated with the risk of a few autoimmune diseases. There is strong linkage disequilibrium (LD) on the 2q33 region; the whole gene of CD28 exists in its own LD block but CTLA4 and the 5' part of ICOS are within a same LD block. The 3' part of ICOS and PDCD1 are in their own separate LD blocks. Extended haplotypes covering the 2q33 region can be identified. This study focuses on immune related conditions like coeliac disease (CD) which is a chronic inflammatory disease with autoimmune features. Immunoglobulin A deficiency (IgAD) belongs to the group of primary antibody deficiencies characterised by reduced levels of immunoglobulins. IgAD co-occurs often with coeliac disease. Renal transplantation is needed in the end stage kidney diseases. Transplantation causes strong immune response which is tried to suppress with drugs. All these conditions are multifactorial with complex genetic background and multiple environmental factors affecting the outcome. We have screened ICOS for polymorphisms by sequencing the exon regions. We detected 11 new variants and determined their frequencies in Finnish population. We have measured linkage disequilibrium on the 2q33 region in Finnish as well as other European populations and observed conserved haplotypes. We analysed genetic association and linkage of the co-stimulatory receptor gene region aiming to study if it is a common risk locus for immune diseases. The 2q33 region was replicated to be linked to coeliac disease in Finnish population and CTLA4-ICOS haplotypes were found to be associated with CD and IgAD being the first non-HLA risk locus common for CD and immunodeficiencies. We also showed association between ICOS and the outcome of kidney transplantation. Our results suggest new evidence for CTLA4-ICOS gene region to be involved in susceptibility of coeliac disease. The earlier published contradictory association results can be explained by involvement of both CTLA4 and ICOS in disease susceptibility. The pattern of variants acting together rather than a single polymorphism may confer the disease risk. These genes may predispose also to immunodeficiencies as well as decreased graft survival and delayed graft function. Consequently, the present study indicates that like the well established HLA locus, the co-stimulatory receptor genes predispose to variety of immune disorders.

Phylogeography and Population Genetics of the Moor frog (Rana arvalis Nilsson) in Northern Europe

The ongoing climate change along with increasing levels of pollutants, diseases, habitat loss and fragmentation constitute global threats to the persistence of many populations, species and ecosystems. However, for the long-term persistence of local populations, one of the biggest threats is the intrinsic loss of genetic variation. In order to adapt to changes in the environment, organisms must have a sufficient supply of heritable variation in traits important for their fitness. With a loss of genetic variation, the risk of extinction will increase. For conservational practices, one should therefore understand the processes that shape the genetic population structure and also the broader (historical) phylogenetic patterning of the species in focus. In this thesis, microsatellite markers were applied to study genetic diversity and population differentiation of the protected moor frog (Rana arvalis) in Fennoscandia from both historical (evolutionary) and applied (conservation) perspectives. The results demonstrate that R. arvalis populations are highly structured over rather short geographic distances. Moreover, the results suggest that R. arvalis recolonized Fennoscandia from two directions after the last ice age. This has had implications for the genetic structuring and population differentiation, especially in the northernmost parts where the two lineages have met. Compared to more southern populations, the genetic variation decreases and the interpopulation differentiation increases dramatically towards north. This could be an outcome of serial population bottlenecking along the recolonization route. Also, current isolation and small population sizes increase the effect of drift, thus reinforcing the observed pattern. The same pattern can also be seen in island populations. However, though R. arvalis on the island of Gotland has lost most of its neutral genetic variability, our results indicate that the levels of additive genetic variation have remained high. This conforms to the conjecture that though neutral markers are widely used in conservation purposes, they may be quite uninformative about the levels of genetic variation in ecologically important traits. Finally, the evolutionary impact of the typical amphibian mating behaviour on genetic diversity was investigated. Given the short time available for larval development, it is important that mating takes place as early as possible. The genetic data and earlier capture-recapture data suggest that R. arvalis gather at mating grounds they are familiar with. However, by forming leks in random to relatedness, and having multiple paternities in single clutches, the risk of inbreeding may be minimized in this otherwise highly philopatric species.

Molecular genetics of Meckel syndrome : Ciliary genes are defective in MKS

Meckel syndrome (MKS, MIM 249000) is a severe developmental disorder that leads to death already in utero or shortly after birth. MKS diagnosis can be established by a careful ultrasound examination already at 11-14 weeks of gestation. The main features of MKS are occipital meningoencephalocele, cystic kidney dysplasia and fibrotic changes of the liver. In addition, polydactyly is frequently reported in the cases. The aim of the study was to characterize the molecular and functional defects in MKS. In this study we were able to identify two major MKS mutations in Finnish population, which cover over 90% of the cases. The first mutation is a 29 bp intronic deletion in the MKS1 gene (c.1483-7_35del) that is found in 70% of the families and the second is a C>T substitution in the coding region of CC2D2A (c.1762C>T), that is found in 20% of the MKS families. Both of these mutations result in abnormal splicing. The discovery of the disease genes has revealed that MKS is caused by primary cilia dysfunction. MKS1 gene has a conserved B9 domain, and it is found in the predicted ciliary proteome. CC2D2A protein is also found in the predicted ciliary proteome and it has a Ca2+ binding domain. The number of genes behind MKS has increased rapidly in the past years and to date, mutations have been identified in five genes (MKS1, TMEM67/MKS3, CEP290/MKS4, RPGRIP1L/MKS5 and CC2D2A/MKS6). Identification of the disease genes mutations has also revealed that MKS is an allelic disorder with other syndromes with overlapping phenotypes. Disorders that are caused by primary cilia dysfunction are collectively known as ciliopathies. Sequence analysis of all the known MKS genes in Finnish and non-Finnish families available to us, where the mutation was still unknown, revealed mutations in 14 out of the 30 families included in the study. When we collected all the reported mutations in MKS genes in different syndromes we could see that there was clearly a genotype-syndrome correlation between the mutations and the syndromes, since the same pair of mutations has never been reported in different syndromes. The basic molecular events behind MKS will not only give us information of this syndrome, but also significant novel information on early fetal development in general.

Molecular genetics of tooth agenesis

Congenital missing of teeth, tooth agenesis or hypodontia, is one of the most common developmental anomalies in man. The common forms in which one or a few teeth are absent, may cause occlusal or cosmetic harm, while severe forms which are relatively rare always require clinical attention to support and maintain the dental function. Observation of tooth agenesis is also important for diagnosis of malformation syndromes. Some external factors may cause developmental defects and agenesis in dentition. However, the role of inheritance in the etiology of tooth agenesis is well established by twin and family studies. Studies on familial tooth agenesis as well as mouse null mutants have also identified several genetic factors. However, these explain syndromic or rare dominant forms of tooth agenesis, whereas the genes and defects responsible for the majority of cases of tooth agenesis, especially the common and less severe forms, are largely unknown. In this study it was shown, that a dominant nonsense mutation in PAX9 was responsible for severe tooth agenesis (oligodontia) in a Finnish family. In a study of tooth agenesis associated with Wolf-Hirschhorn syndrome, it was shown that severe tooth agenesis was present if the causative deletion in 4p spanned the MSX1 locus. It was concluded that severe tooth agenesis was caused by haploinsufficiency of these transcription factors. A summary of the phenotypes associated with known defects in MSX1 and PAX9 showed that, despite similarities, they were significantly different, suggesting that the genes, in addition to known interactions, also have independent roles during the development of human dentition. The original aim of this work was to identify gene defects that underlie the common incisor and premolar hypodontia. After excluding several candidate genes, a genome-wide search was conducted in seven Finnish families in which this phenotype was inherited in an autosomal dominant manner. A promising locus for second premolar agenesis was identified in chromosome 18 in one family and this finding was supported by results from other families. The results also implied the existence of other loci both for second premolar agenesis and for incisor agenesis. On the other hand the results did not lend support for comprehensive involvement of the most obvious candidate genes in the etiology of incisor and premolar hypodontia. Rather, they suggest remarkable genetic heterogeneity of tooth agenesis. The available evidence suggests that quantitative defects during tooth development predispose to a failure to overcome a developmental threshold and to agenesis. The results of the study increase the understanding of the etiology and heredity of tooth agenesis. Further studies may lead to identification of novel genes that affect the development of teeth.

Mu in vitro Transposition Technology in Functional Genetics and Genomics: Applications on Mouse and Bacteriophages

Transposons are mobile elements of genetic material that are able to move in the genomes of their host organisms using a special form of recombination called transposition. Bacteriophage Mu was the first transposon for which a cell-free in vitro transposition reaction was developed. Subsequently, the reaction has been refined and the minimal Mu in vitro reaction is useful in the generation of comprehensive libraries of mutant DNA molecules that can be used in a variety of applications. To date, the functional genetics applications of Mu in vitro technology have been subjected to either plasmids or genomic regions and entire genomes of viruses cloned on specific vectors. This study expands the use of Mu in vitro transposition in functional genetics and genomics by describing novel methods applicable to the targeted transgenesis of mouse and the whole-genome analysis of bacteriophages. The methods described here are rapid, efficient, and easily applicable to a wide variety of organisms, demonstrating the potential of the Mu transposition technology in the functional analysis of genes and genomes. First, an easy-to-use, rapid strategy to generate construct for the targeted mutagenesis of mouse genes was developed. To test the strategy, a gene encoding a neuronal K+/Cl- cotransporter was mutagenised. After a highly efficient transpositional mutagenesis, the gene fragments mutagenised were cloned into a vector backbone and transferred into bacterial cells. These constructs were screened with PCR using an effective 3D matrix system. In addition to traditional knock-out constructs, the method developed yields hypomorphic alleles that lead into reduced expression of the target gene in transgenic mice and have since been used in a follow-up study. Moreover, a scheme is devised to rapidly produce conditional alleles from the constructs produced. Next, an efficient strategy for the whole-genome analysis of bacteriophages was developed based on the transpositional mutagenesis of uncloned, infective virus genomes and their subsequent transfer into susceptible host cells. Mutant viruses able to produce viable progeny were collected and their transposon integration sites determined to map genomic regions nonessential to the viral life cycle. This method, applied here to three very different bacteriophages, PRD1, ΦYeO3 12, and PM2, does not require the target genome to be cloned and is directly applicable to all DNA and RNA viruses that have infective genomes. The method developed yielded valuable novel information on the three bacteriophages studied and whole-genome data can be complemented with concomitant studies on individual genes. Moreover, end-modified transposons constructed for this study can be used to manipulate genomes devoid of suitable restriction sites.

The genetic associations of acute anterior uveitis and their overlap with the genetics of ankylosing spondylitis

Acute anterior uveitis (AAU) involves inflammation of the iris and ciliary body of the eye. It occurs both in isolation and as a complication of ankylosing spondylitis (AS). It is strongly associated with HLA-B*27, but previous studies have suggested that further genetic factors may confer additional risk. We sought to investigate this using the Illumina Exomechip microarray, to compare 1504 cases with AS and AAU, 1805 with AS but no AAU and 21 133 healthy controls. We also used a heterogeneity test to test the differences in effect size between AS with AAU and AS without AAU. In the analysis comparing AS+AAU+ cases versus controls, HLA-B*27 and HLA-A*02:01 were significantly associated with the presence of AAU (P<10−300 and P=6 × 10−8, respectively). Secondary independent association with PSORS1C3 (P=4.7 × 10−5) and TAP2 (P=1.1 × 10−5) were observed in the major histocompatibility complex. There was a new suggestive association with a low-frequency variant at zinc-finger protein 154 in the AS without AAU versus control analysis (zinc-finger protein 154 (ZNF154), P=2.2 × 10−6). Heterogeneity testing showed that rs30187 in ERAP1 has a larger effect on AAU compared with that in AS alone. These findings also suggest that variants in ERAP1 have a differential impact on the risk of AAU when compared with AS, and hence the genetic risk for AAU differs from AS.

Genetics of ankylosing spondylitis - Insights into pathogenesis

Ankylosing spondylitis (AS), an immune-mediated arthritis, is the prototypic member of a group of conditions known as spondyloarthropathies that also includes reactive arthritis, psoriatic arthritis and enteropathic arthritis. Patients with these conditions share a clinical predisposition for spinal and pelvic joint dysfunction, as well as genetic associations, notably with HLA-B*27. Spondyloarthropathies are characterized by histopathological inflammation in entheses (regions of high mechanical stress where tendons and ligaments insert into bone) and in the subchondral bone marrow, and by abnormal osteoproliferation at involved sites. The association of AS with HLA-B*27, first described >40 years ago, led to hope that the cause of the disease would be rapidly established. However, even though many theories have been advanced to explain how HLA-B*27 is involved in AS, no consensus about the answers to this question has been reached, and no successful treatments have yet been developed that target HLA-B27 or its functional pathways. Over the past decade, rapid progress has been made in discovering further genetic associations with AS that have shed new light on the aetiopathogenesis of the disease. Some of these discoveries have driven translational ideas, such as the repurposing of therapeutics targeting the cytokines IL-12 and IL-23 and other factors downstream of this pathway. AS provides an excellent example of how hypothesis-free research can lead to major advances in understanding pathogenesis and to the development of innovative therapeutic strategies.

Gene Expression : From Microarrays to Functional Genomics

The time of the large sequencing projects has enabled unprecedented possibilities of investigating more complex aspects of living organisms. Among the high-throughput technologies based on the genomic sequences, the DNA microarrays are widely used for many purposes, including the measurement of the relative quantity of the messenger RNAs. However, the reliability of microarrays has been strongly doubted as robust analysis of the complex microarray output data has been developed only after the technology had already been spread in the community. An objective of this study consisted of increasing the performance of microarrays, and was measured by the successful validation of the results by independent techniques. To this end, emphasis has been given to the possibility of selecting candidate genes with remarkable biological significance within specific experimental design. Along with literature evidence, the re-annotation of the probes and model-based normalization algorithms were found to be beneficial when analyzing Affymetrix GeneChip data. Typically, the analysis of microarrays aims at selecting genes whose expression is significantly different in different conditions followed by grouping them in functional categories, enabling a biological interpretation of the results. Another approach investigates the global differences in the expression of functionally related groups of genes. Here, this technique has been effective in discovering patterns related to temporal changes during infection of human cells. Another aspect explored in this thesis is related to the possibility of combining independent gene expression data for creating a catalog of genes that are selectively expressed in healthy human tissues. Not all the genes present in human cells are active; some involved in basic activities (named housekeeping genes) are expressed ubiquitously. Other genes (named tissue-selective genes) provide more specific functions and they are expressed preferably in certain cell types or tissues. Defining the tissue-selective genes is also important as these genes can cause disease with phenotype in the tissues where they are expressed. The hypothesis that gene expression could be used as a measure of the relatedness of the tissues has been also proved. Microarray experiments provide long lists of candidate genes that are often difficult to interpret and prioritize. Extending the power of microarray results is possible by inferring the relationships of genes under certain conditions. Gene transcription is constantly regulated by the coordinated binding of proteins, named transcription factors, to specific portions of the its promoter sequence. In this study, the analysis of promoters from groups of candidate genes has been utilized for predicting gene networks and highlighting modules of transcription factors playing a central role in the regulation of their transcription. Specific modules have been found regulating the expression of genes selectively expressed in the hippocampus, an area of the brain having a central role in the Major Depression Disorder. Similarly, gene networks derived from microarray results have elucidated aspects of the development of the mesencephalon, another region of the brain involved in Parkinson Disease.

Evolutionary Genetics in the WIld : from Populations to Individuals

Predicting evolutionary outcomes and reconstructing past evolutionary transitions are among the main goals of evolutionary biology. Ultimately, understanding the mechanisms of evolutionary change will also provide answers to the timely question of whether and how organisms will adapt to changing environmental conditions. In this thesis, I have investigated the relative roles of natural selection, random genetic drift and genetic correlations in the evolution of complex traits at different levels of organisation from populations to individuals. I have shown that natural selection has been the driving force behind body shape divergence of marine and freshwater threespine stickleback (Gasterosteus aculeatus) populations, while genetic drift may have played a significant role in the more fine scale divergence among isolated freshwater populations. These results are concurrent with the patterns that have emerged in the published studies comparing the relative importance of natural selection and genetic drift as explanations for population divergence in different traits and taxa. I have also shown that body shape and armour divergence among threespine stickleback populations is likely to be biased by the patterns of genetic variation and covariation. Body shape and armour variation along the most likely direction of evolution the direction of maximum genetic variance reflects the general patterns of variation observed wild populations across the distribution range of the threespine stickleback. Conversely, it appears that genetic correlations between the sexes have not imposed significant constraints on the evolution of sexual dimorphism in threespine stickleback body shape and armour. I have demonstrated that the patterns of evolution seen in the wild can be experimentally recreated to tease out the effects of different selection agents in detail. In addition, I have shown how important it is to take into account the correlative nature of traits, when making interpretations about the effects of natural selection on individual traits. Overall, this thesis provides a demonstration of how considering the relative roles of different mechanism of evolutionary change at different levels of organisation can aid in an emergence of a comprehensive picture of how adaptive divergence in wild populations occurs.

Behavioural and physiological responses to predators of captive-bred Arctic charr: significance of genetics, learning and ontogeny

Predation forms one of the main selective forces in nature and in a vast number of prey species the behavioural responses form the main way to avoid predation. World wide numerous captive breeding programs are used to produce fish and other animal species for conservational reintroductions. However, rearing animals in the absence of predators in captivity has been shown to weaken their predator avoidance skills and lead to behavioural divergence between wild and captive-bred populations. In my thesis I studied the effects of predator odour exposures on antipredator behavioural and physiological responses of captive reared Saimaa Arctic charr. This charr population is the most endangered fish population in Finland and a sample of the remaining population has been taken to captive breeding and used for an extensive reintroduction program. Lowered responsiveness to predators is probably one of the major reasons for the poor survival probability of the charr after release into the wild. The main aims of my thesis were to explore the reasons for behavioural phenotypic variation in this charr population and whether naïve charr young could be trained to recognise their natural predators. The predator species in my thesis were burbot (Lota lota) and pikeperch (Sander lucioperca). In my thesis I showed that the captive-bred charr responded to chemical cues from burbot and pikeperch, but the magnitude of responses was linked to the predator species. The burbot odour increased the spatial odour avoidance of the charr young. On the other hand, in the pikeperch treatment charr reduced their relative swimming activity and tended to show more freezing behaviour relative to the burbot treatment. It seems evident that these different responses are related to the different hunting tactics of predator species. Furthermore, I detected wide between-family differences in antipredator responsiveness (i.e. inherited variation in antipredator behaviours) in this captive stock. Detected differences were greater in the response towards burbot than towards pikeperch. These results, in addition to predator-specific antipredator responses, suggest that there is a clear inherited component in antipredator responsiveness in Saimaa charr population and that the detected inherited differences could explain a part of the behavioural phenotypic variation in this population. In my thesis I also found out that both social learning and direct exposure to live predators enhance the antipredator responsiveness of charr young. In addition, I obtained indications that predator odour exposures (i.e. life-skills training) in alevin and fry stages can fine-tune the innate antipredator responsiveness of charr. Thus, all these methods have the potential to enhance the innate antipredator responsiveness of naïve charr young, possibly also improving the post-release survival of these trained individuals in the wild. However, the next logical phase would be to carry out large scale survival studies in the wild to test this hypothesis. Finally, the results of my thesis emphasize that possible long-term life-skills training methods should take into account not only the behavioural but also the physiological effects of training.

A Proof of Convergence of the B-RED and P-RED Algorithms for Random Early Detection

In [8], we recently presented two computationally efficient algorithms named B-RED and P-RED for random early detection. In this letter, we present the mathematical proof of convergence of these algorithms under general conditions to local minima.