Back to search

University of British Columbia

Study of two biochemical models : chemical reaction networks, and nucleic acid systems

Abstract

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

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Bioinformatics
Grantor dc:publisher
University of British Columbia
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hajiaghayi, Monir

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/63311

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hajiaghayi, Monir. Study of two biochemical models : chemical reaction networks, and nucleic acid systems. doctoral thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/63311