No description available.

In the context of gene expression, we proposed a nonlinear stochastic delay differential equation as a mathematical model to study the effects of extrinsic noise on a delay induced Hopf bifurcation. We envisaged its direct numerical resolution. Following the example of the noisy oscillator, we first solved a linearized version of the equation, close to the Hopf bifurcation. The numerical scheme used is a combination of a standard algorithm to solve a deterministic delay differential equation and a stochastic Euler scheme. From our calculations we verified that the deterministic behaviour is fully recovered. For the stochastic case, we found that our solution is qualitatively accurate, in the sense that the noise induced shift in the critical value a, follows the trend the known analytic results predict. However, our numerical solution systematically overestimates the value of the shift. This is explained because the accuracy in the numerical estimation of the decay rate of a solution towards the stationary state value is a function of the control parameter a. We believe the mismatch between the numerical solution and the analytic results is due to a lack of convergence of our scheme, rather than to lack of accuracy. As our numerical scheme is an hybrid, the convergence problem can be improved, both at the deterministic and at the stochastic parts of the scheme. In this work we left our numerical results on the nonlinear case out, because before proceeding to the investigation of the nonlinear equation, the convergence must be assured in the linear case.

published_or_final_version / Mathematics / Master / Master of Philosophy

In this thesis we present a new model for identifying dependencies within a gene regulatory cycle. The model incorporates both probabilistic and temporal aspects, but is kept deliberately simple to make it amenable for learning from the gene expression data of microarray experiments. A key simplifying feature in our model is the use of a compression function for collapsing multiple causes of gene expression into a single cause. This allows us to introduce a learning algorithm which avoids the over-fitting tendencies of models with many parameters. We have validated the learning algorithm on simulated data, and carried out experiments on real microarray data. In doing so, we have discovered novel, yet plausible, biological relationships.

Modeling gene regulation is an important problem in genomic research. The Boolean network (BN) and its generalization Probabilistic Boolean network (PBN) have been proposed to model genetic regulatory interactions. BN is a deterministic model while PBN is a stochastic model. In a PBN, on one hand, its stationary distribution gives important information about the long-run behavior of the network. On the other hand, one may be interested in system synthesis which requires the construction of networks from the observed stationary distribution. This results in an inverse problem of constructing PBNs from a given stationary distribution and a given set of Boolean Networks (BNs), which is ill-posed and challenging, because there may be many networks or no network having the given properties and the size of the inverse problem is huge. The inverse problem is first formulated as a constrained least squares problem. A heuristic method is then proposed based on the conjugate gradient (CG) algorithm, an iterative method, to solve the resulting least squares problem. An estimation method for the parameters of the PBNs is also discussed. Numerical examples are then given to demonstrate the effectiveness of the proposed methods. However, the PBNs generated by the above algorithm depends on the initial guess and is not unique. A heuristic method is then proposed for generating PBNs from a given transition probability matrix. Unique solution can be obtained in this case. Moreover, these algorithms are able to recover the dominated BNs and therefore the major structure of the network. To further evaluate the feasible solutions, a maximum entropy approach is proposed using entropy as a measure of the fitness. Newton’s method in conjunction with the CG method is then applied to solving the inverse problem. The convergence rate of the proposed method is demonstrated. Numerical examples are also given to demonstrate the effectiveness of our proposed method. Another important problem is to find the optimal control policy for a PBN so as to avoid the network from entering into undesirable states. By applying external control, the network is desired to enter into some state within a few time steps. For PBN CONTROL, people propose to find a control sequence such that the network will terminate in the desired state with a maximum probability. Also, the problem of minimizing the maximum cost is considered. Integer linear programming (ILP) and dynamic programming (DP) in conjunction with hard constraints are then employed to solve the above problems. Numerical experiments are given to demonstrate the effectiveness of our algorithms. A hardness result is demonstrated and suggests that PBN CONTROL is harder than BN CONTROL. In addition, deciding the steady state probability in PBN for a specified global state is demonstrated to be NP-hard. However, due to the high computational complexity of PBNs, DP method is computationally inefficient for a large size network. Inspired by the state reduction strategies studied in [86], the DP method in conjunction with state reduction approach is then proposed to reduce the computational cost of the DP method. Numerical examples are given to demonstrate both the effectiveness and the efficiency of our proposed method. / published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

Quantitative analysis of Drosophila melanogaster gap gene expression data reveals valuable information about the nature and strengths of interactions in the gap gene network. We first explore different models for fitting the spatiotemporal gene expression data of Drosophila gap gene system and validate our results by computational analysis and comparison with the existing literature. A fundamental problem in systems biology is to associate these results with the inherent cause of gene regulation, namely the binding of the transcription factors (TF) to their respective binding sites. In order to relate these expression-based estimates of gap gene regulation with the sequence-based information of TF binding site composition, we also explore two related problems of (i) finding a set of regulatory weights that is proportional to the binding site occupancy matrix of the transcription factors in current literature and (ii) finding a set of position weight matrices of the TFs that produce a new binding site occupancy matrix showing a greater level of proportionality with our regulatory weights. Our solution to the first problem yielded a regulatory weight matrix incapable of explaining the true causes of gene expression profile despite its relative numerical accuracy in predicting the gene expressions. On the other hand, the second optimization problem could be solved up to a reasonable level of accuracy, but further analysis on the result demonstrated that this optimization problem may be under-constrained. We devise a simple regularization strategy that helps us to reduce the under-constrained nature of the problem.

No description available.

On TFBS motif discovery, three novel GA based algorithms are developed, namely GALF-P with focus on optimization, GALF-G for modeling, and GASMEN for spaced motifs. Novel memetic operators are introduced, namely local filtering and probabilistic refinement, to significantly improve effectiveness (e.g. 73% better than MEME) and efficiency (e.g. 4.49 times speedup) in search. The GA based algorithms have been extensively tested on comprehensive synthetic, real and benchmark datasets, and shown outstanding performances compared with state-of-the-art approaches. Our algorithms also "evolve" to handle more and more relaxed cases, namely from fixed motif widths to most flexible widths, from single motifs to multiple motifs with overlapping control, from stringent motif instance assumption to very relaxed ones, and from contiguous motifs to generic spaced motifs with arbitrary spacers. / TF-TFBS associated sequence pattern (rule) discovery is further investigated for better deciphering protein-DNA interactions in regulation. We for the first time generalize previous exact TF-TFBS rules to approximate ones using a progressive approach. A customized algorithm is developed, outperforming MEME by over 73%. The approximate TF-TFBS rules, compared with the exact ones, have significantly more verified rules and better verification ratios. Detailed analysis on PDB cases and conservation verification on NCBI protein records illustrate that the approximate rules reveal the flexible and specific protein-DNA interactions with much greater generalized capability. / The comprehensive pattern discovery algorithms developed will be further verified, improved and extended to further deciphering transcriptionial regulation, such as inferring whole gene regulatory networks by applying TFBS and TF-TFBS patterns discovered and incorporating expression data. / Transcription Factor (TF) and Transcription Factor Binding Site (TFBS) bindings are fundamental protein-DNA interactions in transcriptional regulation. TFs and TFBSs are conserved to form patterns (motifs) due to their important roles for controlling gene expressions and finally affecting functions and appearances. Pattern discovery is thus important for deciphering gene regulation, which has tremendous impacts on the understanding of life, bio-engineering and therapeutic applications. This thesis contributes to pattern discovery involving TFBS motifs and TF-TFBS associated sequence patterns based on Evolutionary Computation (EC), especially Genetic Algorithms (GAs), which are promising for bioinformatics problems with huge and noisy search space. / Chan, Tak Ming. / Advisers: Kwong-Sak Leung; Kin-Hong Lee. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 147-153). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Cette thèse de doctorat s’inscrit dans le développement et l’utilisation de méthodes mathématiques et informatiques qui exploitent les données temporelles d’expression des gènes issues de puces à ADN afin de rationaliser et de modéliser les réseaux de régulation génique. Dans cette optique, nous nous sommes principalement intéressés aux données d’expression des gènes de la drosophile (Drosophila melanogaster) pendant son développement, du stade embryonnaire au stade adulte. Nous avons également étudié des données concernant le développement d’autres eucaryotes supérieurs, la réponse d’une bactérie soumises à différents stress et le cycle cellulaire d’une levure. Ce travail a été réalisé selon trois volets principaux :la détection des stades de développement et des perturbations, les classifications de profils d’expression et la modélisation de réseaux de régulation.<p><p>Premièrement, l’observation des données d’expression utilisées nous a conduits à approfondir l’étude des phénomènes survenant lors des changements de stades de développement de la drosophile. Dans ce but, deux méthodes de détection automatique de ces changements ont été développées et appliquées aux données temporelles disponibles sur le développement d’eucaryotes supérieurs. Elles ont également été appliquées à des données temporelles relatives à des perturbations externes de bactéries. Cette étude à montré qu’une formulation mathématique simple permettait de retrouver les instants expérimentaux où une perturbation ou un changement de stade de développement est observé, à partir uniquement des profils d’expression. Par ailleurs, la réponse à une perturbation externe s’avère non distinguable d’une succession de stades de développement, sur la base des seuls profils temporels d’expression.<p><p>Deuxièmement, en raison des dimensions du problème constitué par les données d’expression de plusieurs milliers de gènes et de l’impossibilité de distinguer le rôle dans la régulation des gènes qui présentent des profils d’expression similaires, il s’est avéré nécessaire de classifier les gènes selon leurs profils d’expression. En nous basant sur les résultats obtenus lors de la détection des stades de développement, la démarche suivie est de regrouper les gènes qui présentent des profils temporels d’expression aux comportements similaires non seulement au cours de la série temporelle complète, mais également dans chacun des stades de développement. Dans cette optique, trois distances ont été proposées et utilisées dans une classification hiérarchique des données d’expression de la drosophile.<p><p>Troisièmement, des structures de modèles linéaires et non linéaires ainsi que des méthodes d’estimation et de réduction paramétriques ont été développées et utilisées pour reproduire les données d’expression du développement de la drosophile. Les résultats de ce travail ont montré qu’avec une structure de modèle linéaire simple, la reproduction des profils expérimentaux était excellente et que, dans ce cas, le réseau de régulation génique de la drosophile pouvait se contenter d’une faible connectivité (en moyenne 3 connexions par classe de gènes) et ce, sans hypothèse a priori. Toutefois, les modèles linéaires ont ensuite sérieusement été remis en question par des analyses de robustesse aux perturbations paramétriques et de stabilité des profils après extrapolation dans le temps. Dès lors, quatre structures de modèles non linéaires et cinq méthodes de réduction paramétrique ont été proposées et utilisées pour concilier les critères de reproduction des données, de robustesse et de stabilité des réseaux identifiés. En outre, ces méthodes de modélisation ont été appliquées à un sous-ensemble de 20 gènes impliqués dans le développement musculaire de la drosophile et pour lesquels 36 interactions ont été validées expérimentalement, ainsi qu’à des profils synthétiques bruités. Nous avons pu constater que plus de la moitié des connexions et non-connexions sont retrouvées par trois modèles non linéaires. Les résultats de cette étude ont permis d’éliminer certaines structures de modèle et méthodes de réduction et ont mis en lumière plusieurs directions futures à suivre dans la démarche de modélisation des réseaux de régulation génique. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished