Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Optimal reservoir operation for irrigation of multiple crops using genetic algorithms

This paper presents a genetic algorithm (GA) model for obtaining an optimal operating policy and optimal crop water allocations from an irrigation reservoir. The objective is to maximize the sum of the relative yields from all crops in the irrigated area. The model takes into account reservoir inflow, rainfall on the irrigated area, intraseasonal competition for water among multiple crops, the soil moisture dynamics in each cropped area, the heterogeneous nature of soils. and crop response to the level of irrigation applied. The model is applied to the Malaprabha single-purpose irrigation reservoir in Karnataka State, India. The optimal operating policy obtained using the GA is similar to that obtained by linear programming. This model can be used for optimal utilization of the available water resources of any reservoir system to obtain maximum benefits.

Integration-free algorithms for fixed end-point regulator problems

A new formulation is suggested for the fixed end-point regulator problem, which, in conjunction with the recently developed integration-free algorithms, provides an efficient means of obtaining numerical solutions to such problems.

Population genetics of the invasive plant species Impatiens glandulifera in Southern Finland

Biological invasions affect biodiversity worldwide, and, consequently, the invaded ecosystems may suffer from significant losses in economic and cultural values. Impatiens glandulifera Royle (Balsaminaceae) is an invasive annual herb, native to the western Himalayas and introduced into Europe in the 19th century as a garden ornamental plant. The massive invasion of I. glandulifera is due to its high reproductive output, rapid growth and its ability to outcompete native species. In Finland, the first observations regarding the presence of I. glandulifera date from the year 1947, and today it is considered a serious problem in riparian habitats. The aim of this master’s thesis research is to reveal the population genetic structure of I. glandulifera in Finland and to find out whether there have been one or multiple invasions in Finland. The study focuses on investigating the origin of I. glandulifera in Southern Finland, by comparing plant samples from the Helsinki region with those from its native region and other regions of invasion. Samples from four populations in Helsinki and from the United Kingdom, Canada, India and Pakistan were collected and genotyped using 11 microsatellite markers. The genetic analyses were evaluated using the programs Arlequin and Structure. The results of the genetic analyses suggested that I. glandulifera has been introduced to Finland more than once. Multiple introductions are supported by the higher level of genetic diversity detected within and among Finnish populations than would be expected for a single introduction. Results of the Bayesian Structure analysis divided the four Finnish populations into four clusters. This geographical structure was further supported by pairwise Fst values among populations. The causes and potential consequences of such multiple introductions of I. glandulifera in Finland and further perspectives are discussed.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Simulation and graph mining tools for improving gene mapping efficiency

Gene mapping is a systematic search for genes that affect observable characteristics of an organism. In this thesis we offer computational tools to improve the efficiency of (disease) gene-mapping efforts. In the first part of the thesis we propose an efficient simulation procedure for generating realistic genetical data from isolated populations. Simulated data is useful for evaluating hypothesised gene-mapping study designs and computational analysis tools. As an example of such evaluation, we demonstrate how a population-based study design can be a powerful alternative to traditional family-based designs in association-based gene-mapping projects. In the second part of the thesis we consider a prioritisation of a (typically large) set of putative disease-associated genes acquired from an initial gene-mapping analysis. Prioritisation is necessary to be able to focus on the most promising candidates. We show how to harness the current biomedical knowledge for the prioritisation task by integrating various publicly available biological databases into a weighted biological graph. We then demonstrate how to find and evaluate connections between entities, such as genes and diseases, from this unified schema by graph mining techniques. Finally, in the last part of the thesis, we define the concept of reliable subgraph and the corresponding subgraph extraction problem. Reliable subgraphs concisely describe strong and independent connections between two given vertices in a random graph, and hence they are especially useful for visualising such connections. We propose novel algorithms for extracting reliable subgraphs from large random graphs. The efficiency and scalability of the proposed graph mining methods are backed by extensive experiments on real data. While our application focus is in genetics, the concepts and algorithms can be applied to other domains as well. We demonstrate this generality by considering coauthor graphs in addition to biological graphs in the experiments.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

Distributed algorithms for edge dominating sets

An edge dominating set for a graph G is a set D of edges such that each edge of G is in D or adjacent to at least one edge in D. This work studies deterministic distributed approximation algorithms for finding minimum-size edge dominating sets. The focus is on anonymous port-numbered networks: there are no unique identifiers, but a node of degree d can refer to its neighbours by integers 1, 2, ..., d. The present work shows that in the port-numbering model, edge dominating sets can be approximated as follows: in d-regular graphs, to within 4 − 6/(d + 1) for an odd d and to within 4 − 2/d for an even d; and in graphs with maximum degree Δ, to within 4 − 2/(Δ − 1) for an odd Δ and to within 4 − 2/Δ for an even Δ. These approximation ratios are tight for all values of d and Δ: there are matching lower bounds.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Molecular genetics of Usher syndrome -inherited deafness and blindness

Usher syndrome (USH) is an inherited blindness and deafness disorder with variable vestibular dysfunction. The syndrome is divided into three subtypes according to the progression and severity of clinical symptoms. The gene mutated in Usher syndrome type 3 (USH3), clarin 1 (CLRN1), was identified in Finland in 2001 and two mutations were identified in Finnish patients at that time. Prior to this thesis study, the two CLRN1 gene mutations were the only USH mutations identified in Finnish USH patients. To further clarify the Finnish USH mutation spectrum, all nine USH genes were studied. Seven mutations were identified: one was a previously known mutation in CLRN1, four were novel mutations in myosin VIIa (MYO7A) and two were a novel and a previously known mutation in usherin (USH2A). Another aim of this thesis research was to further study the structure and function of the CLRN1 gene, and to clarify the effects of mutations on protein function. The search for new splice variants resulted in the identification of eight novel splice variants in addition to the three splice variants that were already known prior to this study. Studies of the possible promoter regions for these splice variants showed the most active region included the 1000 bases upstream of the translation start site in the first exon of the main three exon splice variant. The 232 aa CLRN1 protein encoded by the main (three-exon) splice variant was transported to the plasma membrane when expressed in cultured cells. Western blot studies suggested that CLRN1 forms dimers and multimers. The CLRN1 mutant proteins studied were retained in the endoplasmic reticulum (ER) and some of the USH3 mutations caused CLRN1 to be unstable. During this study, two novel CLRN1 sequence alterations were identified and their pathogenicity was studied with cell culture protein expression. Previous studies with mice had shown that Clrn1 is expressed in mouse cochlear hair cells and spiral ganglion cells, but the expression profile in mouse retina remained unknown. The Clrn1 knockout mice display cochlear cell disruption/death, but do not have a retinal phenotype. The zebrafish, Danio rerio, clrn1 was found to be expressed in hair cells associated with hearing and balance. Clrn1 expression was also found in the inner nuclear layer (INL), photoreceptor layer and retinal pigment epithelium layer (RPE) of the zebrafish retina. When Clrn1 production was knocked down with injected morpholino oligonucleotides (MO) targeting Clrn1 translation or correct splicing, the zebrafish larvae showed symptoms similar to USH3 patients. These larvae had balance/hearing problems and reduced response to visual stimuli. The knowledge this thesis research has provided about the mutations in USH genes and the Finnish USH mutation spectrum are important in USH patient diagnostics. The extended information about the structure and function of CLRN1 is a step further in exploring USH3 pathogenesis caused by mutated CLRN1 as well as a step in finding a cure for the disease.