5 Search Results for "Allen, Chris"


Document
Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer

Authors: Ahmed Shalaby, Chris Thachuk, and Damien Woods

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)


Abstract
Polynomial time dynamic programming algorithms play a crucial role in the design, analysis and engineering of nucleic acid systems including DNA computers and DNA/RNA nanostructures. However, in complex multistranded or pseudoknotted systems, computing the minimum free energy (MFE), and partition function of nucleic acid systems is NP-hard. Despite this, multistranded and/or pseudoknotted systems represent some of the most utilised and successful systems in the field. This leaves open the tempting possibility that many of the kinds of multistranded and/or pseudoknotted systems we wish to engineer actually fall into restricted classes, that do in fact have polynomial time algorithms, but we've just not found them yet. Here, we give polynomial time algorithms for MFE and partition function calculation for a restricted kind of multistranded system called the 1D scaffolded DNA computer. This model of computation thermodynamically favours correct outputs over erroneous states, simulates finite state machines in 1D and Boolean circuits in 2D, and is amenable to DNA storage applications. In an effort to begin to ask the question of whether we can naturally compare the expressivity of nucleic acid systems based on the computational complexity of prediction of their preferred energetic states, we show our MFE problem is in logspace (the complexity class L), making it perhaps one of the simplest known, natural, nucleic acid MFE problems. Finally, we provide a stochastic kinetic simulator for the 1D scaffolded DNA computer and evaluate strategies for efficiently speeding up this thermodynamically favourable system in a constant-temperature kinetic regime.

Cite as

Ahmed Shalaby, Chris Thachuk, and Damien Woods. Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{shalaby_et_al:LIPIcs.DNA.29.1,
  author =	{Shalaby, Ahmed and Thachuk, Chris and Woods, Damien},
  title =	{{Minimum Free Energy, Partition Function and Kinetics Simulation Algorithms for a Multistranded Scaffolded DNA Computer}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.1},
  URN =		{urn:nbn:de:0030-drops-187840},
  doi =		{10.4230/LIPIcs.DNA.29.1},
  annote =	{Keywords: thermodynamic computation, model of computation, molecular computing, minimum free energy, partition function, DNA computing, DNA self-assembly, DNA strand displacement, kinetics simulation}
}
Document
Fast and Robust Strand Displacement Cascades via Systematic Design Strategies

Authors: Tiernan Kennedy, Cadence Pearce, and Chris Thachuk

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)


Abstract
A barrier to wider adoption of molecular computation is the difficulty of implementing arbitrary chemical reaction networks (CRNs) that are robust and replicate the kinetics of designed behavior. DNA Strand Displacement (DSD) cascades have been a favored technology for this purpose due to their potential to emulate arbitrary CRNs and known principles to tune their reaction rates. Progress on leakless cascades has demonstrated that DSDs can be arbitrarily robust to spurious "leak" reactions when incorporating systematic domain level redundancy. These improvements in robustness result in slower kinetics of designed reactions. Existing work has demonstrated the kinetic and thermodynamic effects of sequence mismatch introduction and elimination during displacement. We present a systematic, sequence modification strategy for optimizing the kinetics of leakless cascades without practical cost to their robustness. An in-depth case study explores the effects of this optimization when applied to a typical leakless translator cascade. Thermodynamic analysis of energy barriers and kinetic experimental data support that DSD cascades can be fast and robust.

Cite as

Tiernan Kennedy, Cadence Pearce, and Chris Thachuk. Fast and Robust Strand Displacement Cascades via Systematic Design Strategies. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kennedy_et_al:LIPIcs.DNA.28.1,
  author =	{Kennedy, Tiernan and Pearce, Cadence and Thachuk, Chris},
  title =	{{Fast and Robust Strand Displacement Cascades via Systematic Design Strategies}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.1},
  URN =		{urn:nbn:de:0030-drops-167869},
  doi =		{10.4230/LIPIcs.DNA.28.1},
  annote =	{Keywords: DNA strand displacement, Energy barriers, Kinetics}
}
Document
Short Paper
Assessing Neighborhood Conditions using Geographic Object-Based Image Analysis and Spatial Analysis (Short Paper)

Authors: Chi-Feng Yen, Ming-Hsiang Tsou, and Chris Allen

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)


Abstract
Traditionally, understanding urban neighborhood conditions heavily relies on time-consuming and labor-intensive surveying. As the growing development of computer vision and GIScience technology, neighborhood conditions assessment can be more cost-effective and time-efficient. This study utilized Google Earth Engine (GEE) to acquire 1m aerial imagery from the National Agriculture Image Program (NAIP). The features within two main categories: (i) aesthetics and (ii) street morphology that have been selected to reflect neighborhood socio-economic (SE) and demographic (DG) conditions were subsequently extracted through geographic object-based image analysis (GEOBIA) routine. Finally, coefficient analysis was performed to validate the relationship between selected SE indicators, generated via spatial analysis, as well as actual SE and DG data within region of interests (ROIs). We hope this pilot study can be leveraged to perform cost- and time- effective neighborhood conditions assessment in support of community data assessment on both demographics and health issues.

Cite as

Chi-Feng Yen, Ming-Hsiang Tsou, and Chris Allen. Assessing Neighborhood Conditions using Geographic Object-Based Image Analysis and Spatial Analysis (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 70:1-70:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{yen_et_al:LIPIcs.GISCIENCE.2018.70,
  author =	{Yen, Chi-Feng and Tsou, Ming-Hsiang and Allen, Chris},
  title =	{{Assessing Neighborhood Conditions using Geographic Object-Based Image Analysis and Spatial Analysis}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{70:1--70:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.70},
  URN =		{urn:nbn:de:0030-drops-93983},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.70},
  annote =	{Keywords: neighborhood conditions assessment, geographic object-based image analysis, spatial analysis}
}
Document
The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property

Authors: Chris Dowden, Mihyun Kang, and Michael Krivelevich

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which `region' m falls into. Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases. In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n. We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.

Cite as

Chris Dowden, Mihyun Kang, and Michael Krivelevich. The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{dowden_et_al:LIPIcs.AofA.2018.17,
  author =	{Dowden, Chris and Kang, Mihyun and Krivelevich, Michael},
  title =	{{The Genus of the Erd\"{o}s-R\'{e}nyi Random Graph and the Fragile Genus Property}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17},
  URN =		{urn:nbn:de:0030-drops-89100},
  doi =		{10.4230/LIPIcs.AofA.2018.17},
  annote =	{Keywords: Random graphs, Genus, Fragile genus}
}
Document
Lower Bounds for CSP Refutation by SDP Hierarchies

Authors: Ryuhei Mori and David Witmer

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)


Abstract
For a k-ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m >= O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP(P) using an SDP is determined by a parameter cmplx(P), the smallest t for which there does not exist a t-wise uniform distribution over satisfying assignments to P. In particular they show that random instances of CSP(P) with m >> n^{cmplx(P)/2} can be refuted efficiently using an SDP. In this work, we give evidence that n^{cmplx(P)/2} constraints are also necessary for refutation using SDPs. Specifically, we show that if P supports a (t-1)-wise uniform distribution over satisfying assignments, then the Sherali-Adams_+ and Lovasz-Schrijver_+ SDP hierarchies cannot refute a random instance of CSP(P) in polynomial time for any m <= n^{t/2-epsilon}.

Cite as

Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 41:1-41:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{mori_et_al:LIPIcs.APPROX-RANDOM.2016.41,
  author =	{Mori, Ryuhei and Witmer, David},
  title =	{{Lower Bounds for CSP Refutation by SDP Hierarchies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{41:1--41:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  URN =		{urn:nbn:de:0030-drops-66645},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  annote =	{Keywords: constraint satisfaction problems, LP and SDP relaxations, average-case complexity}
}
  • Refine by Author
  • 2 Thachuk, Chris
  • 1 Allen, Chris
  • 1 Dowden, Chris
  • 1 Kang, Mihyun
  • 1 Kennedy, Tiernan
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Chemistry
  • 1 Applied computing → Physical sciences and engineering
  • 1 Computer systems organization → Molecular computing
  • 1 Computing methodologies → Computer vision
  • 1 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 2 DNA strand displacement
  • 1 DNA computing
  • 1 DNA self-assembly
  • 1 Energy barriers
  • 1 Fragile genus
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2018
  • 1 2016
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail