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.

Systematic search for optical Barker codes with minimum length

A method that yields optical Barker codes of smallest known lengths for given discrimination is described.

Resistance Minimum in Dilute Magnetic Alloys in the Absence of Impurity Moments

A possible mechanism for the resistance minimum in dilute alloys in which the localized impurity states are non-magnetic is suggested. The fact is considered that what is essential to the Kondo-like behaviour is the interaction of the conduction electron spin s with the internal dynamical degrees of freedom of the impurity centre. The necessary internal dynamical degrees of freedom are provided by the dynamical Jahn-Teller effect associated with the degenerate 3d-orbitals of the transition-metal impurities interacting with the surrounding (octahedral) complex of the nearest-neighbour atoms. The fictitious spin I characterizing certain low-lying vibronic states of the system is shown to couple with the conduction electron spin s via s-d mixing and spin-orbit coupling, giving rise to a singular temperature-dependent exchange-like interaction. The resistivity so calculated is in fair agreement with the experimental results of Cape and Hake for Ti containing 0.2 at% of Fe.

Location of concentrators in a computer communication network: a stochastic automation search method

The following problem is considered. Given the locations of the Central Processing Unit (ar;the terminals which have to communicate with it, to determine the number and locations of the concentrators and to assign the terminals to the concentrators in such a way that the total cost is minimized. There is alao a fixed cost associated with each concentrator. There is ail upper limit to the number of terminals which can be connected to a concentrator. The terminals can be connected directly to the CPU also In this paper it is assumed that the concentrators can bo located anywhere in the area A containing the CPU and the terminals. Then this becomes a multimodal optimization problem. In the proposed algorithm a stochastic automaton is used as a search device to locate the minimum of the multimodal cost function . The proposed algorithm involves the following. The area A containing the CPU and the terminals is divided into an arbitrary number of regions (say K). An approximate value for the number of concentrators is assumed (say m). The optimum number is determined by iteration later The m concentrators can be assigned to the K regions in (mk) ways (m > K) or (km) ways (K>m).(All possible assignments are feasible, i.e. a region can contain 0,1,…, to concentrators). Each possible assignment is assumed to represent a state of the stochastic variable structure automaton. To start with, all the states are assigned equal probabilities. At each stage of the search the automaton visits a state according to the current probability distribution. At each visit the automaton selects a 'point' inside that state with uniform probability. The cost associated with that point is calculated and the average cost of that state is updated. Then the probabilities of all the states are updated. The probabilities are taken to bo inversely proportional to the average cost of the states After a certain number of searches the search probabilities become stationary and the automaton visits a particular state again and again. Then the automaton is said to have converged to that state Then by conducting a local gradient search within that state the exact locations of the concentrators are determined This algorithm was applied to a set of test problems and the results were compared with those given by Cooper's (1964, 1967) EAC algorithm and on the average it was found that the proposed algorithm performs better.

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.

Application of the Conjugate Gradient Method to a Problem on Minimum Time Orbit Transfer

This correspondence considers the problem of optimally controlling the thrust steering angle of an ion-propelled spaceship so as to effect a minimum time coplanar orbit transfer from the mean orbital distance of Earth to mean Martian and Venusian orbital distances. This problem has been modelled as a free terminal time-optimal control problem with unbounded control variable and with state variable equality constraints at the final time. The problem has been solved by the penalty function approach, using the conjugate gradient algorithm. In general, the optimal solution shows a significant departure from earlier work. In particular, the optimal control in the case of Earth-Mars orbit transfer, during the initial phase of the spaceship's flight, is found to be negative, resulting in the motion of the spaceship within the Earth's orbit for a significant fraction of the total optimized orbit transfer time. Such a feature exhibited by the optimal solution has not been reported at all by earlier investigators of this problem.

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.

Normalized Two Stage SVQ for Minimum Complexity Wide-band LSF Quantization

We develop a two stage split vector quantization method with optimum bit allocation, for achieving minimum computational complexity. This also results in much lower memory requirement than the recently proposed switched split vector quantization method. To improve the rate-distortion performance further, a region specific normalization is introduced, which results in 1 bit/vector improvement over the typical two stage split vector quantizer, for wide-band LSF quantization.

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

Optimum design of Lanchester damper for a viscously damped single degree of freedom system by using minimum force transmissibility criterion

The problem of optimum design of a Lanchester damper for minimum force transmission from a viscously damped single degree of freedom system subjected to harmonic excitation is investigated. Explicit expressions are developed for determining the optimum absorber parameters. It is shown that for the particular case of the undamped single degree of freedom system the results reduce to the classical ones obtained by using the concept of a fixed point on the transmissibility curves.

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.

A possible explanation of the Maunder minimum from a flux transport dynamo model

We propose that the poloidal field at the end of the last sunspot cycle before the Maunder minimum fell to a very low value due to fluctuations in the Babcock-Leighton process. With this assumption, a flux transport dynamo model is able to explain various aspects of the historical records of the Maunder minimum remarkably well by suitably choosing the parameters of the model to give the correct growth time.

The electronic factor in Bergman cyclization

Through-bond interactions in 1,4-dehydrobenzene preferentially stabilize the out-of-phase combination of the radical hydrids, The resultant splitting between the frontier orbitals is crucial in making Bergman cyclization a symmetry-allowed process. Orbital symmetry also inhibits the radical centers from forming a C-C bond, enabling the biradical to survive as a local minimum capable of intermolecular hydrogen abstraction, Both these factors, which are important in the design of DNA cleaving molecules, are confirmed through calculations on biradicals formed from diynes in which through-bond interactions stabilize the in-phase combination of hybrids at the radical centers.