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.

Mixed Convection Induced in a Gas Flowing Past a Hot Horizontal Flat Plate

A boundary layer analysis of mixed convective motion over a hot horizontal flat plate is performed under the conditions of steady flow and low speed. Use of the Howarth-Dorodnytsyn transformation makes it possible to dispense with the usual Boussinesq approximation, and variable gas properties are accounted for via the assumption that dynamic viscosity and thermal conductivity are proportional to the absolute temperature. The formulation presented enables the entire mixed convection regime to be described by a single set of equations. Finite difference solutions when the Prandtl number is 0.72 are obtained over the entire range of the mixed convection parameter ξ from 0 (free convection) to 1 (forced convection) and heating parameter ▵ values from 2 to 12. The effects of both ξ and ▵on the velocity profiles, the temperature profiles, and the variation of skin friction and heat transfer functions are clearly illustrated in tables and graphs.

Stress-strain characteristics of Tress-strain characteristics of reinforcing steel bars under cyclic loading

This paper presents test results for 22 high strength deformed bars and nine mild steel bars subjected to monotonic repeated and reversed axial loading to determine the stress-strain behavior. Equations have been proposed for the stress-strain curves and have been compared with test results. Satisfactory agreement was obtained.

Processing map for hot working of alpha-zirconium

The hot deformation characteristics of alpha-zirconium in the temperature range of 650 °C to 850 °C and in the strain-rate range of 10-3 to 102 s-1 are studied with the help of a power dissipation map developed on the basis of the Dynamic Materials Model.[7,8,9] The processing map describes the variation of the efficiency of power dissipation (η =2m/m + 1) calculated on the basis of the strain-rate sensitivity parameter (m), which partitions power dissipation between thermal and microstructural means. The processing map reveals a domain of dynamic recrystallization in the range of 730 °C to 850 °C and 10−2 to 1−1 with its peak efficiency of 40 pct at 800 °C and 0.1 s-1 which may be considered as optimum hot-working parameters. The characteristics of dynamic recrystallization are similar to those of static recrystallization regarding the sigmoidal variation of grain size (or hardness) with temperature, although the dynamic recrystallization temperature is much higher. When deformed at 650 °C and 10-3 s-1 texture-induced dynamic recovery occurred, while at strain rates higher than 1 s-1, alpha-zirconium exhibits microstructural instabilities in the form of localized shear bands which are to be avoided in processing.

Stress-Strain Characteristics of Reinforcing Steel Bars Under Cyclic Loading

This paper presents test results for 22 high strength deformed bars and nine mild steel bars subjected to monotonic repeated and reversed axial loading to determine the stress-strain behavior. Equations have been proposed for the stress-strain curves and have been compared with test results. Satisfactory agreement was obtained.

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

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.

Optimisation problems in wireless sensor networks

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.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

Inelastic response of beams under sinusoidal and random loads

A new analytical model has been suggested for the hysteretic behaviour of beams. The model can be directly used in a response analysis without bothering to locate the precise point where the unloading commences. The model can efficiently simulate several types of realistic softening hysteretic loops. This is demonstrated by computing the response of cantilever beams under sinusoidal and random loadings. Results are presented in the form of graphs for maximum deflection, bending moment and shear

Macroscopic model of city traffic using bond graph modelling

Modelling of city traffic involves capturing of all the dynamics that exist in real-time traffic. Probabilistic models and queuing theory have been used for mathematical representation of the traffic system. This paper proposes the concept of modelling the traffic system using bond graphs wherein traffic flow is based on energy conservation. The proposed modelling approach uses switched junctions to model complex traffic networks. This paper presents the modelling, simulation and experimental validation aspects.

On characterization of deformation microstructure in Boron modified Ti-6Al-4V alloy

Addition of boron in small quantities to various titanium alloys have shown significant improvement in mechanical behavior of materials. In the present study, electron back-scatter diffraction (EBSD) techniques have been applied to investigate the deformation microstructure evolution in boron modified two-phase titanium alloy Ti-6Al-4V. The alloy was hot compressed at 750 degrees C up to 50% height reduction at two different strain rates (10(-3) s(-1) and 1 s(-1)). The EBSD analyses indicated significant differences in deformed microstructure of the base alloy and the alloy containing boron. A strong subgrain formation tendency was observed along with inhomogeneous distribution of dislocations inside large a colonies of Ti64. In contrast, a colonies were relatively strain free for Ti64 + B, with more uniform dislocation density distribution. The observed difference is attributed to microstructural modifications viz, grain size refinement and presence of TiB particles at grain boundary produced due to boron addition. (C) 2010 Elsevier B.V. All rights reserved.

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).

Planar subgraphs without low-degree nodes

We study the following problem: given a geometric graph G and an integer k, determine if G has a planar spanning subgraph (with the original embedding and straight-line edges) such that all nodes have degree at least k. If G is a unit disk graph, the problem is trivial to solve for k = 1. We show that even the slightest deviation from the trivial case (e.g., quasi unit disk graphs or k = 1) leads to NP-hard problems.

Relation-Aware Isosurface Extraction in Multifield Data

We introduce a variation density function that profiles the relationship between multiple scalar fields over isosurfaces of a given scalar field. This profile serves as a valuable tool for multifield data exploration because it provides the user with cues to identify interesting isovalues of scalar fields. Existing isosurface-based techniques for scalar data exploration like Reeb graphs, contour spectra, isosurface statistics, etc., study a scalar field in isolation. We argue that the identification of interesting isovalues in a multifield data set should necessarily be based on the interaction between the different fields. We demonstrate the effectiveness of our approach by applying it to explore data from a wide variety of applications.