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.

Computational Methods for Locating and Analyzing Conserved Gene Regulatory DNA Elements

This thesis presents methods for locating and analyzing cis-regulatory DNA elements involved with the regulation of gene expression in multicellular organisms. The regulation of gene expression is carried out by the combined effort of several transcription factor proteins collectively binding the DNA on the cis-regulatory elements. Only sparse knowledge of the 'genetic code' of these elements exists today. An automatic tool for discovery of putative cis-regulatory elements could help their experimental analysis, which would result in a more detailed view of the cis-regulatory element structure and function. We have developed a computational model for the evolutionary conservation of cis-regulatory elements. The elements are modeled as evolutionarily conserved clusters of sequence-specific transcription factor binding sites. We give an efficient dynamic programming algorithm that locates the putative cis-regulatory elements and scores them according to the conservation model. A notable proportion of the high-scoring DNA sequences show transcriptional enhancer activity in transgenic mouse embryos. The conservation model includes four parameters whose optimal values are estimated with simulated annealing. With good parameter values the model discriminates well between the DNA sequences with evolutionarily conserved cis-regulatory elements and the DNA sequences that have evolved neutrally. In further inquiry, the set of highest scoring putative cis-regulatory elements were found to be sensitive to small variations in the parameter values. The statistical significance of the putative cis-regulatory elements is estimated with the Two Component Extreme Value Distribution. The p-values grade the conservation of the cis-regulatory elements above the neutral expectation. The parameter values for the distribution are estimated by simulating the neutral DNA evolution. The conservation of the transcription factor binding sites can be used in the upstream analysis of regulatory interactions. This approach may provide mechanistic insight to the transcription level data from, e.g., microarray experiments. Here we give a method to predict shared transcriptional regulators for a set of co-expressed genes. The EEL (Enhancer Element Locator) software implements the method for locating putative cis-regulatory elements. The software facilitates both interactive use and distributed batch processing. We have used it to analyze the non-coding regions around all human genes with respect to the orthologous regions in various other species including mouse. The data from these genome-wide analyzes is stored in a relational database which is used in the publicly available web services for upstream analysis and visualization of the putative cis-regulatory elements in the human genome.

Computational Identification of Recessive Mutations in Cancers using High Throughput SNP-arrays

This thesis presents a highly sensitive genome wide search method for recessive mutations. The method is suitable for distantly related samples that are divided into phenotype positives and negatives. High throughput genotype arrays are used to identify and compare homozygous regions between the cohorts. The method is demonstrated by comparing colorectal cancer patients against unaffected references. The objective is to find homozygous regions and alleles that are more common in cancer patients. We have designed and implemented software tools to automate the data analysis from genotypes to lists of candidate genes and to their properties. The programs have been designed in respect to a pipeline architecture that allows their integration to other programs such as biological databases and copy number analysis tools. The integration of the tools is crucial as the genome wide analysis of the cohort differences produces many candidate regions not related to the studied phenotype. CohortComparator is a genotype comparison tool that detects homozygous regions and compares their loci and allele constitutions between two sets of samples. The data is visualised in chromosome specific graphs illustrating the homozygous regions and alleles of each sample. The genomic regions that may harbour recessive mutations are emphasised with different colours and a scoring scheme is given for these regions. The detection of homozygous regions, cohort comparisons and result annotations are all subjected to presumptions many of which have been parameterized in our programs. The effect of these parameters and the suitable scope of the methods have been evaluated. Samples with different resolutions can be balanced with the genotype estimates of their haplotypes and they can be used within the same study.

The fully implicit stochastic-alpha method for stiff stochastic differential equations

A fully implicit integration method for stochastic differential equations with significant multiplicative noise and stiffness in both the drift and diffusion coefficients has been constructed, analyzed and illustrated with numerical examples in this work. The method has strong order 1.0 consistency and has user-selectable parameters that allow the user to expand the stability region of the method to cover almost the entire drift-diffusion stability plane. The large stability region enables the method to take computationally efficient time steps. A system of chemical Langevin equations simulated with the method illustrates its computational efficiency.

Two highly unsymmetrical tetradentate (N3O) Schiff base copper(II) complexes: Template synthesis, structural characterization, magnetic and computational studies

Two new copper(II) complexes, [Cu-2(L-1)(2)](ClO4)(2) (1) and [Cu(L-2)(ClO4)] (2), of the highly unsymmetrical tetradentate (N3O) Schiff base ligands HL1 and HL2 (where HL1 = N-(2-hydroxyacetophenone)-bis-3-aminopropylamine and HL2 = N-(salicyldehydine)-bis-3-aminopropylamine) have been synthesised using a template method. Their single crystal X-ray structures show that in complex 1 two independent copper(II) centers are doubly bridged through sphenoxo-O atoms (O1A and O1B) of the two ligands and each copper atom is five-coordinated with a distorted square pyramidal geometry. The asymmetric unit of complex 2 consists of two crystallographically independe N-(salicylidene) bis(aminopropyl)amine-copper(II) molecules, A and B, with similar square pyramidal geometries. Cryomagnetic susceptibility measurements (5-300 K) on complex 1 reveal a distinct antiferromagnetic interaction with J=-23.6 cm(-1), which is substantiated by a DFT calculation (J=-27.6 cm(-1)) using the B3LYP functional. Complex 1, immobilized over highly ordered hexagonal mesoporous silica, shows moderate catalytic activity for the epoxidation of cyclohexene and styrene in the presence of TBHP as an oxidant.

Bauer Method of MVDR Spectral Factorization for Pitch Modification in the Source Domain

In our earlier work [1], we employed MVDR (minimum variance distortionless response) based spectral estimation instead of modified-linear prediction method [2] in pitch modification. Here, we use the Bauer method of MVDR spectral factorization, leading to a causal inverse filter rather than a noncausal filter setup with MVDR spectral estimation [1]. Further, this is employed to obtain source (or residual) signal from pitch synchronous speech frames. The residual signal is resampled using DCT/IDCT depending on the target pitch scale factor. Finally, forward filters realized from the above factorization are used to get pitch modified speech. The modified speech is evaluated subjectively by 10 listeners and mean opinion scores (MOS) are tabulated. Further, modified bark spectral distortion measure is also computed for objective evaluation of performance. We find that the proposed algorithm performs better compared to time domain pitch synchronous overlap [3] and modified-LP method [2]. A good MOS score is achieved with the proposed algorithm compared to [1] with a causal inverse and forward filter setup.

Thermoelectric Power Under Strong Magnetic Field in Quantum Dots and Quantized Superlattices: Simplified Theory and Relative Comparison

In this paper, we study the thermoelectric power under strong magnetic field (TPSM) in quantum dots (QDs) of nonlinear optical, III-V, II-VI, GaP, Ge, Te, Graphite, PtSb2, zerogap, Lead Germanium Telluride, GaSb, stressed materials, Bismuth, IV-VI, II-V, Zinc and Cadmium diphosphides, Bi2Te3 and Antimony respectively. The TPSM in III-V, II-VI, IV-VI, HgTe/CdTe quantum well superlattices with graded interfaces and effective mass superlattices of the same materials together with the quantum dots of aforementioned superlattices have also been investigated in this context on the basis of respective carrier dispersion laws. It has been found that the TPSM for the said quantum dots oscillates with increasing thickness and decreases with increasing electron concentration in various manners and oscillates with film thickness, inverse quantizing magnetic field and impurity concentration for all types of superlattices with two entirely different signatures of quantization as appropriate in respective cases of the aforementioned quantized structures. The well known expression of the TPSM for wide-gap materials has been obtained as special case for our generalized analysis under certain limiting condition, and this compatibility is an indirect test of our generalized formalism. Besides, we have suggested the experimental method of determining the carrier contribution to elastic constants for nanostructured materials having arbitrary dispersion laws.

Computational fluid dynamics simulations in aerosol and nucleation studies

Nucleation is the first step in the formation of a new phase inside a mother phase. Two main forms of nucleation can be distinguished. In homogeneous nucleation, the new phase is formed in a uniform substance. In heterogeneous nucleation, on the other hand, the new phase emerges on a pre-existing surface (nucleation site). Nucleation is the source of about 30% of all atmospheric aerosol which in turn has noticeable health effects and a significant impact on climate. Nucleation can be observed in the atmosphere, studied experimentally in the laboratory and is the subject of ongoing theoretical research. This thesis attempts to be a link between experiment and theory. By comparing simulation results to experimental data, the aim is to (i) better understand the experiments and (ii) determine where the theory needs improvement. Computational fluid dynamics (CFD) tools were used to simulate homogeneous onecomponent nucleation of n-alcohols in argon and helium as carrier gases, homogeneous nucleation in the water-sulfuric acid-system, and heterogeneous nucleation of water vapor on silver particles. In the nucleation of n-alcohols, vapor depletion, carrier gas effect and carrier gas pressure effect were evaluated, with a special focus on the pressure effect whose dependence on vapor and carrier gas properties could be specified. The investigation of nucleation in the water-sulfuric acid-system included a thorough analysis of the experimental setup, determining flow conditions, vapor losses, and nucleation zone. Experimental nucleation rates were compared to various theoretical approaches. We found that none of the considered theoretical descriptions of nucleation captured the role of water in the process at all relative humidities. Heterogeneous nucleation was studied in the activation of silver particles in a TSI 3785 particle counter which uses water as its working fluid. The role of the contact angle was investigated and the influence of incoming particle concentrations and homogeneous nucleation on counting efficiency determined.

The partition of unity finite element method for elastic wave propagation in Reissner-Mindlin plates

This paper reports a numerical method for modelling the elastic wave propagation in plates. The method is based on the partition of unity approach, in which the approximate spectral properties of the infinite dimensional system are embedded within the space of a conventional finite element method through a consistent technique of waveform enrichment. The technique is general, such that it can be applied to the Lagrangian family of finite elements with specific waveform enrichment schemes, depending on the dominant modes of wave propagation in the physical system. A four-noded element for the Reissner-indlin plate is derived in this paper, which is free of shear locking. Such a locking-free property is achieved by removing the transverse displacement degrees of freedom from the element nodal variables and by recovering the same through a line integral and a weak constraint in the frequency domain. As a result, the frequency-dependent stiffness matrix and the mass matrix are obtained, which capture the higher frequency response with even coarse meshes, accurately. The steps involved in the numerical implementation of such element are discussed in details. Numerical studies on the performance of the proposed element are reported by considering a number of cases, which show very good accuracy and low computational cost. Copyright (C)006 John Wiley & Sons, Ltd.

Direct and Inverse Scattering for Beltrami Fields

We consider an obstacle scattering problem for linear Beltrami fields. A vector field is a linear Beltrami field if the curl of the field is a constant times itself. We study the obstacles that are of Neumann type, that is, the normal component of the total field vanishes on the boundary of the obstacle. We prove the unique solvability for the corresponding exterior boundary value problem, in other words, the direct obstacle scattering model. For the inverse obstacle scattering problem, we deduce the formulas that are needed to apply the singular sources method. The numerical examples are computed for the direct scattering problem and for the inverse scattering problem.

Detection of a periodic structure hidden in random background: the role of signal amplitude in the matched filter detection method

The matched filter method for detecting a periodic structure on a surface hidden behind randomness is known to detect up to (r(0)/Lambda) gt;= 0.11, where r(0) is the coherence length of light on scattering from the rough part and 3 is the wavelength of the periodic part of the surface-the above limit being much lower than what is allowed by conventional detection methods. The primary goal of this technique is the detection and characterization of the periodic structure hidden behind randomness without the use of any complicated experimental or computational procedures. This paper examines this detection procedure for various values of the amplitude a of the periodic part beginning from a = 0 to small finite values of a. We thus address the importance of the following quantities: `(a)lambda) `, which scales the amplitude of the periodic part with the wavelength of light, and (r(0))Lambda),in determining the detectability of the intensity peaks.

New Method for Delexicalization and its Application to Prosodic Tagging for Text-to-Speech Synthesis

This paper describes a new flexible delexicalization method based on glottal excited parametric speech synthesis scheme. The system utilizes inverse filtered glottal flow and all-pole modelling of the vocal tract. The method provides a possibil- ity to retain and manipulate all relevant prosodic features of any kind of speech. Most importantly, the features include voice quality, which has not been properly modeled in earlier delex- icalization methods. The functionality of the new method was tested in a prosodic tagging experiment aimed at providing word prominence data for a text-to-speech synthesis system. The ex- periment confirmed the usefulness of the method and further corroborated earlier evidence that linguistic factors influence the perception of prosodic prominence.

Fractal boundaries of basin of attraction of Newton-Raphson method in helicopter trim

A key problem in helicopter aeroelastic analysis is the enormous computational time required for a numerical solution of the nonlinear system of algebraic equations required for trim, particularly when free wake models are used. Trim requires calculation of the main rotor and tail rotor controls and the vehicle attitude which leads to the six steady forces and moments about the helicopter center of gravity to be zero. An appropriate initial estimate of the trim state is needed for successful helicopter trim. This study aims to determine the control inputs that can have considerable effect on the convergence of trim solution in the aeroelastic analysis of helicopter rotors by investigating the basin of attraction of the nonlinear equations (set of initial guess points from which the nonlinear equations converge). It is illustrated that the three main rotor pitch controls of collective pitch, longitudinal cyclic pitch and lateral cyclic pitch have a significant contribution to the convergence of the trim solution. Trajectories of the Newton iterates are shown and some ideas for accelerating the convergence of a trim solution in the aeroelastic analysis of helicopters are proposed. It is found that the basins of attraction can have fractal boundaries. (C) 2010 Elsevier Ltd. All rights reserved.

Inverse problem for the wave equation : partial data and novel boundary sources

An inverse problem for the wave equation is a mathematical formulation of the problem to convert measurements of sound waves to information about the wave speed governing the propagation of the waves. This doctoral thesis extends the theory on the inverse problems for the wave equation in cases with partial measurement data and also considers detection of discontinuous interfaces in the wave speed. A possible application of the theory is obstetric sonography in which ultrasound measurements are transformed into an image of the fetus in its mother's uterus. The wave speed inside the body can not be directly observed but sound waves can be produced outside the body and their echoes from the body can be recorded. The present work contains five research articles. In the first and the fifth articles we show that it is possible to determine the wave speed uniquely by using far apart sound sources and receivers. This extends a previously known result which requires the sound waves to be produced and recorded in the same place. Our result is motivated by a possible application to reflection seismology which seeks to create an image of the Earth s crust from recording of echoes stimulated for example by explosions. For this purpose, the receivers can not typically lie near the powerful sound sources. In the second article we present a sound source that allows us to recover many essential features of the wave speed from the echo produced by the source. Moreover, these features are known to determine the wave speed under certain geometric assumptions. Previously known results permitted the same features to be recovered only by sequential measurement of echoes produced by multiple different sources. The reduced number of measurements could increase the number possible applications of acoustic probing. In the third and fourth articles we develop an acoustic probing method to locate discontinuous interfaces in the wave speed. These interfaces typically correspond to interfaces between different materials and their locations are of interest in many applications. There are many previous approaches to this problem but none of them exploits sound sources varying freely in time. Our use of more variable sources could allow more robust implementation of the probing.

An efficient marching algorithm for waterhammer analysis by the method of characteristics

A new fast and efficient marching algorithm is introduced to solve the basic quasilinear, hyperbolic partial differential equations describing unsteady, flow in conduits by the method of characteristics. The details of the marching method are presented with an illustration of the waterhammer problem in a simple piping system both for friction and frictionless cases. It is shown that for the same accuracy the new marching method requires fewer computational steps, less computer memory and time.