1 |
Finding conserved patterns in biological sequences, networks and genomesYang, Qingwu 15 May 2009 (has links)
Biological patterns are widely used for identifying biologically interesting regions
within macromolecules, classifying biological objects, predicting functions and studying
evolution. Good pattern finding algorithms will help biologists to formulate and
validate hypotheses in an attempt to obtain important insights into the complex
mechanisms of living things.
In this dissertation, we aim to improve and develop algorithms for five biological
pattern finding problems. For the multiple sequence alignment problem, we propose
an alternative formulation in which a final alignment is obtained by preserving pairwise
alignments specified by edges of a given tree. In contrast with traditional NPhard
formulations, our preserving alignment formulation can be solved in polynomial
time without using a heuristic, while having very good accuracy.
For the path matching problem, we take advantage of the linearity of the query
path to reduce the problem to finding a longest weighted path in a directed acyclic
graph. We can find k paths with top scores in a network from the query path in
polynomial time. As many biological pathways are not linear, our graph matching
approach allows a non-linear graph query to be given. Our graph matching formulation
overcomes the common weakness of previous approaches that there is no
guarantee on the quality of the results.
For the gene cluster finding problem, we investigate a formulation based on constraining the overall size of a cluster and develop statistical significance estimates that
allow direct comparisons of clusters of different sizes. We explore both a restricted
version which requires that orthologous genes are strictly ordered within each cluster,
and the unrestricted problem that allows paralogous genes within a genome and clusters
that may not appear in every genome. We solve the first problem in polynomial
time and develop practical exact algorithms for the second one.
In the gene cluster querying problem, based on a querying strategy, we propose
an efficient approach for investigating clustering of related genes across multiple
genomes for a given gene cluster. By analyzing gene clustering in 400 bacterial
genomes, we show that our algorithm is efficient enough to study gene clusters across
hundreds of genomes.
|
2 |
Computational Stochastic MorphogenesisSaygun, Yakup January 2015 (has links)
Self-organizing patterns arise in a variety of ways in nature, the complex patterning observed on animal coats is such an example. It is already known that the mechanisms responsible for pattern formation starts at the developmental stage of an embryo. However, the actual process determining cell fate has been, and still is, unknown. The mathematical interest for pattern formation emerged from the theories formulated by the mathematician and computer scientist Alan Turing in 1952. He attempted to explain the mechanisms behind morphogenesis and how the process of spatial cell differentiation from homogeneous cells lead to organisms with different complexities and shapes. Turing formulated a mathematical theory and proposed a reaction-diffusion system where morphogens, a postulated chemically active substance, moderated the whole mechanism. He concluded that this process was stable as long as diffusion was neglected; otherwise this would lead to a diffusion-driven instability, which is the fundamental part of pattern formation. The mathematical theory describing this process consists of solving partial differential equations and Turing considered deterministic reaction-diffusion systems. This thesis will start with introducing the reader to the problem and then gradually build up the mathematical theory needed to get an understanding of the stochastic reaction-diffusion systems that is the focus of the thesis. This study will to a large extent simulate stochastic systems using numerical computations and in order to be computationally feasible a compartment-based model will be used. Noise is an inherent part of such systems, so the study will also discuss the effects of noise and morphogen kinetics on different geometries with boundaries of different complexities from one-dimensional cases up to three-dimensions.
|
Page generated in 0.0606 seconds