- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Study of two biochemical models : chemical reaction...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Study of two biochemical models : chemical reaction networks, and nucleic acid systems Hajiaghayi, Monir
Abstract
The contributions of this thesis are motivated by an exciting challenge at the intersection of computer science and biochemistry: Can we program molecules to do interesting or useful computations? There has been significant progress in programming nucleic acids - particularly DNA molecules - thanks in part to availability of models and algorithms for predicting nucleic acid structure and folding kinetics. At a higher level of abstraction, Chemical Reaction Networks (CRNs) have proven to be valuable as a molecular programming model that enables researchers to understand the potential and limitations of computing with molecules, unencumbered by low-level details. These two levels of abstraction are linked; it is possible to "compile" CRN programs into nucleic acid systems that make the programs implementable in a test tube. We design and analyze CRN algorithms for two purposes. First, we show how any semilinear function can be computed by CRNs, even when no "leader" species (i.e., initial species with constant but non-zero counts) is present. Our results improve earlier results of Chen et al. (2012) who showed that only semilinear functions are computable by error-free CRNs using leaders. Our new CRN construction can be done in expected time O(n), which is faster than O(n log n) bound achieved by Chen et al. Second, we provide the most intuitive proofs of correctness and efficiency for three different CRNs computing Approximate Majority: Given a mixture of two types of species with an initial gap between their counts, a CRN computation must reach totality on the majority species with high probability. The CRNs of our interest have the ability to start with an initial gap of Ω(√n log n). In the second part of this thesis, we study the problem of predicting the Minimum Free Energy secondary structure (the set of base pairs) of a given set of nucleic acid strands with no pseudoknots (crossing base pairs). We show that this problem is APX-hard which implies that there does not exist a polynomial time approximation scheme for this problem, unless P = NP. We also propose a new Monte-Carlo based method to efficiently estimate nucleic acid folding kinetics.
Item Metadata
Title |
Study of two biochemical models : chemical reaction networks, and nucleic acid systems
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2017
|
Description |
The contributions of this thesis are motivated by an exciting challenge at
the intersection of computer science and biochemistry: Can we program
molecules to do interesting or useful computations? There has been significant progress in programming nucleic acids - particularly DNA molecules -
thanks in part to availability of models and algorithms for predicting nucleic
acid structure and folding kinetics. At a higher level of abstraction, Chemical
Reaction Networks (CRNs) have proven to be valuable as a molecular programming
model that enables researchers to understand the potential and
limitations of computing with molecules, unencumbered by low-level details.
These two levels of abstraction are linked; it is possible to "compile" CRN
programs into nucleic acid systems that make the programs implementable
in a test tube.
We design and analyze CRN algorithms for two purposes. First, we
show how any semilinear function can be computed by CRNs, even when
no "leader" species (i.e., initial species with constant but non-zero counts)
is present. Our results improve earlier results of Chen et al. (2012) who
showed that only semilinear functions are computable by error-free CRNs
using leaders. Our new CRN construction can be done in expected time
O(n), which is faster than O(n log n) bound achieved by Chen et al. Second,
we provide the most intuitive proofs of correctness and efficiency for three
different CRNs computing Approximate Majority: Given a mixture of two
types of species with an initial gap between their counts, a CRN computation
must reach totality on the majority species with high probability. The CRNs
of our interest have the ability to start with an initial gap of Ω(√n log n).
In the second part of this thesis, we study the problem of predicting the
Minimum Free Energy secondary structure (the set of base pairs) of a given
set of nucleic acid strands with no pseudoknots (crossing base pairs). We
show that this problem is APX-hard which implies that there does not exist
a polynomial time approximation scheme for this problem, unless P = NP.
We also propose a new Monte-Carlo based method to efficiently estimate
nucleic acid folding kinetics.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2017-10-16
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0357130
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2017-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International