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.

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.

Development of a transient gradient enhanced non local continuum damage mechanics model for masonry

Due to the advent of varied types of masonry systems a comprehensive failure mechanism of masonry essential for the understanding of its behaviour is impossible to be determined from experimental testing. As masonry is predominantly used in wall structures a biaxial stress state dominates its failure mechanism. Biaxial testing will therefore be necessary for each type of masonry, which is expensive and time consuming. A computational method would be advantageous; however masonry is complex to model which requires advanced computational modelling methods. This thesis has formulated a damage mechanics inspired modelling method and has shown that the method effectively determines the failure mechanisms and deformation characteristics of masonry under biaxial states of loading.

Inhibition of Human Two-Pore Domain K+ Channel TREK1 by Local Anesthetic Lidocaine: Negative Cooperativity and Half-of-Sites Saturation Kinetics

TWIK-related K+ channel TREK1, a background leak K+ channel, has been strongly implicated as the target of several general and local anesthetics. Here, using the whole-cell and single-channel patch-clamp technique, we investigated the effect of lidocaine, a local anesthetic, on the human (h) TREK1 channel heterologously expressed in human embryonic kidney 293 cells by an adenoviral-mediated expression system. Lidocaine, at clinical concentrations, produced reversible, concentration-dependent inhibition of hTREK1 current, with IC50 value of 180 mu M, by reducing the single-channel open probability and stabilizing the closed state. We have identified a strategically placed unique aromatic couplet (Tyr352 and Phe355) in the vicinity of the protein kinase A phosphorylation site, Ser348, in the C-terminal domain (CTD) of hTREK1, that is critical for the action of lidocaine. Furthermore, the phosphorylation state of Ser348 was found to have a regulatory role in lidocaine-mediated inhibition of hTREK1. It is interesting that we observed strong intersubunit negative cooperativity (Hill coefficient = 0.49) and half-of-sites saturation binding stoichiometry (half-reaction order) for the binding of lidocaine to hTREK1. Studies with the heterodimer of wild-type (wt)-hTREK1 and Delta 119 C-terminal deletion mutant (hTREK1(wt)-Delta 119) revealed that single CTD of hTREK1 was capable of mediating partial inhibition by lidocaine, but complete inhibition necessitates the cooperative interaction between both the CTDs upon binding of lidocaine. Based on our observations, we propose a model that explains the unique kinetics and provides a plausible paradigm for the inhibitory action of lidocaine on hTREK1.

Chapter 1: Precarious creativity: Global media, local labor

In most parts of the world, screen media workers—actors, directors, gaffers, and makeup artists—consider Hollywood to be glamorous and aspirational. If given the opportunity to work on a major studio lot, many would make the move, believing the standards of professionalism are high and the history of accomplishment is renowned. Moreover, as a global leader, Hollywood offers the chance to rub shoulders with talented counterparts and network with an elite labor force that earns top-tier pay and benefits. Yet despite this reputation, veterans say the view from inside isn’t so rosy, that working conditions have been deteriorating since the 1990s if not earlier. This grim outlook is supported by industry statistics that show the number of good jobs has been shrinking as studios outsource production to Atlanta, London, and Budapest, among others...

On the computation of two-dimensional compressible flow fields by the modified local stability scheme

The modified local stability scheme is applied to several two-dimensional problems—blunt body flow, regular reflection of a shock and lambda shock. The resolution of the flow features obtained by the modified local stability scheme is found to be better than that achieved by the other first order schemes and almost identical to that achieved by the second order schemes incorporating artificial viscosity. The scheme is easy for coding, consumes moderate amount of computer storage and time. The scheme can be advantageously used in place of second order schemes.

Significance of Branching Angles in Streamer Discharges

The phenomenon of branching at specific angles in streamer breakdown studies is found to be more universal than was ever thought. The angles measured in the breakdown of gases show that the coefficient of field distortion, K, lies in the range from 1 to less than 0.1. The values of K, so obtained agree well with those envisaged in the criterion of the streamer mechanism. It is hoped that branching angles observed in various types of breakdown may, possibly, be explained similarly.

CADASIL: molecular studies on the most common hereditary vascular dementing disorder

Cerebral Autosomal Dominant Arteriopathy with Subcortical Infarcts and Leukoencephalopathy (CADASIL) is the most common hereditary vascular dementia. CADASIL is a systemic disease of small and medium-sized arteries although the symptoms are almost exclusively neurological, including migraineous headache, recurrent ischemic episodes, cognitive impairment and, finally, subcortical dementia. CADASIL is caused by over 170 different mutations in the NOTCH3 gene, which encodes a receptor expressed in adults predominantly in the vascular smooth muscle cells. The function of NOTCH3 is not crucial for embryonic development but is needed after birth. NOTCH3 directs postnatal arterial maturation and helps to maintain arterial integrity. It is involved in regulation of vascular tone and in the wound healing of a vascular injury. In addition, NOTCH3 promotes cell survival by inducing expression of anti-apoptotic proteins. NOTCH3 is a membrane-spanning protein with a large extracellular domain (N3ECD) containing 34 epidermal growth factor-like (EGF) repeats and a smaller intracellular domain with six ankyrin repeats. All CADASIL mutations are located in the EGF repeats and the majority of the mutations cause gain or loss of one cysteine residue in one of these repeats leading to an odd number of cysteine residues, which in turn leads to misfolding of N3ECD. This misfolding most likely alters the maturation, targetting, degradation and/or function of the NOTCH3 receptor. CADASIL mutations do not seem to affect the canonical NOTCH3 signalling pathway. The main pathological findings are the accumulation of the NOTCH3 extracellular domain on degenerating vascular smooth muscle cells (VSMCs), accumulation of granular osmiophilic material (GOM) in the close vicinity of VSMCs as well as fibrosis and thickening of arterial walls. Narrowing of the arterial lumen and local thrombosis cause insufficient blood flow, mainly in small arteries of the cerebral white matter, resulting in tissue damage and lacunar infarcts. CADASIL is suspected in patients with a suggestive family history and clinical picture as well as characteristic white matter alterations in magnetic resonance imaging. A definitive verification of the diagnosis can be achieved by identifying a pathogenic mutation in the NOTCH3 gene or through the detection of GOM by electron microscopy. To understand the pathology underlying CADASIL, we have generated a unique set of cultured vascular smooth muscle cell (VSMC) lines from umbilical cord, placental, systemic and cerebral arteries of CADASIL patients and controls. Analyses of these VSMCs suggest that mutated NOTCH3 is misfolded, thus causing endoplasmic reticulum stress, activation of the unfolded protein response and increased production of reactive oxygen species. In addition, mutation in NOTCH3 causes alterations in actin cytoskeletal structures and protein expression, increased branching and abnormal node formation. These changes correlate with NOTCH3 expression levels within different VSMCs lines, suggesting that the phenotypic differences of SMCs may affect the vulnerability of the VSMCs and, therefore, the pathogenic impact of mutated NOTCH3 appears to vary in the arteries of different locations. Furthermore, we identified PDGFR- as an immediate downstream target gene of NOTCH3 signalling. Activation of NOTCH induces up-regulation of the PDGFR- expression in control VSMCs, whereas this up-regulation is impaired in CADASIL VSMCs and might thus serve as an alternative molecular mechanism that contributes to CADASIL pathology. In addition, we have established the congruence between NOTCH3 mutations and electron microscopic detection of GOM with a view to constructing a strategy for CADASIL diagnostics. In cases where the genetic analysis is not available or the mutation is difficult to identify, a skin biopsy is an easy-to-perform and highly reliable diagnostic method. Importantly, it is invaluable in setting guidelines concerning how far one should proceed with the genetic analyses.

Characterization of a local isolate of Bombyx mori nuclear polyhedrosis virus

Polyhedral bodies of Bombyx mori nuclear polyhedrosis virus, BmNPV (BGL) isolated from infected silkworms around Bangalore were propagated either in the cultured B. mori cell line, BmN or through infection of larvae. Electron microscopic (EM) observations of the polyhedra revealed an average length of 2 mu m and a height of 0.5 mu m. The purified polyhedra derived virions (PDV) showed several bands in sucrose gradient centrifugation, indicating the multiple nucleocapsid nature of BmNPV. Electron microscopic studies of PDV revealed a cylindrical, rod-shaped nucleocapsid with an average length of 300 nm and a diameter of 35 nm. The genomic DNA from the PDV was characterized by extensive restriction analysis and the genome size was estimated to be 132 kb. The restriction pattern of BmNPV (BGL) resembled that of the prototype strain BmNPV-T3. Distinct differences due to polymorphic sites for restriction enzyme HindIII were apparent between BmNPV (BGL) and the virus isolated from a different part of Karnataka (Dharwad area), BmNPV (DHR).

A combination of local inflammation and central memory T cells potentiates immunotherapy in the skin

Adoptive T cell therapy uses the specificity of the adaptive immune system to target cancer and virally infected cells. Yet the mechanism and means by which to enhance T cell function are incompletely described, especially in the skin. In this study, we use a murine model of immunotherapy to optimize cell-mediated immunity in the skin. We show that in vitro - derived central but not effector memory-like T cells bring about rapid regression of skin-expressing cognate Ag as a transgene in keratinocytes. Local inflammation induced by the TLR7 receptor agonist imiquimod subtly yet reproducibly decreases time to skin graft rejection elicited by central but not effector memory T cells in an immunodeficient mouse model. Local CCL4, a chemokine liberated by TLR7 agonism, similarly enhances central memory T cell function. In this model, IL-2 facilitates the development in vivo of effector function from central memory but not effector memory T cells. In a model of T cell tolerogenesis, we further show that adoptively transferred central but not effector memory T cells can give rise to successful cutaneous immunity, which is dependent on a local inflammatory cue in the target tissue at the time of adoptive T cell transfer. Thus, adoptive T cell therapy efficacy can be enhanced if CD8+ T cells with a central memory T cell phenotype are transferred, and IL-2 is present with contemporaneous local inflammation. Copyright © 2012 by The American Association of Immunologists, Inc.

Beyond fractional derivatives: local approximation of other convolution integrals

Dynamic systems involving convolution integrals with decaying kernels, of which fractionally damped systems form a special case, are non-local in time and hence infinite dimensional. Straightforward numerical solution of such systems up to time t needs O(t(2)) computations owing to the repeated evaluation of integrals over intervals that grow like t. Finite-dimensional and local approximations are thus desirable. We present here an approximation method which first rewrites the evolution equation as a coupled in finite-dimensional system with no convolution, and then uses Galerkin approximation with finite elements to obtain linear, finite-dimensional, constant coefficient approximations for the convolution. This paper is a broad generalization, based on a new insight, of our prior work with fractional order derivatives (Singh & Chatterjee 2006 Nonlinear Dyn. 45, 183-206). In particular, the decaying kernels we can address are now generalized to the Laplace transforms of known functions; of these, the power law kernel of fractional order differentiation is a special case. The approximation can be refined easily. The local nature of the approximation allows numerical solution up to time t with O(t) computations. Examples with several different kernels show excellent performance. A key feature of our approach is that the dynamic system in which the convolution integral appears is itself approximated using another system, as distinct from numerically approximating just the solution for the given initial values; this allows non-standard uses of the approximation, e. g. in stability analyses.