| Liu L, Jacobson B and Stefanovic D (2026), "PID-controller enhanced artificial β-cells", PLOS One., March, 2026. Vol. 21(3), pp. e0342799. Public Library of Science (PLoS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Conventional management of diabetes via injection or external insulin pumps suffers from inconvenience and inability to accurately maintain blood glucose levels. A potential solution to these problems consists of implanting synthetic artificial β-cells that can sense glucose and transcribe insulin protein. Experimental results from Xie et al. show these cells are able to release insulin and somewhat improve postprandial glucose levels in diabetic mice. However, they fail to achieve the degree of glucose regulation as in healthy mice. In our analysis, we explain that this artificial β-cell system has a major disadvantage: it is a high-dimensional dynamic system but with little tuning space. Here, we propose an analytical model of a PID-controller-based enhanced artificial β-cell design to solve this issue. Our numerical simulations show that a model of PID-controlled engineered artificial β-cells can shut down production of insulin in time and maintain a proper glycemia level, in addition to adding more tuning space. These enhanced models of PID-controller-based artificial β-cell are thus able to perform better in regulating glucose levels in Type 1 diabetic mice compared with artificial β-cells without PID-control. |
BibTeX:
@article{Liu2026,
author = {Liu, Lin and Jacobson, Bruna and Stefanovic, Darko},
editor = {Chatenoud, Lucienne},
title = {PID-controller enhanced artificial β-cells},
journal = {PLOS One},
publisher = {Public Library of Science (PLoS)},
year = {2026},
volume = {21},
number = {3},
pages = {e0342799},
doi = {10.1371/journal.pone.0342799}
}
|
| Harding BI, Pollak NM, Stefanovic D and Macdonald J (2022), "Complexing deoxyribozymes with RNA aptamers for detection of the small molecule theophylline", Biosensors and Bioelectronics., February, 2022. Vol. 198, pp. 113774. Elsevier BV.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Biointegrative information processing systems offer a great advantage to autonomous biodevices, as their capacity for biological computation provides the ability to sense the state of more complex environments and better integrate with downstream biological regulation systems. Deoxyribozymes (DNAzymes) and aptamers are of interest to such computational biosensing systems due to the enzymatic properties of DNAzymes and the ligand-inducible conformational structures of aptamers. Herein, we describe a novel method for providing ligand-responsive allosteric control to a DNAzyme using an RNA aptamer. We designed a NOT-logic-compliant E6 DNAzyme to be complementary to an RNA aptamer targeting theophylline, such that the aptamer competitively interacted with either theophylline or the DNAzyme, and disabled the DNAzyme only when theophylline concentration was below a given threshold. Out of our seven designed “complexing aptazymes,” three demonstrated effective theophylline-responsive allosteric regulation (2.84 ± 3.75%, 4.97 ± 2.92%, and 8.91 ± 4.19% activity in the absence of theophylline; 46.29 ± 3.36%, 50.70 ± 10.15%, and 61.26 ± 6.18% activity in the presence of theophylline). Moreover, the same three complexing aptazymes also demonstrated the ability to semi-quantitatively determine the concentration of theophylline present in solution, successfully discriminating between therapeutically ineffective (<20 μM), safe (20–100 μM), and toxic (>100 μM) theophylline concentrations. Our method of using an RNA aptamer for ligand-responsive allosteric control of a DNAzyme expands the way aptamers can be configured for biosensing, and suggests a pathway for embedding DNAzymes to provide enhanced information processing and control of biological systems." |
BibTeX:
@article{Harding2022,
author = {Harding, Bradley I. and Pollak, Nina M. and Stefanovic, Darko and Macdonald, Joanne},
title = {Complexing deoxyribozymes with RNA aptamers for detection of the small molecule theophylline},
journal = {Biosensors and Bioelectronics},
publisher = {Elsevier BV},
year = {2022},
volume = {198},
pages = {113774},
doi = {10.1016/j.bios.2021.113774}
}
|
| Staufer O, De Lora JA, Bailoni E, Bazrafshan A, Benk AS, Jahnke K, Manzer ZA, Otrin L, Díez Pérez T, Sharon J, Steinkühler J, Adamala KP, Jacobson B, Dogterom M, Göpfrich K, Stefanovic D, Atlas SR, Grunze M, Lakin MR, Shreve AP, Spatz JP and López GP (2021), "Building a community to engineer synthetic cells and organelles from the bottom-up", eLife., December, 2021. Vol. 10 eLife Sciences Publications, Ltd.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Employing concepts from physics, chemistry and bioengineering, 'learning-by-building'approaches are becoming increasingly popular in the life sciences, especially with researchers who are attempting to engineer cellular life from scratch. The SynCell2020/21 conference brought together researchers from different disciplines to highlight progress in this field, including areas where synthetic cells are having socioeconomic and technological impact. Conference participants also identified the challenges involved in designing, manipulating and creating synthetic cells with hierarchical organization and function. A key conclusion is the need to build an international and interdisciplinary research community through enhanced communication, resource-sharing, and educational initiatives. |
BibTeX:
@article{Staufer2021,
author = {Staufer, Oskar and De Lora, Jacqueline A and Bailoni, Eleonora and Bazrafshan, Alisina and Benk, Amelie S and Jahnke, Kevin and Manzer, Zachary A and Otrin, Lado and Díez Pérez, Telmo and Sharon, Judee and Steinkühler, Jan and Adamala, Katarzyna P and Jacobson, Bruna and Dogterom, Marileen and Göpfrich, Kerstin and Stefanovic, Darko and Atlas, Susan R and Grunze, Michael and Lakin, Matthew R and Shreve, Andrew P and Spatz, Joachim P and López, Gabriel P},
title = {Building a community to engineer synthetic cells and organelles from the bottom-up},
journal = {eLife},
publisher = {eLife Sciences Publications, Ltd},
year = {2021},
volume = {10},
doi = {10.7554/elife.73556}
}
|
| Lakin MR, Stefanovic D and Stojanovic MN (2021), "Diverse Applications of DNAzymes in Computing and Nanotechnology". August, 2021.
[BibTeX] [DOI]
|
BibTeX:
@misc{Lakin2021,
author = {Lakin, Matthew R. and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Diverse Applications of DNAzymes in Computing and Nanotechnology},
journal = {Ribozymes},
publisher = {Wiley},
year = {2021},
pages = {633--660},
doi = {10.1002/9783527814527.ch25}
}
|
| Arredondo D, Lakin MR, Stefanovic D and Stojanovic MN (2021), "Development and Application of Catalytic DNA in Nanoscale Robotics". January, 2021.
[BibTeX] [DOI]
|
BibTeX:
@misc{Arredondo2021,
author = {Arredondo, David and Lakin, Matthew R. and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Development and Application of Catalytic DNA in Nanoscale Robotics},
journal = {DNA‐ and RNA‐Based Computing Systems},
publisher = {Wiley},
year = {2021},
pages = {293--306},
doi = {10.1002/9783527825424.ch15}
}
|
| Arredondo D and Stefanovic D (2020), "Effect of polyvalency on tethered molecular walkers on independent one-dimensional tracks", Physical Review E., June, 2020. Vol. 101(6), pp. 062101. American Physical Society (APS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We study the motion of random walkers with residence time bias between first and subsequent visits to a site, as a model for synthetic molecular walkers composed of coupled DNAzyme legs known as molecular spiders.The mechanism of the transient superdiffusion has been explained via the emergence of a boundary between the new and the previously visited sites, and the tendency of the multilegged walker to cling to this boundary, provided residence time for a first visit to a site is longer than for subsequent visits. Using both kinetic Monte Carlo simulation and an analytical approach, we model a system that consists of unipedal walkers, each on its own one-dimensional track, connected by a tether, i.e., a kinematic constraint that no two walkers can be more than a certain distance apart. Even though a single unipedal walker does not at all exhibit directional, superdiffusive motion, we find that a team of unipedal walkers on parallel tracks, connected by a flexible tether, does enjoy a superdiffusive transient. Furthermore, unipedal walker teams exhibit a greater expected number of steps per boundary period and are able to diffuse more quickly than bipedal walker teams, which leads to longer periods of superdiffusion. |
BibTeX:
@article{Arredondo2020,
author = {Arredondo, David and Stefanovic, Darko},
title = {Effect of polyvalency on tethered molecular walkers on independent one-dimensional tracks},
journal = {Physical Review E},
publisher = {American Physical Society (APS)},
year = {2020},
volume = {101},
number = {6},
pages = {062101},
doi = {10.1103/physreve.101.062101}
}
|
| Mallette TL, Stojanovic MN, Stefanovic D and Lakin MR (2020), "Robust Heterochiral Strand Displacement Using Leakless Translators", ACS Synthetic Biology., June, 2020. Vol. 9(7), pp. 1907-1910. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular computing offers a powerful framework for in situ biosensing and signal processing at the nanoscale. However, for in vivo applications, the use of conventional DNA components can lead to false positive signals being generated due to degradation of circuit components by nuclease enzymes. Here, we use hybrid chiral molecules, consisting of both L- and D-nucleic acid domains, to implement leakless signal translators that enable D-nucleic acid signals to be detected by hybridization and then translated into a robust L-DNA signal for further analysis. We show that our system is robust to false positive signals even if the D-DNA components are degraded by nucleases, thanks to circuit-level robustness. This work thus broadens the scope and applicability of DNA-based molecular computers for practical, in vivo applications. |
BibTeX:
@article{Mallette2020,
author = {Mallette, Tracy L. and Stojanovic, Milan N. and Stefanovic, Darko and Lakin, Matthew R.},
title = {Robust Heterochiral Strand Displacement Using Leakless Translators},
journal = {ACS Synthetic Biology},
publisher = {American Chemical Society (ACS)},
year = {2020},
volume = {9},
number = {7},
pages = {1907--1910},
doi = {10.1021/acssynbio.0c00131}
}
|
| Nguyen H, Banda P, Stefanovic D and Teuscher C (2020), "Reservoir Computing with Random Chemical Systems", In The 2020 Conference on Artificial Life. MIT Press.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Top-down engineering of biomolecular circuits to perform specific computational tasks is notoriously hard and time-consuming. Current circuits have limited complexity and are brittle and application-specific. Here we propose an alternative: we design and test a bottom-up constructed Reservoir Computer (RC) that uses random chemical circuits inspired by DNA strand displacement reactions. This RC has the potential to be implemented easily and trained for various tasks. We describe and simulate it by means of a Chemical Reaction Network (CRN) and evaluate its performance on three computational tasks: the Hamming distance and a short- as well as a long-term memory. Compared with the deoxyribozyme oscillator RC model simulated by Yahiro et al., our random chemical RC performs 75.5% better for the short-term and 67.2% better for the long-term memory task. Our model requires an 88.5% larger variety of chemical species, but it relies on random chemical circuits, which can be more easily realized and scaled up. Thus, our novel random chemical RC has the potential to simplify the way we build adaptive biomolecular circuits. |
BibTeX:
@inproceedings{Nguyen2020,
author = {Nguyen, Hoang and Banda, Peter and Stefanovic, Darko and Teuscher, Christof},
title = {Reservoir Computing with Random Chemical Systems},
booktitle = {The 2020 Conference on Artificial Life},
publisher = {MIT Press},
year = {2020},
doi = {10.1162/isal_a_00324}
}
|
| Harding BI, Pollak NM, Stefanovic D and Macdonald J (2019), "Repeated Reuse of Deoxyribozyme-Based Logic Gates", Nano Letters., October, 2019. Vol. 19(11), pp. 7655-7661. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Deoxyribozymes (DNAzymes) have demonstrated a significant capacity for biocomputing and hold promise for information processing within advanced biological devices if several key capabilities are developed. One required capability is reuse—having DNAzyme logic gates be cyclically, and controllably, activated and deactivated. We designed an oligonucleotide-based system for DNAzyme reuse that could (1) remove previously bound inputs by addition of complementary oligonucleotides via toe-hold mediated binding and (2) diminish output signal through the addition of quencher-labeled oligonucleotides complementary to the fluorophore-bound substrate. Our system demonstrated, for the first time, the ability for DNAzymes to have their activity toggled, with activity returning to 90−125% of original activity. This toggling could be performed multiple times with control being exerted over when the toggling occurs, with three clear cycles observed before the variability in activity became too great. Our data also demonstrated that fluorescent output of the DNAzyme activity could be actively removed and regenerated. This reuse system can increase the efficiency of DNAzyme-based logic circuits by reducing the number of redundant oligonucleotides and is critical for future development of reusable biodevices controlled by logical operations. |
BibTeX:
@article{Harding2019,
author = {Harding, Bradley I. and Pollak, Nina M. and Stefanovic, Darko and Macdonald, Joanne},
title = {Repeated Reuse of Deoxyribozyme-Based Logic Gates},
journal = {Nano Letters},
publisher = {American Chemical Society (ACS)},
year = {2019},
volume = {19},
number = {11},
pages = {7655--7661},
doi = {10.1021/acs.nanolett.9b02326}
}
|
| Fabry-Wood A, Fetrow ME, Oloyede A, Yang K-A, Stojanovic MN, Stefanovic D, Graves SW, Carroll NJ and Lakin MR (2019), "Microcompartments for Protection and Isolation of Nanoscale DNA Computing Elements", ACS Applied Materials & Interfaces., March, 2019. Vol. 11(12), pp. 11262-11269. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Physical isolation of molecular computing elements holds the potential for increasing system complexity by enabling the reuse of standardized components and by protecting the components from environmental degradation. However, once elements have been compartmentalized, methods for communicating into these compartments are needed. We report the compartmentalization of steroid-responsive DNA aptamers within giant unilamellar vesicles (GUVs) that are permeable to steroid inputs. Monodisperse GUVs are loaded with aptamers using a microfluidic platform. We demonstrate the target-specific activation of individual aptamers within the GUVs and then load two noninterfering aptamers into the same GUV and demonstrate specific responses to all possible combinations of the two input steroids. Crucially, GUVs prevent the degradation of DNA components by nucleases, providing a potential mechanism for deploying nucleic acid components in vivo. Importantly, our compartments also prevent nonspecific cross-talk between complementary strands, thereby providing a method for parallel execution of cross-reacting molecular logic components. Thus, we provide a mechanism for spatially organizing molecular computing elements, which will increase system modularity by allowing standardized components to be reused. |
BibTeX:
@article{FabryWood2019,
author = {Fabry-Wood, Aurora and Fetrow, Madalyn Elise and Oloyede, Ayomide and Yang, Kyung-Ae and Stojanovic, Milan N. and Stefanovic, Darko and Graves, Steven W. and Carroll, Nick J. and Lakin, Matthew R.},
title = {Microcompartments for Protection and Isolation of Nanoscale DNA Computing Elements},
journal = {ACS Applied Materials & Interfaces},
publisher = {American Chemical Society (ACS)},
year = {2019},
volume = {11},
number = {12},
pages = {11262--11269},
doi = {10.1021/acsami.9b03143}
}
|
| Stelle G, Stefanovic D, Olivier SL and Forrest S (2019), "Cactus Environment Machine: Shared Environment Call-by-Need", In Trends in Functional Programming. , pp. 24-43. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Existing machines for lazy evaluation use a flat representation of environments, storing the terms associated with free variables in an array. Combined with a heap, this structure supports the shared intermediate results required by lazy evaluation. We propose and describe an alternative approach that uses a shared environment to minimize the overhead of delayed computations. We show how a shared environment can act as both an environment and a mechanism for sharing results. To formalize this approach, we introduce a calculus that makes the shared environment explicit, as well as a machine to implement the calculus, the Cactus Environment Machine. A simple compiler implements the machine and is used to run experiments for assessing performance. The results show reasonable performance and suggest that incorporating this approach into real-world compilers could yield performance benefits in some scenarios. |
BibTeX:
@inbook{Stelle2019,
author = {Stelle, George and Stefanovic, Darko and Olivier, Stephen L. and Forrest, Stephanie},
title = {Cactus Environment Machine: Shared Environment Call-by-Need},
booktitle = {Trends in Functional Programming},
publisher = {Springer International Publishing},
year = {2019},
pages = {24--43},
doi = {10.1007/978-3-030-14805-8_2}
}
|
| Stefanovic D (2018), "A simplified account of cooperative effects in molecular walker teams", In Proceedings of the 5th ACM International Conference on Nanoscale Computing and Communication., September, 2018. , pp. 1-2. ACM.
[Abstract] [BibTeX] [DOI] [PDF]
|
| Abstract: We study the motion of random walkers with residence time bias between first and subsequent visits to a site, as a model for synthetic molecular walkers based on catalytic DNA known as molecular spiders. Even though a single one-legged walker does not exhibit directional, superdiffusive motion, we find that a team of one-legged walkers on parallel tracks, connected by a flexible tether, does enjoy a superdiffusive transient. |
BibTeX:
@inproceedings{Stefanovic2018,
author = {Stefanovic, Darko},
title = {A simplified account of cooperative effects in molecular walker teams},
booktitle = {Proceedings of the 5th ACM International Conference on Nanoscale Computing and Communication},
publisher = {ACM},
year = {2018},
pages = {1--2},
doi = {10.1145/3233188.3233218}
}
|
| Stelle G and Stefanovic D (2018), "Verifiably Lazy: Verified Compilation of Call-by-Need", In Proceedings of the 30th Symposium on Implementation and Application of Functional Languages., September, 2018. , pp. 49-58. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Call-by-need semantics underlies the widely used programming language Haskell. Unfortunately, unlike call-by-value counterparts, there are no verified compilers for call-by-need. In this paper we present the first verified compiler for call-by-need semantics. We use recent work on a simple call-by-need abstract machine as a way of reducing the formalization burden. We discuss some of the difficulties in verifying call-by-need, and show how we overcome them. |
BibTeX:
@inproceedings{Stelle2018,
author = {Stelle, George and Stefanovic, Darko},
title = {Verifiably Lazy: Verified Compilation of Call-by-Need},
booktitle = {Proceedings of the 30th Symposium on Implementation and Application of Functional Languages},
publisher = {ACM},
year = {2018},
pages = {49--58},
doi = {10.1145/3310232.3310236}
}
|
| Blount D, Banda P, Teuscher C and Stefanovic D (2017), "Feedforward Chemical Neural Network: An In Silico Chemical System That Learns XOR", Artificial Life., August, 2017. Vol. 23(3), pp. 295-317. MIT Press - Journals.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Inspired by natural biochemicals that perform complex information processing within living cells, we design and simulate a chemically implemented feedforward neural network, which learns by a novel chemical-reaction-based analogue of backpropagation. Our network is implemented in a simulated chemical system, where individual neurons are separated from each other by semipermeable cell-like membranes. Our compartmentalized, modular design allows a variety of network topologies to be constructed from the same building blocks. This brings us towards general-purpose, adaptive learning in chemico: wet machine learning in an embodied dynamical system. |
BibTeX:
@article{Blount2017,
author = {Blount, Drew and Banda, Peter and Teuscher, Christof and Stefanovic, Darko},
title = {Feedforward Chemical Neural Network: An In Silico Chemical System That Learns XOR},
journal = {Artificial Life},
publisher = {MIT Press - Journals},
year = {2017},
volume = {23},
number = {3},
pages = {295--317},
doi = {10.1162/artl_a_00233}
}
|
| Fabry-Wood A, Fetrow ME, Brown CW, Baker NA, Fernandez Oropeza N, Shreve AP, Montaño GA, Stefanovic D, Lakin MR and Graves SW (2017), "A Microsphere-Supported Lipid Bilayer Platform for DNA Reactions on a Fluid Surface", ACS Applied Materials & Interfaces., August, 2017. Vol. 9(35), pp. 30185-30195. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We report a versatile microsphere-supported lipid bilayer system that can serve as a general-purpose platform for implementing DNA nanotechnologies on a fluid surface. To demonstrate our platform, we implemented both toehold-mediated strand displacement (TMSD) and DNAzyme reactions, which are typically performed in solution and which are the cornerstone of DNA-based molecular logic and dynamic DNA nanotechnology, on the surface. We functionalized microspheres bearing supported lipid bilayers (μSLBs) with membrane-bound nucleic acid components. Using functionalized μSLBs, we developed TMSD and DNAzyme reactions by optimizing reaction conditions to reduce nonspecific interactions between DNA and phospholipids and to enhance bilayer stability. Additionally, the physical and optical properties of the bilayer were tuned via lipid composition and addition of fluorescently tagged lipids to create stable and multiplexable μSLBs that are easily read out by flow cytometry. Multiplexed TMSD reactions on μSLBs enabled the successful operation of a Dengue serotyping assay that correctly identified all 16 patterns of target sequences to demonstrate detection of DNA strands derived from the sequences of all four Dengue serotypes. The limit of detection for this assay was 3 nM. Furthermore, we demonstrated DNAzyme reactions on a fluid lipid surface, which benefit from free diffusion on the surface. This work provides the basis for expansion of both TMSD and DNAzyme based molecular reactions on supported lipid bilayers for use in molecular logic and DNA nanotechnology. As our system is multiplexable and results in fluid surfaces, it may be of use in compartmentalization and improved kinetics of molecular logic reactions and as a useful building block in a variety of DNA nanotechnology systems. |
BibTeX:
@article{FabryWood2017,
author = {Fabry-Wood, Aurora and Fetrow, Madalyn E. and Brown, Carl W. and Baker, Nicholas A. and Fernandez Oropeza, Nadiezda and Shreve, Andrew P. and Montaño, Gabriel A. and Stefanovic, Darko and Lakin, Matthew R. and Graves, Steven W.},
title = {A Microsphere-Supported Lipid Bilayer Platform for DNA Reactions on a Fluid Surface},
journal = {ACS Applied Materials & Interfaces},
publisher = {American Chemical Society (ACS)},
year = {2017},
volume = {9},
number = {35},
pages = {30185--30195},
doi = {10.1021/acsami.7b11046}
}
|
| Lakin MR and Stefanovic D (2017), "Towards Temporal Logic Computation Using DNA Strand Displacement Reactions", In Unconventional Computation and Natural Computation. , pp. 41-55. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Time-varying signals are ubiquitous throughout science, and studying the high-level temporal structure of such processes is of significant practical importance. In this context, techniques from computer science such as temporal logic are a powerful tool. Temporal logic allows one to describe temporal properties of time-varying processes, e.g., the order in which particular events occur. In this paper, we show that DNA strand displacement reaction networks can be used to implement computations that check certain temporal relationships within time-varying input signals. A key aspect of this work is the development of DNA circuits that incorporate a primitive memory, so that their behavior is influenced not just by the current observed chemical environment, but also by environments observed in the past. We formalize our circuit designs in the DSD programming language and use simulation results to confirm that they function as intended. This work opens up the possibility of developing DNA circuits capable of long-term monitoring of processes such as cellular function, and points to possible designs of future DNA circuits that can decide more sophisticated temporal logics. |
BibTeX:
@inbook{Lakin2017a,
author = {Lakin, Matthew R. and Stefanovic, Darko},
title = {Towards Temporal Logic Computation Using DNA Strand Displacement Reactions},
booktitle = {Unconventional Computation and Natural Computation},
publisher = {Springer International Publishing},
year = {2017},
pages = {41--55},
doi = {10.1007/978-3-319-58187-3_4}
}
|
| Mo D, Lakin MR and Stefanovic D (2016), "Logic circuits based on molecular spider systems", Biosystems., August, 2016. Vol. 146, pp. 10-25. Elsevier BV.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Spatial locality brings the advantages of computation speed-up and sequence reuse to molecular computing. In particular, molecular walkers that undergo localized reactions are of interest for implementing logic computations at the nanoscale. We use molecular spider walkers to implement logic circuits. We develop an extended multi-spider model with a dynamic environment wherein signal transmission is triggered via localized reactions, and use this model to implement three basic gates (AND, OR, NOT) and a cascading mechanism. We develop an algorithm to automatically generate the layout of the circuit. We use a kinetic Monte Carlo algorithm to simulate circuit computations, and we analyze circuit complexity: our design scales linearly with formula size and has a logarithmic time complexity. |
BibTeX:
@article{Mo2016,
author = {Mo, Dandan and Lakin, Matthew R. and Stefanovic, Darko},
title = {Logic circuits based on molecular spider systems},
journal = {Biosystems},
publisher = {Elsevier BV},
year = {2016},
volume = {146},
pages = {10--25},
doi = {10.1016/j.biosystems.2016.03.008}
}
|
| Lakin MR, Stojanovic MN and Stefanovic D (2016), "Implementing Molecular Logic Gates, Circuits, and Cascades Using DNAzymes", In Advances in Unconventional Computing., July, 2016. , pp. 1-28. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: The programmable nature of DNA chemistry makes it an attractive framework for the implementation of unconventional computing systems. Our early work in this area was among the first to use oligonucleotide-based logic gates to perform computations in a bulk solution. In this chapter we chart the development of this technology over the course of almost 15 years. We review our work on the implementation of DNA-based logic gates and circuits, which we have used to demonstrate digital logic circuits, autonomous game-playing automata, trainable systems and, more recently, decision-making circuits with potential diagnostic applications. |
BibTeX:
@inbook{Lakin2016a,
author = {Lakin, Matthew R. and Stojanovic, Milan N. and Stefanovic, Darko},
title = {Implementing Molecular Logic Gates, Circuits, and Cascades Using DNAzymes},
booktitle = {Advances in Unconventional Computing},
publisher = {Springer International Publishing},
year = {2016},
pages = {1--28},
doi = {10.1007/978-3-319-33921-4_1}
}
|
| Lakin MR, Stefanovic D and Phillips A (2016), "Modular verification of chemical reaction network encodings via serializability analysis", Theoretical Computer Science., June, 2016. Vol. 632, pp. 21-42. Elsevier BV.
[BibTeX] [DOI]
|
BibTeX:
@article{Lakin2016b,
author = {Lakin, Matthew R. and Stefanovic, Darko and Phillips, Andrew},
title = {Modular verification of chemical reaction network encodings via serializability analysis},
journal = {Theoretical Computer Science},
publisher = {Elsevier BV},
year = {2016},
volume = {632},
pages = {21--42},
doi = {10.1016/j.tcs.2015.06.033}
}
|
| Lakin MR and Stefanovic D (2016), "Supervised Learning in Adaptive DNA Strand Displacement Networks", ACS Synthetic Biology., May, 2016. Vol. 5(8), pp. 885-897. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: The development of engineered biochemical circuits that exhibit adaptive behavior is a key goal of synthetic biology and molecular computing. Such circuits could be used for long-term monitoring and control of biochemical systems, for instance, to prevent disease or to enable the development of artificial life. In this article, we present a framework for developing adaptive molecular circuits using buffered DNA strand displacement networks, which extend existing DNA strand displacement circuit architectures to enable straightforward storage and modification of behavioral parameters. As a proof of concept, we use this framework to design and simulate a DNA circuit for supervised learning of a class of linear functions by stochastic gradient descent. This work highlights the potential of buffered DNA strand displacement as a powerful circuit architecture for implementing adaptive molecular systems. |
BibTeX:
@article{Lakin2016,
author = {Lakin, Matthew R. and Stefanovic, Darko},
title = {Supervised Learning in Adaptive DNA Strand Displacement Networks},
journal = {ACS Synthetic Biology},
publisher = {American Chemical Society (ACS)},
year = {2016},
volume = {5},
number = {8},
pages = {885--897},
doi = {10.1021/acssynbio.6b00009}
}
|
| Mohr D and Stefanovic D (2016), "Stella: a python-based domain-specific language for simulations", In Proceedings of the 31st Annual ACM Symposium on Applied Computing., April, 2016. , pp. 1952-1959. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We wish to make it easier and quicker to write well-performing scientific simulations that (1) have single-thread performance competitive with low-level languages, (2) use object-oriented programming to properly structure the code, and (3) are very easy to develop. Instead of prototyping in a high-level language and then rewriting in a lower-level language, we created a DSL embedded in Python that is transparently usable, retains some OOP features, compiles to machine code, and executes at speed similar to C. |
BibTeX:
@inproceedings{Mohr2016,
author = {Mohr, David and Stefanovic, Darko},
title = {Stella: a python-based domain-specific language for simulations},
booktitle = {Proceedings of the 31st Annual ACM Symposium on Applied Computing},
publisher = {ACM},
year = {2016},
pages = {1952--1959},
doi = {10.1145/2851613.2851749}
}
|
| Burger J, Goudarzi A, Stefanovic D and Teuscher C (2015), "Hierarchical composition of memristive networks for real-time computing", In Proceedings of the 2015 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH´15)., July, 2015. , pp. 33-38. IEEE.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Advances in materials science have led to physical instantiations of self-assembled networks of memristive devices and demonstrations of their computational capability through reservoir computing. Reservoir computing is an approach that takes advantage of collective system dynamics for real-time computing. A dynamical system, called a reservoir, is excited with a time-varying signal and observations of its states are used to reconstruct a desired output signal. However, such a monolithic assembly limits the computational power due to signal interdependency and the resulting correlated readouts. Here, we introduce an approach that hierarchically composes a set of interconnected memristive networks into a larger reservoir. We use signal amplification and restoration to reduce reservoir state correlation, which improves the feature extraction from the input signals. Using the same number of output signals, such a hierarchical composition of heterogeneous small networks outperforms monolithic memristive networks by at least 20% on waveform generation tasks. On the NARMA-10 task, we reduce the error by up to a factor of 2 compared to homogeneous reservoirs with sigmoidal neurons, whereas single memristive networks are unable to produce the correct result. Hierarchical composition is key for solving more complex tasks with such novel nano-scale hardware. |
BibTeX:
@inproceedings{Burger2015a,
author = {Burger, Jens and Goudarzi, Alireza and Stefanovic, Darko and Teuscher, Christof},
title = {Hierarchical composition of memristive networks for real-time computing},
booktitle = {Proceedings of the 2015 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH´15)},
publisher = {IEEE},
year = {2015},
pages = {33--38},
doi = {10.1109/nanoarch.2015.7180583}
}
|
| Goudarzi A, Shabani A and Stefanovic D (2015), "Product reservoir computing: Time-series computation with multiplicative neurons", In 2015 International Joint Conference on Neural Networks (IJCNN)., July, 2015. , pp. 1-8. IEEE.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Echo state networks (ESN), a type of reservoir computing (RC) architecture, are efficient and accurate artificial neural systems for time series processing and learning. An ESN consists of a core of recurrent neural networks, called a reservoir, with a small number of tunable parameters to generate a high-dimensional representation of an input, and a readout layer which is easily trained using regression to produce a desired output from the reservoir states. Certain computational tasks involve real-time calculation of high-order time correlations, which requires nonlinear transformation either in the reservoir or the readout layer. Traditional ESN employs a reservoir with sigmoid or tanh function neurons. In contrast, some types of biological neurons obey response curves that can be described as a product unit rather than a sum and threshold. Inspired by this class of neurons, we introduce a RC architecture with a reservoir of product nodes for time series computation. We find that the product RC shows many properties of standard ESN such as short-term memory and nonlinear capacity. On standard benchmarks for chaotic prediction tasks, the product RC maintains the performance of a standard nonlinear ESN while being more amenable to mathematical analysis. Our study provides evidence that such networks are powerful in highly nonlinear tasks owing to high-order statistics generated by the recurrent product node reservoir. |
BibTeX:
@inproceedings{Goudarzi2015b,
author = {Goudarzi, Alireza and Shabani, Alireza and Stefanovic, Darko},
title = {Product reservoir computing: Time-series computation with multiplicative neurons},
booktitle = {2015 International Joint Conference on Neural Networks (IJCNN)},
publisher = {IEEE},
year = {2015},
pages = {1--8},
doi = {10.1109/ijcnn.2015.7280453}
}
|
| Goudarzi A, Arnold D, Stefanovic D, Ferreira KB and Feldman G (2015), "A Principled Approach to HPC Event Monitoring", In Proceedings of the 5th Workshop on Fault Tolerance for HPC at eXtreme Scale., June, 2015. , pp. 3-10. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: As high-performance computing (HPC) systems become larger and more complex, fault tolerance becomes a greater concern. At the same time, the data volume collected to help in understanding and mitigating hardware and software faults and failures also becomes prohibitively large. We argue that the HPC community must adopt more systematic approaches to system event logging as opposed to the current, ad hoc, strategies based on practitioner intuition and experience. Specifically, we show that event correlation and prediction can increase our understanding of fault behavior and can become critical components of effective fault tolerance strategies. While event correlation and prediction have been used in HPC contexts, we offer new insights about their potential capabilities. Using event logs from the computer failure data repository (cfdr) (1) we use cross and partial correlations to observe conditional correlations in HPC event data; (2) we use information theory to understand the fundamental predictive power of HPC failure data; (3) we study neural networks for failure prediction; and (4) finally, we use principal component analysis to understand to what extent dimensionality reduction can apply to HPC event data. This work results in the following insights that can inform HPC event monitoring: ad hoc correlations or ones based on direct correlations can be deficient or even misleading; highly accurate failure prediction may only require small windows of failure event history; and principal component analysis can significantly reduce HPC event data without loss of relevant information. |
BibTeX:
@inproceedings{Goudarzi2015,
author = {Goudarzi, Alireza and Arnold, Dorian and Stefanovic, Darko and Ferreira, Kurt B. and Feldman, Guy},
title = {A Principled Approach to HPC Event Monitoring},
booktitle = {Proceedings of the 5th Workshop on Fault Tolerance for HPC at eXtreme Scale},
publisher = {ACM},
year = {2015},
pages = {3--10},
doi = {10.1145/2751504.2751506}
}
|
| Goudarzi A, Shabani A and Stefanovic D (2015), "Exploring transfer function nonlinearity in echo state networks", In 2015 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA)., May, 2015. , pp. 1-8. IEEE.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Supralinear and sublinear pre-synaptic and dendritic integration is considered to be responsible for nonlinear computation power of biological neurons, emphasizing the role of nonlinear integration as opposed to nonlinear output thresholding. How, why, and to what degree the transfer function nonlinearity helps biologically inspired neural network models is not fully understood. Here, we study these questions in the context of echo state networks (ESN). ESN is a simple neural network architecture in which a fixed recurrent network is driven with an input signal, and the output is generated by a readout layer from the measurements of the network states. ESN architecture enjoys efficient training and good performance on certain signal-processing tasks, such as system identification and time series prediction. ESN performance has been analyzed with respect to the connectivity pattern in the network structure and the input bias. However, the effects of the transfer function in the network have not been studied systematically. Here, we use an approach tanh on the Taylor expansion of a frequently used transfer function, the hyperbolic tangent function, to systematically study the effect of increasing nonlinearity of the transfer function on the memory, nonlinear capacity, and signal processing performance of ESN. Interestingly, we find that a quadratic approximation is enough to capture the computational power of ESN with tanh function. The results of this study apply to both software and hardware implementation of ESN. |
BibTeX:
@inproceedings{Goudarzi2015a,
author = {Goudarzi, Alireza and Shabani, Alireza and Stefanovic, Darko},
title = {Exploring transfer function nonlinearity in echo state networks},
booktitle = {2015 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA)},
publisher = {IEEE},
year = {2015},
pages = {1--8},
doi = {10.1109/cisda.2015.7208637}
}
|
| Brown CW, Lakin MR, Fabry‐Wood A, Horwitz EK, Baker NA, Stefanovic D and Graves SW (2015), "A Unified Sensor Architecture for Isothermal Detection of Double‐Stranded DNA, Oligonucleotides, and Small Molecules", ChemBioChem., February, 2015. Vol. 16(5), pp. 725-730. Wiley.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Pathogen detection is an important problem in many areas of medicine and agriculture, which can involve genomic or transcriptomic signatures or small-molecule metabolites. We report a unified, DNA-based sensor architecture capable of isothermal detection of double-stranded DNA targets, single-stranded oligonucleotides, and small molecules. Each sensor contains independent target detection and reporter modules, enabling rapid design. We detected gene variants on plasmids by using a straightforward isothermal denaturation protocol. The sensors were highly specific, even with a randomized DNA background. We achieved a limit of detection of 15 pM for single-stranded targets and 5 nM for targets on denatured plasmids. By incorporating a blocked aptamer sequence, we also detected small molecules using the same sensor architecture. This work provides a starting point for multiplexed detection of multi-strain pathogens, and disease states caused by genetic variants (e.g., sickle cell anemia). |
BibTeX:
@article{Brown2015,
author = {Brown, Carl W. and Lakin, Matthew R. and Fabry‐Wood, Aurora and Horwitz, Eli K. and Baker, Nicholas A. and Stefanovic, Darko and Graves, Steven W.},
title = {A Unified Sensor Architecture for Isothermal Detection of Double‐Stranded DNA, Oligonucleotides, and Small Molecules},
journal = {ChemBioChem},
publisher = {Wiley},
year = {2015},
volume = {16},
number = {5},
pages = {725--730},
doi = {10.1002/cbic.201402615}
}
|
| Burger J, Goudarzi A, Stefanovic D and Teuscher C (2015), "Computational capacity and energy consumption of complex resistive switch networks", AIMS Materials Science. Vol. 2(4), pp. 530-545. American Institute of Mathematical Sciences (AIMS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Resistive switches are a class of emerging nanoelectronics devices that exhibit a wide variety of switching characteristics closely resembling behaviors of biological synapses. Assembled into random networks, such resistive switches produce emerging behaviors far more complex than that of individual devices. This was previously demonstrated in simulations that exploit information processing within these random networks to solve tasks that require nonlinear computation as well as memory. Physical assemblies of such networks manifest complex spatial structures and basic processing capabilities often related to biologically-inspired computing. We model and simulate random resistive switch networks and analyze their computational capacities. We provide a detailed discussion of the relevant design parameters and establish the link to the physical assemblies by relating the modeling parameters to physical parameters. More globally connected networks and an increased network switching activity are means to increase the computational capacity linearly at the expense of exponentially growing energy consumption. We discuss a new modular approach that exhibits higher computational capacities, and energy consumption growing linearly with the number of networks used. The results show how to optimize the trade-o between computational capacity and energy e ciency and are relevant for the design and fabrication of novel computing architectures that harness random assemblies of emerging nanodevices. |
BibTeX:
@article{Burger2015,
author = {Burger, Jens and Goudarzi, Alireza and Stefanovic, Darko and Teuscher, Christof},
title = {Computational capacity and energy consumption of complex resistive switch networks},
journal = {AIMS Materials Science},
publisher = {American Institute of Mathematical Sciences (AIMS)},
year = {2015},
volume = {2},
number = {4},
pages = {530--545},
doi = {10.3934/matersci.2015.4.530}
}
|
| Lakin MR and Stefanovic D (2015), "Supervised Learning in an Adaptive DNA Strand Displacement Circuit", In DNA Computing and Molecular Programming. , pp. 154-167. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: The development of DNA circuits capable of adaptive behavior is a key goal in DNA computing, as such systems would have potential applications in long-term monitoring and control of biological and chemical systems. In this paper, we present a framework for adaptive DNA circuits using buffered strand displacement gates, and demonstrate that this framework can implement supervised learning of linear functions. This work highlights the potential of buffered strand displacement as a powerful architecture for implementing adaptive molecular systems. |
BibTeX:
@inbook{Lakin2015,
author = {Lakin, Matthew R. and Stefanovic, Darko},
title = {Supervised Learning in an Adaptive DNA Strand Displacement Circuit},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer International Publishing},
year = {2015},
pages = {154--167},
doi = {10.1007/978-3-319-21999-8_10}
}
|
| Mo D, Lakin MR and Stefanovic D (2015), "Scalable Design of Logic Circuits Using an Active Molecular Spider System", In Information Processing in Cells and Tissues. , pp. 13-28. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: As spatial locality leads to advantages of computation speed-up and sequence reuse in molecular computing, molecular walkers that exhibit localized reactions are of interest for implementing logic computations. We use molecular spiders, which are a type of molecular walkers, to implement logic circuits. We develop an extended multi-spider model with a dynamic environment where signal transmission is triggered locally, and use this model to implement three basic gates (AND, OR, NOT) and a mechanism to cascade the gates. We use a kinetic Monte Carlo algorithm to simulate gate computations, and we analyze circuit complexity: our design scales linearly with formula size and has a logarithmic time complexity |
BibTeX:
@inbook{Mo2015,
author = {Mo, Dandan and Lakin, Matthew R. and Stefanovic, Darko},
title = {Scalable Design of Logic Circuits Using an Active Molecular Spider System},
booktitle = {Information Processing in Cells and Tissues},
publisher = {Springer International Publishing},
year = {2015},
pages = {13--28},
doi = {10.1007/978-3-319-23108-2_2}
}
|
| Lakin MR, Minnich A, Lane T and Stefanovic D (2014), "Design of a biochemical circuit motif for learning linear functions", Journal of The Royal Society Interface., December, 2014. Vol. 11(101), pp. 20140902. The Royal Society.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Learning and adaptive behaviour are fundamental biological processes. A key goal in the field of bioengineering is to develop biochemical circuit architectures with the ability to adapt to dynamic chemical environments. Here, we present a novel design for a biomolecular circuit capable of supervised learning of linear functions, using a model based on chemical reactions catalysed by DNAzymes. To achieve this, we propose a novel mechanism of maintaining and modifying internal state in biochemical systems, thereby advancing the state of the art in biomolecular circuit architecture. We use simulations to demonstrate that the circuit is capable of learning behaviour and assess its asymptotic learning performance, scalability and robustness to noise. Such circuits show great potential for building autonomous in vivo nanomedical devices. While such a biochemical system can tell us a great deal about the fundamentals of learning in living systems and may have broad applications in biomedicine (e.g. autonomous and adaptive drugs), it also offers some intriguing challenges and surprising behaviours from a machine learning perspective. |
BibTeX:
@article{Lakin2014a,
author = {Lakin, Matthew R. and Minnich, Amanda and Lane, Terran and Stefanovic, Darko},
title = {Design of a biochemical circuit motif for learning linear functions},
journal = {Journal of The Royal Society Interface},
publisher = {The Royal Society},
year = {2014},
volume = {11},
number = {101},
pages = {20140902},
doi = {10.1098/rsif.2014.0902}
}
|
| Lakin MR, Brown CW, Horwitz EK, Fanning ML, West HE, Stefanovic D and Graves SW (2014), "Biophysically Inspired Rational Design of Structured Chimeric Substrates for DNAzyme Cascade Engineering", PLoS ONE., October, 2014. Vol. 9(10), pp. e110986. Public Library of Science (PLoS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: The development of large-scale molecular computational networks is a promising approach to implementing logical decision making at the nanoscale, analogous to cellular signaling and regulatory cascades. DNA strands with catalytic activity (DNAzymes) are one means of systematically constructing molecular computation networks with inherent signal amplification. Linking multiple DNAzymes into a computational circuit requires the design of substrate molecules that allow a signal to be passed from one DNAzyme to another through programmed biochemical interactions. In this paper, we chronicle an iterative design process guided by biophysical and kinetic constraints on the desired reaction pathways and use the resulting substrate design to implement heterogeneous DNAzyme signaling cascades. A key aspect of our design process is the use of secondary structure in the substrate molecule to sequester a downstream effector sequence prior to cleavage by an upstream DNAzyme. Our goal was to develop a concrete substrate molecule design to achieve efficient signal propagation with maximal activation and minimal leakage. We have previously employed the resulting design to develop high-performance DNAzyme-based signaling systems with applications in pathogen detection and autonomous theranostics. |
BibTeX:
@article{Lakin2014,
author = {Lakin, Matthew R. and Brown, Carl W. and Horwitz, Eli K. and Fanning, M. Leigh and West, Hannah E. and Stefanovic, Darko and Graves, Steven W.},
editor = {Thattai, Mukund},
title = {Biophysically Inspired Rational Design of Structured Chimeric Substrates for DNAzyme Cascade Engineering},
journal = {PLoS ONE},
publisher = {Public Library of Science (PLoS)},
year = {2014},
volume = {9},
number = {10},
pages = {e110986},
doi = {10.1371/journal.pone.0110986}
}
|
| Krapivsky PL and Stefanovic D (2014), "Lattice gases with a point source", Journal of Statistical Mechanics: Theory and Experiment., September, 2014. Vol. 2014(9), pp. P09003. IOP Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We study diffusive lattice gases with local injection of particles, namely we assume that whenever the origin becomes empty, a new particle is immediately injected into the origin. We consider two lattice gases: a symmetric simple exclusion process and random walkers. The interplay between the injection events and the positions of the particles already present implies an effective collective interaction even for the ostensibly non-interacting random walkers. We determine the average total number of particles entering into the initially empty system. We also compute the average total number of distinct sites visited by all particles, and discuss the shape of the visited domain and the statistics of visits. |
BibTeX:
@article{Krapivsky2014,
author = {Krapivsky, P L and Stefanovic, Darko},
title = {Lattice gases with a point source},
journal = {Journal of Statistical Mechanics: Theory and Experiment},
publisher = {IOP Publishing},
year = {2014},
volume = {2014},
number = {9},
pages = {P09003},
doi = {10.1088/1742-5468/2014/09/p09003}
}
|
| Goudarzi A, Lakin MR, Stefanovic D and Teuscher C (2014), "A model for variation- and fault-tolerant digital logic using self-assembled nanowire architectures", In 2014 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH)., July, 2014. , pp. 116-121. IEEE.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Reconfiguration has been used for both defect- and fault-tolerant nanoscale architectures with regular structure. Recent advances in self-assembled nanowires have opened doors to a new class of electronic devices with irregular structure. For such devices, reservoir computing has been shown to be a viable approach to implement computation. This approach exploits the dynamical properties of a system rather than specifics of its structure. Here, we extend a model of reservoir computing, called the echo state network, to reflect more realistic aspects of self-assembled nanowire networks. As a proof of concept, we use echo state networks to implement basic building blocks of digital computing: AND, OR, and XOR gates, and 2-bit adder and multiplier circuits. We show that the system can operate perfectly in the presence of variations five orders of magnitude higher than ITRS's 2005 target, 6%, and achieves success rates 6 times higher than related approaches at half the cost. We also describe an adaptive algorithm that can detect faults in the system and reconfigure it to resume perfect operational condition. |
BibTeX:
@inproceedings{Goudarzi2014,
author = {Goudarzi, Alireza and Lakin, Matthew R. and Stefanovic, Darko and Teuscher, Christof},
title = {A model for variation- and fault-tolerant digital logic using self-assembled nanowire architectures},
booktitle = {2014 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH)},
publisher = {IEEE},
year = {2014},
pages = {116--121},
doi = {10.1109/nanoarch.2014.6880504}
}
|
| Poje JE, Kastratovic T, Macdonald AR, Guillermo AC, Troetti SE, Jabado OJ, Fanning ML, Stefanovic D and Macdonald J (2014), "Visual Displays that Directly Interface and Provide Read‐Outs of Molecular States via Molecular Graphics Processing Units", Angewandte Chemie International Edition., July, 2014. Vol. 53(35), pp. 9222-9225. Wiley.
[Abstract] [BibTeX] [DOI]
|
| Abstract: The monitoring of molecular systems usually requires sophisticated technologies to interpret nanoscale events into electronic-decipherable signals. We demonstrate a new method for obtaining read-outs of molecular states that uses graphics processing units made from molecular circuits. Because they are made from molecules, the units are able to directly interact with molecular systems. We developed deoxyribozyme-based graphics processing units able to monitor nucleic acids and output alphanumerical read-outs via a fluorescent display. Using this design we created a molecular 7-segment display, a molecular calculator able to add and multiply small numbers, and a molecular automaton able to diagnose Ebola and Marburg virus sequences. These molecular graphics processing units provide insight for the construction of autonomous biosensing devices, and are essential components for the development of molecular computing platforms devoid of electronics.10.1145/1378704.1378723 |
BibTeX:
@article{Poje2014,
author = {Poje, Julia E. and Kastratovic, Tamara and Macdonald, Andrew R. and Guillermo, Ana C. and Troetti, Steven E. and Jabado, Omar J. and Fanning, M. Leigh and Stefanovic, Darko and Macdonald, Joanne},
title = {Visual Displays that Directly Interface and Provide Read‐Outs of Molecular States via Molecular Graphics Processing Units},
journal = {Angewandte Chemie International Edition},
publisher = {Wiley},
year = {2014},
volume = {53},
number = {35},
pages = {9222--9225},
doi = {10.1002/anie.201402698}
}
|
| Brown CW, Lakin MR, Horwitz EK, Fanning ML, West HE, Stefanovic D and Graves SW (2014), "Signal Propagation in Multi‐Layer DNAzyme Cascades Using Structured Chimeric Substrates", Angewandte Chemie International Edition., June, 2014. Vol. 53(28), pp. 7183-7187. Wiley.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Signal propagation through enzyme cascades is a critical component of information processing in cellular systems. Although such systems have potential as biomolecular computing tools, rational design of synthetic protein networks remains infeasible. DNA strands with catalytic activity (DNAzymes) are an attractive alternative, enabling rational cascade design through predictable base-pair hybridization principles. Multi-layered DNAzyme signaling and logic cascades are now reported. Signaling between DNAzymes was achieved using a structured chimeric substrate (SCS) that releases a downstream activator after cleavage by an upstream DNAzyme. The SCS can be activated by various upstream DNAzymes, can be coupled to DNA strand-displacement devices, and is highly resistant to interference from background DNA. This work enables the rational design of synthetic DNAzyme regulatory networks, with potential applications in biomolecular computing, biodetection, and autonomous theranostics. |
BibTeX:
@article{Brown2014a,
author = {Brown, Carl W. and Lakin, Matthew R. and Horwitz, Eli K. and Fanning, M. Leigh and West, Hannah E. and Stefanovic, Darko and Graves, Steven W.},
title = {Signal Propagation in Multi‐Layer DNAzyme Cascades Using Structured Chimeric Substrates},
journal = {Angewandte Chemie International Edition},
publisher = {Wiley},
year = {2014},
volume = {53},
number = {28},
pages = {7183--7187},
doi = {10.1002/anie.201402691}
}
|
| Stojanovic MN, Stefanovic D and Rudchenko S (2014), "Exercises in Molecular Computing", Accounts of Chemical Research., May, 2014. Vol. 47(6), pp. 1845-1852. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: The successes of electronic digital logic have transformed every aspect of human life over the last half-century. The word “computer” now signifies a ubiquitous electronic device, rather than a human occupation. Yet evidently humans, large assemblies of molecules, can compute, and it has been a thrilling challenge to develop smaller, simpler, synthetic assemblies of molecules that can do useful computation. When we say that molecules compute, what we usually mean is that such molecules respond to certain inputs, for example, the presence or absence of other molecules, in a precisely defined but potentially complex fashion. The simplest way for a chemist to think about computing molecules is as sensors that can integrate the presence or absence of multiple analytes into a change in a single reporting property. Here we review several forms of molecular computing developed in our laboratories. |
BibTeX:
@article{Stojanovic2014,
author = {Stojanovic, Milan N. and Stefanovic, Darko and Rudchenko, Sergei},
title = {Exercises in Molecular Computing},
journal = {Accounts of Chemical Research},
publisher = {American Chemical Society (ACS)},
year = {2014},
volume = {47},
number = {6},
pages = {1845--1852},
doi = {10.1021/ar5000538}
}
|
| Banda P, Teuscher C and Stefanovic D (2014), "Training an asymmetric signal perceptron through reinforcement in an artificial chemistry", Journal of The Royal Society Interface., April, 2014. Vol. 11(93), pp. 20131100. The Royal Society.
[Abstract] [BibTeX] [DOI]
|
| Abstract: State-of-the-art biochemical systems for medical applications and chemical computing are application-specific and cannot be reprogrammed or trained once fabricated. The implementation of adaptive biochemical systems that would offer flexibility through programmability and autonomous adaptation faces major challenges because of the large number of required chemical species as well as the timing-sensitive feedback loops required for learning. In this paper, we begin addressing these challenges with a novel chemical perceptron that can solve all 14 linearly separable logic functions. The system performs asymmetric chemical arithmetic, learns through reinforcement and supports both Michaelis–Menten as well as mass-action kinetics. To enable cascading of the chemical perceptrons, we introduce thresholds that amplify the outputs. The simplicity of our model makes an actual wet implementation, in particular by DNA-strand displacement, possible. |
BibTeX:
@article{Banda2014,
author = {Banda, Peter and Teuscher, Christof and Stefanovic, Darko},
title = {Training an asymmetric signal perceptron through reinforcement in an artificial chemistry},
journal = {Journal of The Royal Society Interface},
publisher = {The Royal Society},
year = {2014},
volume = {11},
number = {93},
pages = {20131100},
doi = {10.1098/rsif.2013.1100}
}
|
| Brown CW, Lakin MR, Stefanovic D and Graves SW (2014), "Catalytic Molecular Logic Devices by DNAzyme Displacement", ChemBioChem., April, 2014. Vol. 15(7), pp. 950-954. Wiley.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Chemical reactions catalyzed by DNAzymes offer a route to programmable modification of biomolecules for therapeutic purposes. To this end, we have developed a new type of catalytic DNA-based logic gates in which DNAzyme catalysis is controlled via toehold-mediated strand displacement reactions. We refer to these as DNAzyme displacement gates. The use of toeholds to guide input binding provides a favorable pathway for input recognition, and the innate catalytic activity of DNAzymes allows amplification of nanomolar input concentrations. We demonstrate detection of arbitrary input sequences by rational introduction of mismatched bases into inhibitor strands. Furthermore, we illustrate the applicability of DNAzyme displacement to compute logic functions involving multiple logic gates. This work will enable sophisticated logical control of a range of biochemical modifications, with applications in pathogen detection and autonomous theranostics. |
BibTeX:
@article{Brown2014,
author = {Brown, Carl W. and Lakin, Matthew R. and Stefanovic, Darko and Graves, Steven W.},
title = {Catalytic Molecular Logic Devices by DNAzyme Displacement},
journal = {ChemBioChem},
publisher = {Wiley},
year = {2014},
volume = {15},
number = {7},
pages = {950--954},
doi = {10.1002/cbic.201400047}
}
|
| Goudarzi A, Lakin MR and Stefanovic D (2014), "Reservoir Computing Approach to Robust Computation Using Unreliable Nanoscale Networks", In Unconventional Computation and Natural Computation. , pp. 164-176. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: As we approach the physical limits of CMOS technology, advances in materials science and nanotechnology are making available a variety of unconventional computing substrates that can potentially replace top-down-designed silicon-based computing devices. Inherent stochasticity in the fabrication process and nanometer scale of these substrates inevitably lead to design variations, defects, faults, and noise in the resulting devices. A key challenge is how to harness such devices to perform robust computation. We propose reservoir computing as a solution. In reservoir computing, computation takes place by translating the dynamics of an excited medium, called a reservoir, into a desired output. This approach eliminates the need for external control and redundancy, and the programming is done using a closed-form regression problem on the output, which also allows concurrent programming using a single device. Using a theoretical model, we show that both regular and irregular reservoirs are intrinsically robust to structural noise as they perform computation. |
BibTeX:
@inbook{Goudarzi2014a,
author = {Goudarzi, Alireza and Lakin, Matthew R. and Stefanovic, Darko},
title = {Reservoir Computing Approach to Robust Computation Using Unreliable Nanoscale Networks},
booktitle = {Unconventional Computation and Natural Computation},
publisher = {Springer International Publishing},
year = {2014},
pages = {164--176},
doi = {10.1007/978-3-319-08123-6_14}
}
|
| Goudarzi A and Stefanovic D (2014), "Towards a Calculus of Echo State Networks", Procedia Computer Science. Vol. 41, pp. 176-181. Elsevier BV.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Reservoir computing is a recent trend in neural networks which uses the dynamical perturbations on the phase space of a system to compute a desired target function. We present how one can formulate an expectation of system performance in a simple class of reservoir computing called echo state networks. In contrast with previous theoretical frameworks, which only reveal an upper bound on the total memory in the system, we analytically calculate the entire memory curve as a function of the structure of the system and the properties of the input and the target function. We demonstrate the precision of our framework by validating its result for a wide range of system sizes and spectral radii. Our analytical calculation agrees with numerical simulations. To the best of our knowledge this work presents the first exact analytical characterization of the memory curve in echo state networks. |
BibTeX:
@article{Goudarzi2014b,
author = {Goudarzi, Alireza and Stefanovic, Darko},
title = {Towards a Calculus of Echo State Networks},
journal = {Procedia Computer Science},
publisher = {Elsevier BV},
year = {2014},
volume = {41},
pages = {176--181},
doi = {10.1016/j.procs.2014.11.101}
}
|
| Lakin MR and Stefanovic D (2014), "Pattern Formation by Spatially Organized Approximate Majority Reactions", In Unconventional Computation and Natural Computation. , pp. 254-266. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Pattern formation is a topic of great interest in biology and nanotechnology. In this paper we investigate a system of spatially-organized reactions inspired by a well-known distributed algorithm for approximate majority voting, and demonstrate that this system can lead to pattern formation from a randomly initialized starting state. We also show that the approximate majority reaction scheme can preserve an existing pattern in the face of noise, and that exerting control over reaction rates can influence the generated pattern. This work has potential applications in the rational design of pattern-forming systems in DNA nanotechnology and synthetic biology. |
BibTeX:
@inbook{Lakin2014b,
author = {Lakin, Matthew R. and Stefanovic, Darko},
title = {Pattern Formation by Spatially Organized Approximate Majority Reactions},
booktitle = {Unconventional Computation and Natural Computation},
publisher = {Springer International Publishing},
year = {2014},
pages = {254--266},
doi = {10.1007/978-3-319-08123-6_21}
}
|
| Semenov O, Stefanovic D and Stojanovic MN (2014), "The Effects of Multivalency and Kinetics in Nanoscale Search by Molecular Spiders", In Evolution, Complexity and Artificial Life. , pp. 161-175. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular spiders are nanoscale walkers made with catalytic DNA legs attached to a rigid body. They move over a surface of DNA substrates, cleaving them and leaving behind product DNA strands, which they are able to revisit. The cleavage and detachment from substrates together take more time than the detachment from products. This difference in residence time between substrates and products, in conjunction with the plurality of the legs, makes a spider move differently from an ordinary random walker. The number of legs, and their lengths, can be varied, and this defines how a spider moves on the surface, i.e., its gait. Here we define an abstract model of molecular spiders in two dimensions. Then, using Kinetic Monte Carlo simulation, we study how efficiently the spiders with various gaits are able to find specific targets on a finite two-dimensional lattice. Multi-legged spiders with certain gaits find their targets faster than regular random walkers. The search performance of spiders depends both on their gait and on the kinetic rate r, which describes the relative substrate/product “stickiness.” Spiders with gaits that allow more freedom of leg movement find their targets faster than spiders with more restrictive gaits. For each gait, there is an optimal value of r that minimizes the time to find all target sites. Spiders influence each other’s motion through stigmergy, and this also affects the search performance. |
BibTeX:
@inbook{Semenov2014,
author = {Semenov, Oleg and Stefanovic, Darko and Stojanovic, Milan N.},
title = {The Effects of Multivalency and Kinetics in Nanoscale Search by Molecular Spiders},
booktitle = {Evolution, Complexity and Artificial Life},
publisher = {Springer Berlin Heidelberg},
year = {2014},
pages = {161--175},
doi = {10.1007/978-3-642-37577-4_11}
}
|
| Stefanovic D, Stojanovic M, Olah M and Semenov O (2013), "Catalytic Molecular Walkers: Aspects of Product Release", In Advances in Artificial Life, ECAL 2013., September, 2013. , pp. 1134-1141. MIT Press.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We study a model of multi-legged catalytic molecular walkers that abstract a class of recently developed synthetic molecular motors. We focus on their kinetics of release of catalytic product, delineating the influence of chemical kinetic parameters, geometric configuration, and loss from surface, and also contrast with bulk kinetics of product release. We show that molecular walkers can achieve a uniform rate of release over long time scales, which can be exploited in applications. |
BibTeX:
@inproceedings{Stefanovic2013,
author = {Stefanovic, Darko and Stojanovic, Milan and Olah, Mark and Semenov, Oleg},
title = {Catalytic Molecular Walkers: Aspects of Product Release},
booktitle = {Advances in Artificial Life, ECAL 2013},
publisher = {MIT Press},
year = {2013},
pages = {1134--1141},
doi = {10.7551/978-0-262-31709-2-ch172}
}
|
| Semenov O, Mohr D and Stefanovic D (2013), "First-passage properties of molecular spiders", Physical Review E., July, 2013. Vol. 88(1), pp. 012724. American Physical Society (APS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular spiders are synthetic catalytic DNA-based nanoscale walkers. We study the mean first-passage time for abstract models of spiders moving on a finite two-dimensional lattice with various boundary conditions and compare it with the mean first-passage time of spiders moving on a one-dimensional track. We evaluate by how much the slowdown on newly visited sites, owing to catalysis, can improve the mean f10.1145/1133651.1133654irst-passage time of spiders and show that in one dimension, when both ends of the track are an absorbing boundary, the performance gain is lower than in two dimensions, when the absorbing boundary is a circle; this persists even when the absorbing boundary is a single site. |
BibTeX:
@article{Semenov2013,
author = {Semenov, Oleg and Mohr, David and Stefanovic, Darko},
title = {First-passage properties of molecular spiders},
journal = {Physical Review E},
publisher = {American Physical Society (APS)},
year = {2013},
volume = {88},
number = {1},
pages = {012724},
doi = {10.1103/physreve.88.012724}
}
|
| Olah MJ and Stefanovic D (2013), "Superdiffusive transport by multivalent molecular walkers moving under load", Physical Review E., June, 2013. Vol. 87(6), pp. 062713. American Physical Society (APS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We introduce a model for translational molecular motors to demonstrate that a multivalent catalytic walker with flexible, uncoordinated legs can transform the free energy of surface-bound substrate sites into mechanical work and undergo biased, superdiffusive motion, even in opposition to an external load force. The walker in the model lacks any inherent orientation of body or track, and its legs have no chemomechanical coupling other than the passive constraint imposed by their connection to a common body. Yet, under appropriate kinetic conditions, the walker's motion is biased in the direction of unvisited sites, which allows the walker to move nearly ballistically away from the origin as long as a local supply of unmodified substrate sites is available. The multivalent random walker model is mathematically formulated as a continuous-time Markov process and is studied numerically. We use Monte Carlo simulations to generate ensemble estimates of the mean squared displacement and mean work done for this nonergodic system. Our results show that a residence time bias between visited and unvisited sites leads to superdiffusive motion over significant times and distances. This mechanism can be used to adapt any enzyme-substrate system with appropriate kinetics for use as a functional chemical implementation of a molecular motor, without the need for structural anisotropy or conformationally mediated chemomechanical coordination. |
BibTeX:
@article{Olah2013,
author = {Olah, Mark J. and Stefanovic, Darko},
title = {Superdiffusive transport by multivalent molecular walkers moving under load},
journal = {Physical Review E},
publisher = {American Physical Society (APS)},
year = {2013},
volume = {87},
number = {6},
pages = {062713},
doi = {10.1103/physreve.87.062713}
}
|
| Goudarzi A, Lakin MR and Stefanovic D (2013), "DNA Reservoir Computing: A Novel Molecular Computing Approach", In DNA Computing and Molecular Programming. , pp. 76-89. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We propose a novel molecular computing approach based on reservoir computing. In reservoir computing, a dynamical core, called a reservoir, is perturbed with an external input signal while a readout layer maps the reservoir dynamics to a target output. Computation takes place as a transformation from the input space to a high-dimensional spatiotemporal feature space created by the transient dynamics of the reservoir. The readout layer then combines these features to produce the target output. We show that coupled deoxyribozyme oscillators can act as the reservoir. We show that despite using only three coupled oscillators, a molecular reservoir computer could achieve 90% accuracy on a benchmark temporal problem. |
BibTeX:
@inbook{Goudarzi2013,
author = {Goudarzi, Alireza and Lakin, Matthew R. and Stefanovic, Darko},
title = {DNA Reservoir Computing: A Novel Molecular Computing Approach},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer International Publishing},
year = {2013},
pages = {76--89},
doi = {10.1007/978-3-319-01928-4_6}
}
|
| Lakin MR, Phillips A and Stefanovic D (2013), "Modular Verification of DNA Strand Displacement Networks via Serializability Analysis", In DNA Computing and Molecular Programming. , pp. 133-146. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: DNA strand displacement gates can be used to emulate arbitrary chemical reactions, and a number of different schemes have been proposed to achieve this. Here we develop modular correctness proofs for strand displacement encodings of chemical reaction networks and show how they may be applied to two-domain strand displacement systems. Our notion of correctness is serializability of interleaved reaction encodings, and we infer this global property from the properties of the gates that encode the individual chemical reactions. This allows correctness to be inferred for arbitrary systems constructed using these components, and we illustrate this by applying our results to a two-domain implementation of a well-known approximate majority voting system. |
BibTeX:
@inbook{Lakin2013,
author = {Lakin, Matthew R. and Phillips, Andrew and Stefanovic, Darko},
title = {Modular Verification of DNA Strand Displacement Networks via Serializability Analysis},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer International Publishing},
year = {2013},
pages = {133--146},
doi = {10.1007/978-3-319-01928-4_10}
}
|
| Mo D and Stefanovic D (2013), "Iterative Self-assembly with Dynamic Strength Transformation and Temperature Control", In DNA Computing and Molecular Programming. , pp. 147-159. Springer International Publishing.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We propose an iterative approach to constructing regular shapes by self-assembly. Unlike previous approaches, which construct a shape in one go, our approach constructs a final shape by alternating the steps of assembling and disassembling, increasing the size of the shape iteratively. This approach is embedded into an extended hexagonal tile assembly system, with dynamic strength transformation and temperature control. We present the construction of equilateral triangles as an example and prove the uniqueness of the final shape. The tile complexity of this approach is O(1). |
BibTeX:
@inbook{Mo2013,
author = {Mo, Dandan and Stefanovic, Darko},
title = {Iterative Self-assembly with Dynamic Strength Transformation and Temperature Control},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer International Publishing},
year = {2013},
pages = {147--159},
doi = {10.1007/978-3-319-01928-4_11}
}
|
| Stefanovic D and Stojanovic MN (2013), "Computing Game Strategies", In The Nature of Computation. Logic, Algorithms, Applications. , pp. 383-392. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We revisit the problem of constructing strategies for simple position games. We derive a general, executable formalism for describing game rules and desired strategy properties. We present the outcomes for several variants of the familiar game of tic-tac-toe. |
BibTeX:
@inbook{Stefanovic2013a,
author = {Stefanovic, Darko and Stojanovic, Milan N.},
title = {Computing Game Strategies},
booktitle = {The Nature of Computation. Logic, Algorithms, Applications},
publisher = {Springer Berlin Heidelberg},
year = {2013},
pages = {383--392},
doi = {10.1007/978-3-642-39053-1_45}
}
|
| Semenov O, Olah MJ and Stefanovic D (2012), "Cooperative linear cargo transport with molecular spiders", Natural Computing., November, 2012. Vol. 12(2), pp. 259-276. Springer Science and Business Media LLC.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular spiders are nanoscale walkers made with DNA enzyme legs attached to a common body. They move over a surface of DNA substrates, cleaving them and leaving behind product DNA strands, which they are able to revisit. Simple one-dimensional models of spider motion show significant superdiffusive motion when the leg-substrate bindings are longer-lived than the leg-product bindings. This gives the spiders potential as a faster-than-diffusion transport mechanism. However, analysis shows that single-spider motion eventually decays into an ordinary diffusive motion, owing to the ever increasing size of the region of cleaved products. Inspired by cooperative behavior of natural molecular walkers, we propose a symmetric exclusion process model for multiple walkers interacting as they move over a one-dimensional lattice. We show that when walkers are sequentially released from the origin, the collective effect is to prevent the leading walkers from moving too far backwards. Hence, there is an effective outward pressure on the leading walkers that keeps them moving superdiffusively for longer times, despite the growth of the product region. Multi-spider systems move faster and farther than single spiders or systems with multiple simple random walkers. |
BibTeX:
@article{Semenov2012,
author = {Semenov, Oleg and Olah, Mark J. and Stefanovic, Darko},
title = {Cooperative linear cargo transport with molecular spiders},
journal = {Natural Computing},
publisher = {Springer Science and Business Media LLC},
year = {2012},
volume = {12},
number = {2},
pages = {259--276},
doi = {10.1007/s11047-012-9357-2}
}
|
| Stojanovic MN and Stefanovic D (2012), "Some Experiments and Models in Molecular Computing and Robotics". July, 2012.
[BibTeX] [DOI]
|
BibTeX:
@misc{Stojanovic2012,
author = {Stojanovic, Milan N. and Stefanovic, Darko},
title = {Some Experiments and Models in Molecular Computing and Robotics},
journal = {Biomolecular Information Processing},
publisher = {Wiley},
year = {2012},
pages = {133--143},
doi = {10.1002/9783527645480.ch8}
}
|
| Semenov O, Stefanovic D and Stojanovic MN (2012), "The Effects of Multivalency and Kinetics in Nanoscale Search by Molecular Spiders", In WIVACE2012, Italian Workshop on Artificial Life and Evolutionary Computation., February, 2012.
[Abstract] [BibTeX] [PDF]
|
| Abstract: Molecular spiders are nanoscale walkers made with catalytic DNA legs attached to a rigid body. They move over a surface of DNA substrates, cleaving them and leaving behind product DNA strands, which they are able to revisit. The legs cleave and detach from substrates more slowly than they detach from products. This difference in residence time and the presence of multiple legs make a spider move differently from an ordinary random walker. The number of legs, and their lengths, can be varied, and this defines how a spider moves on the surface, i.e., its gait. In this work we define an abstract model of molecular spiders. Using Kinetic Monte Carlo simulation, we study how efficiently spiders with various gaits are able to find specific targets on a two-dimensional lattice. Multi-legged spiders with certain gaits can find the targets faster than regular random walkers. The search performance of spiders depends on both their gait and the kinetic rate r describing the relative substrate/product “stickiness”. Spiders with gaits that allow more freedom for leg movements find their targets faster than spiders with more restrictive gaits. For every gait, there is an optimal value of r that minimizes the time to find all target sites. |
BibTeX:
@inproceedings{Semenov2012a,
author = {Oleg Semenov and Darko Stefanovic and Milan N. Stojanovic},
title = {The Effects of Multivalency and Kinetics in Nanoscale Search by Molecular Spiders},
booktitle = {WIVACE2012, Italian Workshop on Artificial Life and Evolutionary Computation},
year = {2012}
}
|
| Yang K-A, Pei R, Stefanovic D and Stojanovic MN (2012), "Optimizing Cross-reactivity with Evolutionary Search for Sensors", Journal of the American Chemical Society., January, 2012. Vol. 134(3), pp. 1642-1647. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We report a straightforward evolutionary procedure to build an optimal sensor array from a pool of DNA sequences oriented toward three-way junctions. The individual sensors were mined from this pool under separate selection pressures to interact with four steroids, while allowing cross-reactivity, in a manner designed to achieve perfect classification of individual steroids. The resulting sensor array had three sensors and displayed discriminatory capacity between steroid classes over full ranges of concentrations. We propose that similar protocols can be used whenever we have two or more classes of samples, with individual classes being defined through gross differences in ratios of dominant families of responsive components. |
BibTeX:
@article{Yang2012,
author = {Yang, Kyung-Ae and Pei, Renjun and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Optimizing Cross-reactivity with Evolutionary Search for Sensors},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2012},
volume = {134},
number = {3},
pages = {1642--1647},
doi = {10.1021/ja2084256}
}
|
| Lakin MR, Minnich A, Lane T and Stefanovic D (2012), "Towards a Biomolecular Learning Machine", In Unconventional Computation and Natural Computation. , pp. 152-163. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Learning and generalisation are fundamental behavioural traits of intelligent life. We present a synthetic biochemical circuit which can exhibit non-trivial learning and generalisation behaviours, which is a first step towards demonstrating that these behaviours may be realised at the molecular level. The aim of our system is to learn positive real-valued weights for a real-valued linear function of positive inputs. Mathematically, this can be viewed as solving a non-negative least-squares regression problem. Our design is based on deoxyribozymes, which are catalytic DNA strands. We present simulation results which demonstrate that the system can converge towards a desired set of weights after a number of training instances are provided. |
BibTeX:
@inbook{Lakin2012,
author = {Lakin, Matthew R. and Minnich, Amanda and Lane, Terran and Stefanovic, Darko},
title = {Towards a Biomolecular Learning Machine},
booktitle = {Unconventional Computation and Natural Computation},
publisher = {Springer Berlin Heidelberg},
year = {2012},
pages = {152--163},
doi = {10.1007/978-3-642-32894-7_15}
}
|
| Olah MJ, Mohr D and Stefanovic D (2012), "Representing Uniqueness Constraints in Object-Relational Mapping: The Natural Entity Framework", In Objects, Models, Components, Patterns. , pp. 236-251. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Object-oriented languages model data as transient objects, while relational databases store data persistently using a relational data model. The process of making objects persistent by storing their state as relational tuples is called object-relational mapping (ORM). This process is nuanced and complex as there are many fundamental differences between the relational model and the object model. In this work we address the difficulties in representing entity identity and uniqueness consistently, efficiently, and succinctly in ORM. We introduce the natural entity framework, which: (1) provides a strong concept of value-based persistent object identity; (2) allows the programmer to simultaneously specify natural and surrogate key constraints consistently in the object and relational representations; (3) provides object constructors and initializers that disambiguate the semantics of persistent object creation and retrieval; and (4) automates the mapping of inheritance hierarchies that respect natural key constraints and allows for efficient polymorphic queries and associations. |
BibTeX:
@inbook{Olah2012,
author = {Olah, Mark J. and Mohr, David and Stefanovic, Darko},
title = {Representing Uniqueness Constraints in Object-Relational Mapping: The Natural Entity Framework},
booktitle = {Objects, Models, Components, Patterns},
publisher = {Springer Berlin Heidelberg},
year = {2012},
pages = {236--251},
doi = {10.1007/978-3-642-30561-0_17}
}
|
| Stefanovic D (2012), "Maze Exploration with Molecular-Scale Walkers", In Theory and Practice of Natural Computing. , pp. 216-226. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular spiders are nanoscale walkers made with catalytic DNA legs attached to a rigid body. They move in a matrix of DNA substrates, cleaving them and leaving behind product DNA strands. Unlike a self-avoiding walker, a spider is able to revisit the products. However, the legs cleave and detach from substrates more slowly than they detach from products. This difference in residence time and the presence of multiple legs make a spider move differently from an ordinary random walker. The number of legs, and their lengths, can be varied, and this defines the spider’s local gait, which affects its behavior in global tasks. In this work we define an abstract model of molecular spiders, and within it we study the efficiency of maze exploration as a function of the spider structure. For a fixed geometry, there is an optimal setting of chemical kinetics parameters that minimizes the mean time to traverse a maze. |
BibTeX:
@inbook{Stefanovic2012,
author = {Stefanovic, Darko},
title = {Maze Exploration with Molecular-Scale Walkers},
booktitle = {Theory and Practice of Natural Computing},
publisher = {Springer Berlin Heidelberg},
year = {2012},
pages = {216--226},
doi = {10.1007/978-3-642-33860-1_18}
}
|
| Fanning ML, Macdonald J and Stefanovic D (2011), "ISO: numeric representation of nucleic acid form", In Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine., August, 2011. , pp. 404-408. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We report a representation, ISO, that unambiguously and compactly describes patterns in nucleic acid secondary structure. ISO is equally expressive as other methodologies including dot-parenthesis notation, and various structure graph variations, for representation of well-formed structure patterns. ISO naturally expresses pseudoknot structures as well, without a change or extension in notation, an advantage not possible with commonly used representations. The numerical basis of ISO is readily amenable to development of mathematical evaluation rules, distance metrics, and further abstraction for either design or analysis purposes. In this way, ISO provides an easy mechanism for high-throughput in silico screening of sequence variants for architecting new synthetic systems, and better understanding of structure-function relationships and structure space in natural systems. |
BibTeX:
@inproceedings{Fanning2011,
author = {Fanning, M. Leigh and Macdonald, Joanne and Stefanovic, Darko},
title = {ISO: numeric representation of nucleic acid form},
booktitle = {Proceedings of the 2nd ACM Conference on Bioinformatics, Computational Biology and Biomedicine},
publisher = {ACM},
year = {2011},
pages = {404--408},
doi = {10.1145/2147805.2147859}
}
|
| Stojanovic MN and Stefanovic D (2011), "Chemistry at a Higher Level of Abstraction", Journal of Computational and Theoretical Nanoscience., March, 2011. Vol. 8(3), pp. 434-440. American Scientific Publishers.
[Abstract] [BibTeX] [DOI]
|
| Abstract: In this review we discuss our approach to molecular computing and molecular robotics based on nucleic acid catalysts or deoxyribozymes. We will demonstrate how the application of some simple concepts developed for digital computing and macroscopic robotics enables engineering of complex and intriguing behaviors in molecular systems. |
BibTeX:
@article{Stojanovic2011,
author = {Stojanovic, Milan N. and Stefanovic, Darko},
title = {Chemistry at a Higher Level of Abstraction},
journal = {Journal of Computational and Theoretical Nanoscience},
publisher = {American Scientific Publishers},
year = {2011},
volume = {8},
number = {3},
pages = {434--440},
doi = {10.1166/jctn.2011.1707}
}
|
| Semenov O, Olah MJ and Stefanovic D (2011), "Mechanism of diffusive transport in molecular spider models", Physical Review E., February, 2011. Vol. 83(2), pp. 021117. American Physical Society (APS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Recent advances in single-molecule chemistry have led to designs for artificial multipedal walkers that follow tracks of chemicals. We investigate the motion of a class of walkers, called molecular spiders, which consist of a rigid chemically inert body and several flexible enzymatic legs. The legs can reversibly bind to chemical substrates on a surface and through their enzymatic action convert them to products. The legs can also reversibly bind to products, but at a different rate. Antal and Krapivsky have proposed a model for molecular spider motion over regular one-dimensional lattices [T. Antal and P. L. Krapivsky, Phys. Rev. E 76, 021121 (2007).]. In the model the legs hop from site to site under constraints imposed by connection to a common body. The first time a leg visits a site, the site is an uncleaved substrate, and the leg hops from this site only once it has cleaved it into a product. This cleavage happens at a rate r<1, slower than dissociation from a product site, r=1. The effect of cleavage is to slow down the hopping rate for legs that visit a site for the first time. Along with the constraints imposed on the legs, this leads to an effective bias in the direction of unvisited sites that decreases the average time needed to visit n sites. The overall motion, however, remains diffusive in the long time limit. We have reformulated the Antal-Krapivsky model as a continuous-time Markov process and simulated many traces of this process using kinetic Monte Carlo techniques. Our simulations show a previously unpredicted transient behavior wherein spiders with small r values move superdiffusively over significant distances and times. We explain this transient period of superdiffusive behavior by describing the spider process as switching between two metastates: a diffusive state D wherein the spider moves in an unbiased manner over previously visited sites, and a boundary state B wherein the spider is on the boundary between regions of visited and unvisited sites and experiences a bias in the direction of unvisited sites. We show that while the spider remains in the B state it moves ballistically in the direction of unvisited sites, and while the spider is in the D state it moves diffusively. The relative amount of time the spider spends in the two states determines how superdiffusively the spider moves. We show that the B state is Markovian, but the D state is non-Markovian because the duration of a D period depends on how many sites have been visited previously. As time passes the spider spends progressively more time in the D state (moving diffusively) and less time in the B state (moving ballistically). This explains both the transient superdiffusive motion and the eventual decay to diffusive motion as t→∞. |
BibTeX:
@article{Semenov2011,
author = {Semenov, Oleg and Olah, Mark J. and Stefanovic, Darko},
title = {Mechanism of diffusive transport in molecular spider models},
journal = {Physical Review E},
publisher = {American Physical Society (APS)},
year = {2011},
volume = {83},
number = {2},
pages = {021117},
doi = {10.1103/physreve.83.021117}
}
|
| Olah MJ and Stefanovic D (2011), "Multivalent Random Walkers — A Model for Deoxyribozyme Walkers", In DNA Computing and Molecular Programming. , pp. 160-174. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We propose a stochastic model for molecular transport at the nanoscale that describes the motion of two-dimensional molecular assemblies called multivalent random walkers (MVRWs). This walker model is an abstract description of the motion of multipedal molecular assemblies, called molecular spiders, which use deoxyribozyme legs to move over a surface covered with substrate DNA molecules, cleaving them to produce shorter product DNA molecules as they go. In this model a walker has a rigid inert body and several flexible enzymatic legs. A walker moves over a surface of fixed chemical sites. Each site has one of several molecular species displayed, and walker legs can bind to and unbind from these sites to move over the surface. Additionally, the enzymatic activity of the legs allows them to catalyze irreversible chemical changes to the sites, thereby permanently modifying the state of the surface. We describe a MVRW system as a continuous-time Markov process, where all state transitions in the process correspond to chemical reactions of the legs with the sites.We model the kinetics of the leg reactions by considering the constrained diffusion of the walker body and unattached leg. Through kinetic Monte Carlo simulations, we show that the irreversibility of the enzymatic action of the legs can bias the motion of walkers and cause them to move superdiffusively over significant distances. |
BibTeX:
@inbook{Olah2011,
author = {Olah, Mark J. and Stefanovic, Darko},
title = {Multivalent Random Walkers — A Model for Deoxyribozyme Walkers},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer Berlin Heidelberg},
year = {2011},
pages = {160--174},
doi = {10.1007/978-3-642-23638-9_14}
}
|
| Semenov O, Olah MJ and Stefanovic D (2011), "Multiple Molecular Spiders with a Single Localized Source—The One-Dimensional Case", In DNA Computing and Molecular Programming. , pp. 204-216. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Molecular spiders are nanoscale walkers made with DNA enzyme legs attached to a common body. They move over a surface of DNA substrates, cleaving them and leaving behind product DNA strands, which they are able to revisit. Simple one-dimensional models of spider motion show significant superdiffusive motion when the leg-substrate bindings are longer-lived than the leg-product bindings. This gives the spiders potential as a faster-than-diffusion transport mechanism. However, analysis shows that single-spider motion eventually decays into an ordinary diffusive motion, owing to the ever increasing size of the region of cleaved products. Inspired by cooperative behavior of natural molecular walkers, we propose a model for multiple walkers moving collectively over a one-dimensional lattice. We show that when walkers are sequentially released from the origin, the collective effect is to prevent the leading walkers from moving too far backwards. Hence there is an effective outward pressure on the leading walkers that keeps them moving superdiffusively for longer times, despite the growth of the product region. |
BibTeX:
@inbook{Semenov2011a,
author = {Semenov, Oleg and Olah, Mark J. and Stefanovic, Darko},
title = {Multiple Molecular Spiders with a Single Localized Source—The One-Dimensional Case},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer Berlin Heidelberg},
year = {2011},
pages = {204--216},
doi = {10.1007/978-3-642-23638-9_17}
}
|
| Pei R, Matamoros E, Liu M, Stefanovic D and Stojanovic MN (2010), "Training a molecular automaton to play a game", Nature Nanotechnology., October, 2010. Vol. 5(11), pp. 773-777. Springer Science and Business Media LLC.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Research at the interface between chemistry and cybernetics has led to reports of ‘programmable molecules’, but what does it mean to say ‘we programmed a set of solution-phase molecules to do X’? A survey of recently implemented solution-phase circuitry indicates that this statement could be replaced with ‘we pre-mixed a set of molecules to do X and functional subsets of X’. These hard-wired mixtures are then exposed to a set of molecular inputs, which can be interpreted as being keyed to human moves in a game, or as assertions of logical propositions. In nucleic acids-based systems, stemming from DNA computation, these inputs can be seen as generic oligonucleotides. Here, we report using reconfigurable nucleic acid catalyst-based units to build a multipurpose reprogrammable molecular automaton that goes beyond single-purpose ‘hard-wired’ molecular automata. The automaton covers all possible responses to two consecutive sets of four inputs (such as four first and four second moves for a generic set of trivial two-player two-move games). This is a model system for more general molecular field programmable gate array (FPGA)-like devices that can be programmed by example, which means that the operator need not have any knowledge of molecular computing methods. |
BibTeX:
@article{Pei2010,
author = {Pei, Renjun and Matamoros, Elizabeth and Liu, Manhong and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Training a molecular automaton to play a game},
journal = {Nature Nanotechnology},
publisher = {Springer Science and Business Media LLC},
year = {2010},
volume = {5},
number = {11},
pages = {773--777},
doi = {10.1038/nnano.2010.194}
}
|
| Marron M, Majumdar R, Stefanovic D and Kapur D (2010), "Shape Analysis with Reference Set Relations", In Verification, Model Checking, and Abstract Interpretation. , pp. 247-262. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Tracking subset relations between the contents containers on the heap is fundamental to modeling the semantics of many common programing idioms such as applying a function to a subset of objects and maintaining multiple views of the same set of objects. We introduce a relation, must reference sets, which subsumes the concept of must-aliasing and enables existing shape analysis techniques to efficiently and accurately model many types of containment properties without the use of explicit quantification or specialized logics for containers/sets. We extend an existing shape analysis to model the concept of reference sets. Reference sets allow the analysis to efficiently track a number of important relations (must-=, and must-⊆) between objects that are the targets of sets of references (variables or pointers). We show that shape analysis augmented with reference set information is able to precisely model sharing for a range of data structures in real programs that cannot be expressed using simple must-alias information. In contrast to more expressive proposals based on logic languages (e.g., extensions of first-order predicate logic with transitive closure or the use of a decision procedure for sets), reference sets can be efficiently tracked in a shape analyzer. |
BibTeX:
@inbook{Marron2010,
author = {Marron, Mark and Majumdar, Rupak and Stefanovic, Darko and Kapur, Deepak},
title = {Shape Analysis with Reference Set Relations},
booktitle = {Verification, Model Checking, and Abstract Interpretation},
publisher = {Springer Berlin Heidelberg},
year = {2010},
pages = {247--262},
doi = {10.1007/978-3-642-11319-2_19}
}
|
| Stefanovic D (2009), "Molecules that reason", Nature Nanotechnology., October, 2009. Vol. 4(10), pp. 625-626. Springer Science and Business Media LLC.
[BibTeX] [DOI]
|
BibTeX:
@article{Stefanovic2009,
author = {Stefanovic, Darko},
title = {Molecules that reason},
journal = {Nature Nanotechnology},
publisher = {Springer Science and Business Media LLC},
year = {2009},
volume = {4},
number = {10},
pages = {625--626},
doi = {10.1038/nnano.2009.284}
}
|
| Fanning ML, Macdonald J and Stefanovic D (2009), "Advancing the Deoxyribozyme-Based Logic Gate Design Process", In DNA Computing and Molecular Programming. , pp. 45-54. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We previously described a tic-tac-toe playing molecular automaton, MAYA-II, constructed from a molecular array of deoxyribozyme-based logic gates, that uses oligonucleotides as inputs and outputs. We are now developing an ensemble modeling tool for high-throughput oligonucleotide input and logic gate designs. The modeling tool is based on exhaustive reconstruction of both intended and unintended reactions between MAYA-II gates and inputs, and seeks to directly correlate empirical observations with computational predictions. Here we describe exhaustive analysis of the MAYA-II Yes logic gates folding structures, both alone and in conjunction with the MAYA-II oligonucleotide inputs. Results indicate that in silico modeling accurately reflects experimental results, creating a predictive value and benchmark for future high-throughput oligonucleotide input and Yes gate designs. These studies serve purpose towards our goal of constructing a generalized oligonucleotide design library for expansion of molecular computation beyond hundreds, to millions of potential interactions, conferring greater functionality in terms of both reliability and complexity. |
BibTeX:
@inbook{Fanning2009,
author = {Fanning, M. Leigh and Macdonald, Joanne and Stefanovic, Darko},
title = {Advancing the Deoxyribozyme-Based Logic Gate Design Process},
booktitle = {DNA Computing and Molecular Programming},
publisher = {Springer Berlin Heidelberg},
year = {2009},
pages = {45--54},
doi = {10.1007/978-3-642-10604-0_5}
}
|
| Macdonald J, Stefanovic D and Stojanovic M (2009), "Molecular Automata", In Encyclopedia of Complexity and Systems Science. , pp. 5631-5655. Springer New York.
[BibTeX] [DOI]
|
BibTeX:
@inbook{Macdonald2009,
author = {Macdonald, Joanne and Stefanovic, Darko and Stojanovic, Milan},
title = {Molecular Automata},
booktitle = {Encyclopedia of Complexity and Systems Science},
publisher = {Springer New York},
year = {2009},
pages = {5631--5655},
doi = {10.1007/978-0-387-30440-3_335}
}
|
| Pei R, Shen A, Olah MJ, Stefanovic D, Worgall T and Stojanovic MN (2009), "High-resolution cross-reactive array for alkaloids", Chemical Communications. (22), pp. 3193. Royal Society of Chemistry (RSC).
[Abstract] [BibTeX] [DOI]
|
| Abstract: A high-resolution cross-reactive array capable of classifying alkaloids over a range of concentrations was generated by systematic introduction of a nitroindole analog into a hydrophobic pocket within a DNA three-way junction to match structural motifs presented by the analytes. |
BibTeX:
@article{Pei2009,
author = {Pei, Renjun and Shen, Aihua and Olah, Mark J. and Stefanovic, Darko and Worgall, Tilla and Stojanovic, Milan N.},
title = {High-resolution cross-reactive array for alkaloids},
journal = {Chemical Communications},
publisher = {Royal Society of Chemistry (RSC)},
year = {2009},
number = {22},
pages = {3193},
doi = {10.1039/b900001a}
}
|
| Macdonald J, Stefanovic D and Stojanovic MN (2008), "DNA Computers for Work and Play", Scientific American., November, 2008. Vol. 299(5), pp. 84-91. Springer Science and Business Media LLC.
[BibTeX] [DOI]
|
BibTeX:
@article{Macdonald2008,
author = {Macdonald, Joanne and Stefanovic, Darko and Stojanovic, Milan N.},
title = {DNA Computers for Work and Play},
journal = {Scientific American},
publisher = {Springer Science and Business Media LLC},
year = {2008},
volume = {299},
number = {5},
pages = {84--91},
doi = {10.1038/scientificamerican1108-84}
}
|
| Marron M, Méndez-Lojo M, Hermenegildo M, Stefanovic D and Kapur D (2008), "Sharing analysis of arrays, collections, and recursive structures", In Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering., November, 2008. , pp. 43-49. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of significant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel version. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efficient manner. The effectiveness of the approach is evaluated on a set of challenge problems from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups. |
BibTeX:
@inproceedings{Marron2008a,
author = {Marron, Mark and Méndez-Lojo, Mario and Hermenegildo, Manuel and Stefanovic, Darko and Kapur, Deepak},
title = {Sharing analysis of arrays, collections, and recursive structures},
booktitle = {Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering},
publisher = {ACM},
year = {2008},
pages = {43--49},
doi = {10.1145/1512475.1512485}
}
|
| Blackburn SM, McKinley KS, Garner R, Hoffmann C, Khan AM, Bentzur R, Diwan A, Feinberg D, Frampton D, Guyer SZ, Hirzel M, Hosking A, Jump M, Lee H, Moss JEB, Phansalkar A, Stefanovic D, VanDrunen T, von Dincklage D and Wiedermann B (2008), "Wake up and smell the coffee: evaluation methodology for the 21st century", Communications of the ACM., August, 2008. Vol. 51(8), pp. 83-89. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Evaluation methodology underpins all innovation in experimental computer science. It requires relevant workloads, appropriate experimental design, and rigorous analysis. Unfortunately, methodology is not keeping pace with the changes in our field. |
BibTeX:
@article{Blackburn2008,
author = {Blackburn, Stephen M. and McKinley, Kathryn S. and Garner, Robin and Hoffmann, Chris and Khan, Asjad M. and Bentzur, Rotem and Diwan, Amer and Feinberg, Daniel and Frampton, Daniel and Guyer, Samuel Z. and Hirzel, Martin and Hosking, Antony and Jump, Maria and Lee, Han and Moss, J. Eliot B. and Phansalkar, Aashish and Stefanovic, Darko and VanDrunen, Thomas and von Dincklage, Daniel and Wiedermann, Ben},
title = {Wake up and smell the coffee: evaluation methodology for the 21st century},
journal = {Communications of the ACM},
publisher = {Association for Computing Machinery (ACM)},
year = {2008},
volume = {51},
number = {8},
pages = {83--89},
doi = {10.1145/1378704.1378723}
}
|
| Marron M, Hermenegildo M, Kapur D and Stefanovic D (2008), "Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models", In Compiler Construction. , pp. 245-259. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: The performance of heap analysis techniques has a significant impact on their utility in an optimizing compiler.Most shape analysis techniques perform interprocedural dataflow analysis in a context-sensitive manner, which can result in analyzing each procedure body many times (causing significant increases in runtime even if the analysis results are memoized). To improve the effectiveness of memoization (and thus speed up the analysis) project/extend operations are used to remove portions of the heap model that cannot be affected by the called procedure (effectively reducing the number of different contexts that a procedure needs to be analyzed with). This paper introduces project/extend operations that are capable of accurately modeling properties that are important when analyzing non-trivial programs (sharing, nullity information, destructive recursive functions, and composite data structures). The techniques we introduce are able to handle these features while significantly improving the effectiveness of memoizing analysis results (and thus improving analysis performance). Using a range of well known benchmarks (many of which have not been successfully analyzed using other existing shape analysis methods) we demonstrate that our approach results in significant improvements in both accuracy and efficiency over a baseline analysis. |
BibTeX:
@inbook{Marron2008b,
author = {Marron, Mark and Hermenegildo, Manuel and Kapur, Deepak and Stefanovic, Darko},
title = {Efficient Context-Sensitive Shape Analysis with Graph Based Heap Models},
booktitle = {Compiler Construction},
publisher = {Springer Berlin Heidelberg},
year = {2008},
pages = {245--259},
doi = {10.1007/978-3-540-78791-4_17}
}
|
| Marron M, Stefanovic D, Kapur D and Hermenegildo M (2008), "Identification of Heap–Carried Data Dependence Via Explicit Store Heap Models", In Languages and Compilers for Parallel Computing. , pp. 94-108. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Dependence information between program values is extensively used in many program optimization techniques. The ability to identify statements, calls and loop iterations that do not depend on each other enables many transformations which increase the instruction and thread-level parallelism in a program. When program variables contain complex data structures including arrays, records, and recursive data structures, the ability to precisely model data dependence based on heap structure remains a challenging problem. This paper presents a technique for precisely tracking heap based data dependence in non-trivial Java programs via static analysis. Using an abstract interpretation framework, the approach extends a shape analysis technique based on an existing graph model of heaps, by integrating read/write history information and intelligent memoization. The method has been implemented and its effectiveness and utility are demonstrated by computing detailed dependence information for two benchmarks (Em3d and BH from the JOlden suite) and using this information to parallelize the benchmarks. |
BibTeX:
@inbook{Marron2008,
author = {Marron, Mark and Stefanovic, Darko and Kapur, Deepak and Hermenegildo, Manuel},
title = {Identification of Heap–Carried Data Dependence Via Explicit Store Heap Models},
booktitle = {Languages and Compilers for Parallel Computing},
publisher = {Springer Berlin Heidelberg},
year = {2008},
pages = {94--108},
doi = {10.1007/978-3-540-89740-8_7}
}
|
| Sager J, Farfel J and Stefanovic D (2008), "Nanocomputing", In NanoBioTechnology. , pp. 215-265. Humana Press.
[BibTeX] [DOI]
|
BibTeX:
@inbook{Sager,
author = {Sager, Jennifer and Farfel, Joseph and Stefanovic, Darko},
title = {Nanocomputing},
booktitle = {NanoBioTechnology},
publisher = {Humana Press},
year = {2008},
pages = {215--265},
doi = {10.1007/978-1-59745-218-2_10}
}
|
| Stefanovic D (2008), "Emerging Models of Computation: Directions in Molecular Computing", In Software-Intensive Systems and New Computing Paradigms. , pp. 255-265. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: 10.1145/511334.511352 |
BibTeX:
@inbook{Stefanovic2008,
author = {Stefanovic, Darko},
title = {Emerging Models of Computation: Directions in Molecular Computing},
booktitle = {Software-Intensive Systems and New Computing Paradigms},
publisher = {Springer Berlin Heidelberg},
year = {2008},
pages = {255--265},
doi = {10.1007/978-3-540-89437-7_16}
}
|
| Marron M, Stefanovic D, Hermenegildo M and Kapur D (2007), "Heap analysis in the presence of collection libraries", In Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering., June, 2007. , pp. 31-36. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Memory analysis techniques have become sophisticated enough to model, with a high degree of accuracy, the manipulation of simple memory structures (finite structures, single/double linked lists and trees). However, modern programming languages provide extensive library support including a wide range of generic collection objects that make use of complex internal data structures. While these data structures ensure that the collections are efficient, often these representations cannot be effectively modeled by existing methods (either due to excessive analysis runtime or due to the inability to represent the required information). This paper presents a method to represent collections using an abstraction of their semantics. The construction of the abstract semantics for the collection objects is done in a manner that allows individual elements in the collections to be identified. Our construction also supports iterators over the collections and is able to model the position of the iterators with respect to the elements in the collection. By ordering the contents of the collection based on the iterator position, the model can represent a notion of progress when iteratively manipulating the contents of a collection. These features allow strong updates to the individual elements in the collection as well as strong updates over the collections themselves.10.1109/NANOARCH.2015.7180583 |
BibTeX:
@inproceedings{Marron2007,
author = {Marron, Mark and Stefanovic, Darko and Hermenegildo, Manuel and Kapur, Deepak},
title = {Heap analysis in the presence of collection libraries},
booktitle = {Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering},
publisher = {ACM},
year = {2007},
pages = {31--36},
doi = {10.1145/1251535.1251541}
}
|
| Green E, Olah MJ, Abramova T, Williams LR, Stefanovic D, Worgall T and Stojanovic MN (2006), "A Rational Approach to Minimal High-Resolution Cross-Reactive Arrays", Journal of the American Chemical Society., November, 2006. Vol. 128(47), pp. 15278-15282. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We report a rational approach to the construction of cross-reactive arrays for steroids consisting of five to seven sensors incorporating modified oligonucleotides. The sensors for our arrays were selected to maximize their differential responses to the two steroids most different in an arbitrarily chosen parameter named “shape-length”. The arrays incorporated three previously unreported types of sensors identified through a massive screening effort: (1) three-way junction sensors with neutralized charges within junction; (2) “self-aggregating sensors”; and (3) sensors incorporating fluorophore directly in a three-way junction as a spacer. The arrays were tested on seven steroids and an alkaloid (cocaine) over a range of concentrations, and achieved 92−96% accuracy in class assignments, despite the close structural similarities between steroids. |
BibTeX:
@article{Green2006,
author = {Green, Eric and Olah, Mark J. and Abramova, Tatiana and Williams, Lance R. and Stefanovic, Darko and Worgall, Tilla and Stojanovic, Milan N.},
title = {A Rational Approach to Minimal High-Resolution Cross-Reactive Arrays},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2006},
volume = {128},
number = {47},
pages = {15278--15282},
doi = {10.1021/ja0642663}
}
|
| Blackburn SM, Garner R, Hoffmann C, Khang AM, McKinley KS, Bentzur R, Diwan A, Feinberg D, Frampton D, Guyer SZ, Hirzel M, Hosking A, Jump M, Lee H, Moss JEB, Phansalkar A, Stefanović D, VanDrunen T, von Dincklage D and Wiedermann B (2006), "The DaCapo benchmarks: java benchmarking development and analysis", In Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications., October, 2006. , pp. 169-190. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Since benchmarks drive computer science research and industry product development, which ones we use and how we evaluate them are key questions for the community. Despite complex runtime tradeoffs due to dynamic compilation and garbage collection required for Java programs, many evaluations still use methodologies developed for C, C++, and Fortran. SPEC, the dominant purveyor of benchmarks, compounded this problem by institutionalizing these methodologies for their Java benchmark suite. This paper recommends benchmarking selection and evaluation methodologies, and introduces the DaCapo benchmarks, a set of open source, client-side Java benchmarks. We demonstrate that the complex interactions of (1) architecture, (2) compiler, (3) virtual machine, (4) memory management, and (5) application require more extensive evaluation than C, C++, and Fortran which stress (4) much less, and do not require (3). We use and introduce new value, time-series, and statistical metrics for static and dynamic properties such as code complexity, code size, heap composition, and pointer mutations. No benchmark suite is definitive, but these metrics show that DaCapo improves over SPEC Java in a variety of ways, including more complex code, richer object behaviors, and more demanding memory system requirements. This paper takes a step towards improving methodologies for choosing and evaluating benchmarks to foster innovation in system design and implementation for Java and other managed languages. |
BibTeX:
@inproceedings{Blackburn2006,
author = {Blackburn, Stephen M. and Garner, Robin and Hoffmann, Chris and Khang, Asjad M. and McKinley, Kathryn S. and Bentzur, Rotem and Diwan, Amer and Feinberg, Daniel and Frampton, Daniel and Guyer, Samuel Z. and Hirzel, Martin and Hosking, Antony and Jump, Maria and Lee, Han and Moss, J. Eliot B. and Phansalkar, Aashish and Stefanović, Darko and VanDrunen, Thomas and von Dincklage, Daniel and Wiedermann, Ben},
title = {The DaCapo benchmarks: java benchmarking development and analysis},
booktitle = {Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications},
publisher = {ACM},
year = {2006},
pages = {169--190},
doi = {10.1145/1167473.1167488}
}
|
| Macdonald J, Li Y, Sutovic M, Lederman H, Pendri K, Lu W, Andrews BL, Stefanovic D and Stojanovic MN (2006), "Medium Scale Integration of Molecular Logic Gates in an Automaton", Nano Letters., October, 2006. Vol. 6(11), pp. 2598-2603. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: The assembly of molecular automata that perform increasingly complex tasks, such as game playing, presents an unbiased test of molecular computation. We now report a second-generation deoxyribozyme-based automaton, MAYA-II, which plays a complete game of tic-tac-toe according to a perfect strategy. In silicon terminology, MAYA-II represents the first “medium-scale integrated molecular circuit”, integrating 128 deoxyribozyme-based logic gates, 32 input DNA molecules, and 8 two-channel fluorescent outputs across 8 wells. |
BibTeX:
@article{Macdonald2006,
author = {Macdonald, Joanne and Li, Yang and Sutovic, Marko and Lederman, Harvey and Pendri, Kiran and Lu, Wanhong and Andrews, Benjamin L. and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Medium Scale Integration of Molecular Logic Gates in an Automaton},
journal = {Nano Letters},
publisher = {American Chemical Society (ACS)},
year = {2006},
volume = {6},
number = {11},
pages = {2598--2603},
doi = {10.1021/nl0620684}
}
|
| Pei R, Taylor SK, Stefanovic D, Rudchenko S, Mitchell TE and Stojanovic MN (2006), "Behavior of Polycatalytic Assemblies in a Substrate-Displaying Matrix", Journal of the American Chemical Society., September, 2006. Vol. 128(39), pp. 12693-12699. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We describe polycatalytic assemblies, comprising one or two streptavidin molecules and two to six attached nucleic acid catalysts (deoxyribozymes), with phosphodiesterase activity. When exposed to a matrix covered at high densities with oligonucleotide substrates, these molecules diffuse through the matrix continuously cleaving the substrate at rates comparable to those of individual catalysts in solution. Rates of diffusion (movement), processivity, and resident times of assemblies can be controlled through the number of catalytic units and the length of substrate/product recognition regions. The assemblies were characterized at the ensemble level using surface plasmon resonance. |
BibTeX:
@article{Pei2006,
author = {Pei, Renjun and Taylor, Steven K. and Stefanovic, Darko and Rudchenko, Sergei and Mitchell, Tiffany E. and Stojanovic, Milan N.},
title = {Behavior of Polycatalytic Assemblies in a Substrate-Displaying Matrix},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2006},
volume = {128},
number = {39},
pages = {12693--12699},
doi = {10.1021/ja058394n}
}
|
| Hertz M, Blackburn SM, Moss JEB, McKinley KS and Stefanović D (2006), "Generating object lifetime traces with Merlin", ACM Transactions on Programming Languages and Systems., May, 2006. Vol. 28(3), pp. 476-516. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Programmers are writing a rapidly growing number of programs in object-oriented languages, such as Java and C#, that require garbage collection. Garbage collection traces and simulation speed up research by enabling deeper understandings of object lifetime behavior and quick exploration and design of new garbage collection algorithms. When generating perfect traces, the brute-force method of computing object lifetimes requires a whole-heap garbage collection at every potential collection point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, for example, every 32 KB of allocation.We extend the state of the art for simulating garbage collection algorithms in two ways. First, we develop a systematic methodology for simulation studies of copying garbage collection and present results showing the effects of trace granularity on these simulations. We show that trace granularity often distorts simulated garbage collection results compared with perfect traces. Second, we present and measure the performance of a new algorithm called Merlin for computing object lifetimes. Merlin timestamps objects and later uses the timestamps of dead objects to reconstruct when they died. The Merlin algorithm piggybacks on garbage collections performed by the base system. Experimental results show that Merlin can generate traces over two orders of magnitude faster than the brute-force method which collects after every object allocation. We also use Merlin to produce visualizations of heap behavior that expose new object lifetime behaviors. |
BibTeX:
@article{Hertz2006,
author = {Hertz, Matthew and Blackburn, Stephen M. and Moss, J. Eliot B. and McKinley, Kathryn S. and Stefanović, Darko},
title = {Generating object lifetime traces with Merlin},
journal = {ACM Transactions on Programming Languages and Systems},
publisher = {Association for Computing Machinery (ACM)},
year = {2006},
volume = {28},
number = {3},
pages = {476--516},
doi = {10.1145/1133651.1133654}
}
|
| Sager J, Young M and Stefanovic D (2006), "Characterization of Transverse Channel Concentration Profiles Obtainable with a Class of Microfluidic Networks", Langmuir., March, 2006. Vol. 22(9), pp. 4452-4455. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We analyze mathematically a previously reported class of passive microfluidic mixing networks. The networks produce nonhomogeneous concentrations in the output channel, resulting in diverse concentration prouploads. We formally prove that all profiles obtainable with this class of networks can be described as polynomials of degree no higher than the number of input channels less one. We derive explicit formulas for the calculation of resultant output concentration profiles and conversely for the calculation of input concentrations needed to obtain set output profiles. |
BibTeX:
@article{Sager2006,
author = {Sager, Jennifer and Young, Maxwell and Stefanovic, Darko},
title = {Characterization of Transverse Channel Concentration Profiles Obtainable with a Class of Microfluidic Networks},
journal = {Langmuir},
publisher = {American Chemical Society (ACS)},
year = {2006},
volume = {22},
number = {9},
pages = {4452--4455},
doi = {10.1021/la052166p}
}
|
| Lederman H, Macdonald J, Stefanovic D and Stojanovic MN (2006), "Deoxyribozyme-Based Three-Input Logic Gates and Construction of a Molecular Full Adder", Biochemistry., January, 2006. Vol. 45(4), pp. 1194-1199. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We have developed an array of seven deoxyribozyme-based molecular logic gates that behaves as a full adder in a single solution, with three oligonucleotides as inputs and two independent fluorogenic cleavage reactions as carry and sum outputs. The sum output consisted of four new deoxyribozyme-based logic gates: an ANDAND gate and three ANDNOTANDNOT gates. These gates required the design of a generic three-input deoxyribozyme-based logic gate that can use any three-way combination of activating or inactivating inputs. This generic gate design utilizes an additional inverting element that hybridizes to convert YES logic into NOT logic and vice versa. The system represents the first solution-phase, single test tube, enzymatic full adder and shows the complexity of control over molecular scale events that can be achieved with deoxyribozyme-based logic gates. Similar systems could be applied to control autonomous therapeutic and diagnostic devices.10.1098/rsif.2014.0902 |
BibTeX:
@article{Lederman2006,
author = {Lederman, Harvey and Macdonald, Joanne and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Deoxyribozyme-Based Three-Input Logic Gates and Construction of a Molecular Full Adder},
journal = {Biochemistry},
publisher = {American Chemical Society (ACS)},
year = {2006},
volume = {45},
number = {4},
pages = {1194--1199},
doi = {10.1021/bi051871u}
}
|
| Farfel J and Stefanovic D (2006), "Towards Practical Biomolecular Computers Using Microfluidic Deoxyribozyme Logic Gate Networks", In DNA Computing. , pp. 38-54. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We propose a way of implementing a biomolecular computer in the laboratory using deoxyribozyme logic gates inside a microfluidic reaction chamber. We build upon our previous work, which simulated the operation of a deoxyribozyme-based flip-flop and oscillator in a continuous stirred-tank reactor (CSTR). Unfortunately, using these logic gates in a laboratory-size CSTR is prohibitively expensive, because the reagent quantities are too large. A desire to reduce the cost of open-reactor experiments using these gates motivated our decision to design a microfluidic system. For a realistic microfluidic design, the properties of microfluidic flow and mixing have to be taken into account. We describe the differences between a macrofluidic system such as the CSTR and a microfluidic setting. Liquid in a microfluidic setting exhibits laminar flow, and is more difficult to mix than in a CSTR. We would like to use a rotary mixer, and so we examine how it operates so that we may properly model it. We discuss the details of our mixer simulation, including our diffusion model. We discuss why having discrete phases of influx/efflux (“charging”) and mixing is necessary, and how it changes the kinetics of the system. We then show the result of simulating both a flip-flop and an oscillator inside our rotary mixing chamber, and discuss the differences in results from the CSTR setting. |
BibTeX:
@inbook{Farfel2006,
author = {Farfel, Joseph and Stefanovic, Darko},
title = {Towards Practical Biomolecular Computers Using Microfluidic Deoxyribozyme Logic Gate Networks},
booktitle = {DNA Computing},
publisher = {Springer Berlin Heidelberg},
year = {2006},
pages = {38--54},
doi = {10.1007/11753681_4}
}
|
| Macdonald J, Stefanovic D and Stojanovic MN (2006), "Solution-Phase Molecular-Scale Computation With Deoxyribozyme-Based Logic Gates and Fluorescent Readouts", In Fluorescent Energy Transfer Nucleic Acid Probes. , pp. 343-364. Humana Press.
[BibTeX] [DOI]
|
BibTeX:
@inbook{Macdonald,
author = {Macdonald, Joanne and Stefanovic, Darko and Stojanovic, Milan N.},
title = {Solution-Phase Molecular-Scale Computation With Deoxyribozyme-Based Logic Gates and Fluorescent Readouts},
booktitle = {Fluorescent Energy Transfer Nucleic Acid Probes},
publisher = {Humana Press},
year = {2006},
pages = {343--364},
doi = {10.1385/1-59745-069-3:343}
}
|
| Marron M, Kapur D, Stefanovic D and Hermenegildo M (2006), "A Static Heap Analysis for Shape and Connectivity: Unified Memory Analysis: The Base Framework", In Languages and Compilers for Parallel Computing. , pp. 345-363. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Modeling the evolution of the state of program memory during program execution is critical to many parallelization techniques. Current memory analysis techniques either provide very accurate information but run prohibitively slowly or produce very conservative results. An approach based on abstract interpretation is presented for analyzing programs at compile time, which can accurately determine many important program properties such as aliasing, logical data structures and shape. These properties are known to be critical for transforming a single threaded program into a version that can be run on multiple execution units in parallel. The analysis is shown to be of polynomial complexity in the size of the memory heap. Experimental results for benchmarks in the Jolden suite are given. These results show that in practice the analysis method is efficient and is capable of accurately determining shape information in programs that create and manipulate complex data structures. |
BibTeX:
@inbook{Marron2006,
author = {Marron, Mark and Kapur, Deepak and Stefanovic, Darko and Hermenegildo, Manuel},
title = {A Static Heap Analysis for Shape and Connectivity: Unified Memory Analysis: The Base Framework},
booktitle = {Languages and Compilers for Parallel Computing},
publisher = {Springer Berlin Heidelberg},
year = {2006},
pages = {345--363},
doi = {10.1007/978-3-540-72521-3_25}
}
|
| Sager J and Stefanovic D (2006), "Designing Nucleotide Sequences for Computation: A Survey of Constraints", In DNA Computing. , pp. 275-289. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We survey the biochemical constraints useful for the design of DNA code words for DNA computation. We define the DNA/RNA Code Constraint problem and cover biochemistry topics relevant to DNA libraries. We examine which biochemical constraints are best suited for DNA word design.10.1002/9783527825424.ch15 |
BibTeX:
@inbook{Sager2006a,
author = {Sager, Jennifer and Stefanovic, Darko},
title = {Designing Nucleotide Sequences for Computation: A Survey of Constraints},
booktitle = {DNA Computing},
publisher = {Springer Berlin Heidelberg},
year = {2006},
pages = {275--289},
doi = {10.1007/11753681_22}
}
|
| Kyrylkov S and Stefanovic D (2005), "Comparison of Garbage Collectors Operating in a Large Address Space". Technical report, Department of Computer Science, University of New Mexico., April, 2005. (TR-CS-2005-11)
[Abstract] [BibTeX] [PDF]
|
| Abstract: We analyze the performance of several copying garbage collection algorithms in a large address space offered by modern architectures. In particular, we describe the design and implementation of the RealOF garbage collector, an algorithm explicitly designed to exploit the features of 64-bit environments. This collector maintains a correspondence between object age and object placement in the address space of the heap. It allocates and copies objects within designated regions of memory called zones and performs garbage collection incrementally by collecting one or more ranges of memory called windows. The windows are managed so as to collect middle-aged objects, rather than almost always collecting young objects, as with a generational collector. The address-ordered heap allows us to use the same inexpensive write barrier that works for generational collectors. We show that for server applications this algorithm improves throughput and reduces heap size requirements over the best-throughput generational copying algorithms such as the Appel-style generational collector. |
BibTeX:
@techreport{Kyrylkov2025b,
author = {Sergiy Kyrylkov and Darko Stefanovic},
title = {Comparison of Garbage Collectors Operating in a Large Address Space},
school = {Department of Computer Science, University of New Mexico},
year = {2005},
number = {TR-CS-2005-11}
}
|
| Stojanovic MN, Semova S, Kolpashchikov D, Macdonald J, Morgan C and Stefanovic D (2005), "Deoxyribozyme-Based Ligase Logic Gates and Their Initial Circuits", Journal of the American Chemical Society., April, 2005. Vol. 127(19), pp. 6914-6915. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: A complete set (YES, NOT, AND, and ANDNOT) of molecular scale logic gates based on ligase deoxyribozymes was constructed. The activity of these gates was visualized through the formation of cascades with downstream phosphodieseterase YES gates, which performed fluorogenic cleavage.10.1021/ja016756v |
BibTeX:
@article{Stojanovic2005,
author = {Stojanovic, Milan N. and Semova, Stanka and Kolpashchikov, Dmitry and Macdonald, Joanne and Morgan, Clint and Stefanovic, Darko},
title = {Deoxyribozyme-Based Ligase Logic Gates and Their Initial Circuits},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2005},
volume = {127},
number = {19},
pages = {6914--6915},
doi = {10.1021/ja043003a}
}
|
| Barrantes EG, Ackley DH, Forrest S and Stefanović D (2005), "Randomized instruction set emulation", ACM Transactions on Information and System Security., February, 2005. Vol. 8(1), pp. 3-40. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Injecting binary code into a running program is a common form of attack. Most defenses employ a “guard the doors” approach, blocking known mechanisms of code injection. Randomized instruction set emulation (RISE) is a complementary method of defense, one that performs a hidden randomization of an application's machine code. If foreign binary code is injected into a program running under RISE, it will not be executable because it will not know the proper randomization. The paper describes and analyzes RISE, describing a proof-of-concept implementation built on the open-source Valgrind IA32-to-IA32 translator. The prototype effectively disrupts binary code injection attacks, without requiring recompilation, linking, or access to application source code. Under RISE, injected code (attacks) essentially executes random code sequences. Empirical studies and a theoretical model are reported which treat the effects of executing random code on two different architectures (IA32 and PowerPC). The paper discusses possible extensions and applications of the RISE technique in other contexts. |
BibTeX:
@article{Barrantes2005,
author = {Barrantes, Elena Gabriela and Ackley, David H. and Forrest, Stephanie and Stefanović, Darko},
title = {Randomized instruction set emulation},
journal = {ACM Transactions on Information and System Security},
publisher = {Association for Computing Machinery (ACM)},
year = {2005},
volume = {8},
number = {1},
pages = {3--40},
doi = {10.1145/1053283.1053286}
}
|
| Kyrylkov S and Stefanovic D (2005), "A Study of Garbage Collection With a Large Address Space for Server Applications". Technical report, Department of Computer Science, University of New Mexico., February, 2005. (TR-CS-2005-1)
[Abstract] [BibTeX] [PDF]
|
| Abstract: We analyze the performance of several copying garbage collection algorithms in a large address space offered by modern architectures. In particular, we describe the design and implementation of the RealOF garbage collector, an algorithm explicitly designed to exploit the features of 64-bit environments. This collector maintains a correspondence between object age and object placement in the address space of the heap. It allocates and copies objects within designated regions of memory called zones and performs garbage collection incrementally by collecting one or more ranges of memory called windows. The address-ordered heap allows us to use the same inexpensive write barrier that works for traditional generational collectors. We show that for server applications this algorithm improves throughput and reduces heap size requirements over the best-throughput generational copying algorithms such as the Appel-style generational collector. |
BibTeX:
@techreport{Kyrylkov2005a,
author = {Sergiy Kyrylkov and Darko Stefanovic},
title = {A Study of Garbage Collection With a Large Address Space for Server Applications},
school = {Department of Computer Science, University of New Mexico},
year = {2005},
number = {TR-CS-2005-1}
}
|
| Morgan C, Stefanovic D, Moore C and Stojanovic MN (2005), "Building the Components for a Biomolecular Computer", In DNA Computing. , pp. 247-257. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We propose a new method for amorphous bio-compatible computing using deoxyribozyme logic gates in which oligonucleotides act as enzymes on other oligonucleotides, yielding oligonucleotide products. Moreover, these reactions can be controlled by inputs that are also oligonucleotides. We interpret these reactions as logic gates, and the concentrations of chemical species as signals. Since these reactions are homogeneous, i.e., they use oligonucleotides as both inputs and outputs, we can compose them to construct complex logic circuits. Thus, our system for chemical computation offers functionality similar to conventional electronic circuits with the potential for deployment inside of living cells. Previously, this technology was demonstrated in closed-system batch reactions, which limited its computational ability to simple feed-forward circuits. In this work, we go beyond closed systems, and show how to use thermodynamically open reactors to build biomolecular circuits with feedback. The behavior of an open chemical system is determined both by its chemical reaction network and by the influx and efflux of chemical species. This motivates a change in design process from that used with closed systems. Rather than focusing solely on the stoichiometry of the chemical reactions, we must carefully examine their kinetics. Systems of differential equations and the theory of dynamical systems become the appropriate tools for designing and analyzing such systems. Using these tools, we present an inverter. Next, by introducing feedback into the reaction network, we construct devices with a sense of state.We show how a combination of analytical approximation techniques and numerical methods allows us to tune the dynamics of these systems. We demonstrate a flip-flop which exhibits behavior similar to the RS flip-flop of electronic computation. It has two states in which the concentration of one oligonucleotide is high and the other is low or vice versa. We describe how to control the state of the flip-flop by varying the concentration of the substrates. Moreover, there are large regions of parameter space in which this behavior is robust, and we show how to tune the influx rates as a function of the chemical reaction rates in a way that ensures bistability. |
BibTeX:
@inbook{Morgan2005,
author = {Morgan, Clint and Stefanovic, Darko and Moore, Cristopher and Stojanovic, Milan N.},
title = {Building the Components for a Biomolecular Computer},
booktitle = {DNA Computing},
publisher = {Springer Berlin Heidelberg},
year = {2005},
pages = {247--257},
doi = {10.1007/11493785_22}
}
|
| Stojanovic MN, Stefanovic D, LaBean T and Yan H (2005), "Computing with Nucleic Acids" , pp. 427-455. Wiley-VCH.
[BibTeX] [DOI]
|
BibTeX:
@inbook{Stojanovic2005b,
author = {Milan N. Stojanovic and Darko Stefanovic and Thomas LaBean and Hao Yan},
editor = {Itamar Willner and Eugenii Katz},
title = {Computing with Nucleic Acids},
publisher = {Wiley-VCH},
year = {2005},
pages = {427-455},
doi = {10.1002/352760376X.ch14}
}
|
| Karlin J, Stefanovic D and Forrest S (2004), "The Triton Branch Predictor". Technical report, Department of Computer Science, University of New Mexico., October, 2004.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We describe a new branch predictor that is designed to balance multiple constraints—predicting branch biases versus predicting specific branch instance behavior. Most branch instances only require branch bias information for accurate predictions while a select few require more sophisticated prediction structures. Our predictor uses a cache mechanism to classify branches and dynamically adjust the balance of the predictor. On average, our predictor mispredicts 24% less often than YAGS and 19% less often than a global perceptron predictor with the same bit budget. |
BibTeX:
@techreport{Karlin2004,
author = {Josh Karlin and Darko Stefanovic and Stephanie Forrest},
title = {The Triton Branch Predictor},
school = {Department of Computer Science, University of New Mexico},
year = {2004}
}
|
| Barrantes EG, Ackley DH, Forrest S, Palmer TS, Stefanovic D and Zovi DD (2003), "Randomized instruction set emulation to disrupt binary code injection attacks", In Proceedings of the 10th ACM conference on Computer and communications security., October, 2003. , pp. 281-289. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Binary code injection into an executing program is a common form of attack. Most current defenses against this form of attack use a ‘guard all doors’ strategy, trying to block the avenues by which execution can be diverted. We describe a complementary method of protection, which disrupts foreign code execution regardless of how the code is injected. A unique and private machine instruction set for each executing program would make it difficult for an outsider to design binary attack code against that program and impossible to use the same binary attack code against multiple machines. As a proof of concept, we describe a randomized instruction set emulator (RISE), based on the open-source Valgrind x86-to-x86 binary translator. The prototype disrupts binary code injection attacks against a program without requiring its recompilation, linking, or access to source code. The paper describes the RISE implementation and its limitations, gives evidence demonstrating that RISE defeats common attacks, considers how the dense x86 instruction set affects the method, and discusses potential extensions of the idea. |
BibTeX:
@inproceedings{Barrantes2003,
author = {Barrantes, Elena Gabriela and Ackley, David H. and Forrest, Stephanie and Palmer, Trek S. and Stefanovic, Darko and Zovi, Dino Dai},
title = {Randomized instruction set emulation to disrupt binary code injection attacks},
booktitle = {Proceedings of the 10th ACM conference on Computer and communications security},
publisher = {ACM},
year = {2003},
pages = {281--289},
doi = {10.1145/948109.948147}
}
|
| Stojanovic MN and Stefanovic D (2003), "A deoxyribozyme-based molecular automaton", Nature Biotechnology., August, 2003. Vol. 21(9), pp. 1069-1074. Springer Science and Business Media LLC.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We describe a molecular automaton, called MAYA, which encodes a version of the game of tic-tac-toe and interactively competes against a human opponent. The automaton is a Boolean network of deoxyribozymes that incorporates 23 molecular-scale logic gates and one constitutively active deoxyribozyme arrayed in nine wells (3×3) corresponding to the game board. To make a move, MAYA carries out an analysis of the input oligonucleotide keyed to a particular move by the human opponent and indicates a move by fluorescence signaling in a response well. The cycle of human player input and automaton response continues until there is a draw or a victory for the automaton. The automaton cannot be defeated because it implements a perfect strategy. |
BibTeX:
@article{Stojanovic2003,
author = {Stojanovic, Milan N and Stefanovic, Darko},
title = {A deoxyribozyme-based molecular automaton},
journal = {Nature Biotechnology},
publisher = {Springer Science and Business Media LLC},
year = {2003},
volume = {21},
number = {9},
pages = {1069--1074},
doi = {10.1038/nbt862}
}
|
| Stojanović MN and Stefanović D (2003), "Deoxyribozyme-Based Half-Adder", Journal of the American Chemical Society., May, 2003. Vol. 125(22), pp. 6673-6676. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We have constructed a solution-phase array of three deoxyribozyme-based logic gates that behaves as a half-adder. Two deoxyribozymes mimic i1ANDNOTi2 and i2ANDNOTi1 gates that cleave a fluorogenic substrate, reporting through an increase in fluorescence emission at 570 nm. The third deoxyribozyme mimics an i1ANDi2 gate and cleaves the other fluorogenic substrate, reporting through an increase in fluorescence emission at 520 nm. Together, this system represents the first example of a decision-making enzymatic network with two inputs and two outputs. Similar systems could be applied to control autonomous therapeutic and diagnostic devices. |
BibTeX:
@article{Stojanovic2003a,
author = {Stojanović, Milan N. and Stefanović, Darko},
title = {Deoxyribozyme-Based Half-Adder},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2003},
volume = {125},
number = {22},
pages = {6673--6676},
doi = {10.1021/ja0296632}
}
|
| Cochran J, Kapur D and Stefanovic D (2003), "Model Checking Reconfigurable Processor Configurations for Safety Properties", In Field Programmable Logic and Application. , pp. 996-999. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Reconfigurable processors pose unique problems for program safety because of their use of computational approaches that are difficult to integrate into traditional program analyses. The combination of proof-carrying code for verification of standard processor machine code and model-checking for array configurations is explored. This combination extends proof-carrying code to provide a context for model checking, but uses standard model checking technology. This approach is shown to be useful in verifying safety properties including the synchronization of memory access by the reconfigurable array and memory access bounds checking. |
BibTeX:
@inbook{Cochran2003,
author = {Cochran, John and Kapur, Deepak and Stefanovic, Darko},
title = {Model Checking Reconfigurable Processor Configurations for Safety Properties},
booktitle = {Field Programmable Logic and Application},
publisher = {Springer Berlin Heidelberg},
year = {2003},
pages = {996--999},
doi = {10.1007/978-3-540-45234-8_104}
}
|
| Stojanovic MN, Nikic DB and Stefanovic D (2003), "Implicit-OR tiling of Deoxyribozymes: Construction of Molecular Scale OR, NAND, and Four-Input Logic Gates", Journal of the Serbian Chemical Society. Vol. 68(4-5), pp. 321-326.
[Abstract] [BibTeX]
|
| Abstract: We recently reported the first complete set of molecular-scale logic gates based on deoxyribozymes. Here we report how we tile these logic gates and construct new logic elements: OR, NAND, and the first element with four inputs (i1 AND i5) OR (i2 AND i6). Tiling of logic gates was achieved through a common substrate used for core deoxyribozyme; degradation of this substrate defines the output. This kind of connection between logic gates is an implicit-OR tiling, because it suffices that one componenet of the network is active for thewhole network to give an output of 1. |
BibTeX:
@article{Stojanovic2003b,
author = {Milan N. Stojanovic and Dragan B. Nikic and Darko Stefanovic},
title = {Implicit-OR tiling of Deoxyribozymes: Construction of Molecular Scale OR, NAND, and Four-Input Logic Gates},
journal = {Journal of the Serbian Chemical Society},
year = {2003},
volume = {68},
number = {4-5},
pages = {321-326}
}
|
| Hertz M, Blackburn SM, Moss JEB, McKinley KS and Stefanović D (2002), "Error-free garbage collection traces: how to cheat and not get caught", In Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems., June, 2002. , pp. 140-151. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Programmers are writing a large and rapidly growing number of programs in object-oriented languages such as Java that require garbage collection (GC). To explore the design and evaluation of GC algorithms quickly, researchers are using simulation based on traces of object allocation and lifetime behavior. The brute force method generates perfect traces using a whole-heap GC at every potential GC point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, e.g., every 32K bytes of allocation. We extend the state of the art for simulating GC algorithms in two ways. First, we present a systematic methodology and results on the effects of trace granularity for a variety of copying GC algorithms. We show that trace granularity often distorts GC performance results compared with perfect traces, and that some GC algorithms are more sensitive to this effect than others. Second, we introduce and measure the performance of a new precise algorithm for generating GC traces which is over 800 times faster than the brute force method. Our algorithm, called Merlin, frequently timestamps objects and later uses the timestamps of dead objects to reconstruct precisely when they died. It performs only periodic garbage collections and achieves high accuracy at low cost, eliminating any reason to use granulated traces. |
BibTeX:
@inproceedings{Hertz2002,
author = {Hertz, Matthew and Blackburn, Stephen M and Moss, J Eliot B and McKinley, Kathryn S. and Stefanović, Darko},
title = {Error-free garbage collection traces: how to cheat and not get caught},
booktitle = {Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems},
publisher = {ACM},
year = {2002},
pages = {140--151},
doi = {10.1145/511334.511352}
}
|
| Stefanović D, Hertz M, Blackburn SM, McKinley KS and Moss JEB (2002), "Older-first garbage collection in practice: evaluation in a Java Virtual Machine", ACM SIGPLAN Notices., June, 2002. Vol. 38(2 supplement), pp. 25-36. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Until recently, the best performing copying garbage collectors used a generational policy which repeatedly collects the very youngest objects, copies any survivors to an older space, and then infrequently collects the older space. A previous study that used garbage collection simulation pointed to potential improvements by using an Older-First copying garbage collection algorithm. The Older-First algorithm sweeps a fixed-sized window through the heap from older to younger objects, and avoids copying the very youngest objects which have not yet had sufficient time to die. We describe and examine here an implementation of the Older-First algorithm in theJikes RVM for Java. This investigation shows that Older-First can perform as well as the simulation results suggested, and greatly improves total program performance when compared to using a fixed-size nursery generational collector. We further compare Older-First to a flexible-size nursery generational collector in which the nursery occupies all of the heap that does not contain older objects. In these comparisons, the flexible-nursery collector is occasionally the better of the two, but on average the Older-First collector performs the best. |
BibTeX:
@article{Stefanovic2002,
author = {Stefanović, Darko and Hertz, Matthew and Blackburn, Stephen M. and McKinley, Kathryn S. and Moss, J. Eliot B.},
title = {Older-first garbage collection in practice: evaluation in a Java Virtual Machine},
journal = {ACM SIGPLAN Notices},
publisher = {Association for Computing Machinery (ACM)},
year = {2002},
volume = {38},
number = {2 supplement},
pages = {25--36},
doi = {10.1145/773039.773042}
}
|
| Stojanovic MN, Mitchell TE and Stefanovic D (2002), "Deoxyribozyme-Based Logic Gates", Journal of the American Chemical Society., March, 2002. Vol. 124(14), pp. 3555-3561. American Chemical Society (ACS).
[Abstract] [BibTeX] [DOI]
|
| Abstract: We report herein a set of deoxyribozyme-based logic gates capable of generating any Boolean function. We construct basic NOT and AND gates, followed by the more complex XOR gate. These gates were constructed through a modular design that combines molecular beacon stem-loops with hammerhead-type deoxyribozymes. Importantly, as the gates have oligonucleotides as both inputs and output, they open the possibility of communication between various computation elements in solution. The operation of these gates is conveniently connected to a fluorescent readout. |
BibTeX:
@article{Stojanovic2002,
author = {Stojanovic, Milan N. and Mitchell, Tiffany Elizabeth and Stefanovic, Darko},
title = {Deoxyribozyme-Based Logic Gates},
journal = {Journal of the American Chemical Society},
publisher = {American Chemical Society (ACS)},
year = {2002},
volume = {124},
number = {14},
pages = {3555--3561},
doi = {10.1021/ja016756v}
}
|
| Palmer T, Zovi DD and Stefanovic D (2001), "SIND: A Framework for Binary Translation". Technical report, Department of Computer Science, University of New Mexico., December, 2001. (TR-CS-2001-38)
[Abstract] [BibTeX] [PDF]
|
| Abstract: Recent work with dynamic optimization in platform independent, virtual machine based languages such as Java has sparked interest in the possibility of applying similar techniques to arbitrary compiled binary programs. Systems such as Dynamo, DAISY, and FX!32 exploit dynamic optimization techniques to improve performance of native or foreign architecture binaries. However, research in this area is complicated by the lack of openly licensed, freely available, and platform-independent experimental frameworks. SIND aims to fill this void by providing a easily-extensible and flexible framework for research and development of applications and techniques of binary translation. Current research focuses are dynamic optimization of running binaries and dynamic security augmentation and integrity assurance. |
BibTeX:
@techreport{Palmer2001,
author = {Trek Palmer and Dino Dai Zovi and Darko Stefanovic},
title = {SIND: A Framework for Binary Translation},
school = {Department of Computer Science, University of New Mexico},
year = {2001},
number = {TR-CS-2001-38}
}
|
| Stefanović D, McKinley KS and Moss JEB (2000), "On models for object lifetime distributions", ACM SIGPLAN Notices., October, 2000. Vol. 36(1), pp. 137-142. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Analytical models of object lifetimes are appealing because they would enable mathematical analysis or fast simulation of the memory management behavior of programs. In this paper, we investigate models for object-oriented programs such as Java and Smalltalk. We present analytical models and compare them with observed lifetimes for 58 Smalltalk and Java programs. We find that observed lifetime distributions do not match previously proposed object lifetime models, but do agree in salient shape characteristics with the gamma distribution family used in statistical survival analysis for general populations. |
BibTeX:
@article{Stefanovic2000b,
author = {Stefanović, Darko and McKinley, Kathryn S. and Moss, J. Eliot B.},
title = {On models for object lifetime distributions},
journal = {ACM SIGPLAN Notices},
publisher = {Association for Computing Machinery (ACM)},
year = {2000},
volume = {36},
number = {1},
pages = {137--142},
doi = {10.1145/362426.362477}
}
|
| Stefanović D and Martonosi M (2000), "On Availability of Bit-Narrow Operations in General-Purpose Applications", In Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing. , pp. 412-421. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Program instructions that consume and produce small operands can be executed in hardware circuitry of less than full size. We compare different proposed models of accounting for the usefulness of bit-positions in operands, using a run-time profiling tool, both to observe and summarize operand values, and to reconstruct and analyze the program’s data-flow graph to discover useless bits. We find that under aggressive models, the average number of useful bits per integer operand is as low as 10, not only in kernels but also in general-purpose applications from SPEC95. |
BibTeX:
@inbook{Stefanovic2000a,
author = {Stefanović, Darko and Martonosi, Margaret},
title = {On Availability of Bit-Narrow Operations in General-Purpose Applications},
booktitle = {Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing},
publisher = {Springer Berlin Heidelberg},
year = {2000},
pages = {412--421},
doi = {10.1007/3-540-44614-1_44}
}
|
| Stefanović D and Martonosi M (2000), "Limits and Graph Structure of Available Instruction-Level Parallelism", In Euro-Par 2000 Parallel Processing. , pp. 1018-1022. Springer Berlin Heidelberg.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We reexamine the limits of parallelism available in programs, using runtime reconstruction of program data-flow graphs. While limits of parallelism have been examined in the context of superscalar and VLIW machines, we also wish to study the causes of observed parallelism by examining the structure of the reconstructed data-flow graph. One aspect of structure analysis that we focus on is the isolation of instructions involved only in address calculations. We examine how address calculations present in RISC instruction streams generated by optimizing compilers affect the shape of the data-flow graph and often significantly reduce available parallelism. |
BibTeX:
@inbook{Stefanovic2000,
author = {Stefanović, Darko and Martonosi, Margaret},
title = {Limits and Graph Structure of Available Instruction-Level Parallelism},
booktitle = {Euro-Par 2000 Parallel Processing},
publisher = {Springer Berlin Heidelberg},
year = {2000},
pages = {1018--1022},
doi = {10.1007/3-540-44520-x_144}
}
|
| Stefanović D, McKinley KS and Moss JEB (1999), "Age-based garbage collection", In Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications., October, 1999. , pp. 370-381. ACM.
[Abstract] [BibTeX] [DOI]
|
| Abstract: Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, called age-based, some of which postpone consideration of the youngest objects. Collecting less than the whole heap requires write barrier mechanisms to track pointers into the collected region. We describe here a new, efficient write barrier implementation that works for age-based and traditional generational collectors. To compare several collectors, their configurations, and program behavior, we use an accurate simulator thatmodels all heap objects and the pointers among them, but does not model cache or other memory effects. For object-oriented languages, our results demonstrate that an older-first collector, which collects older objects before the youngest ones, copies on average much less data than generational collectors. Our results also show that an older-first collector does track more pointers, but the combined cost of copying and pointer tracking still favors an older-first over a generational collector in many cases. More importantly, we reopen for consideration the question where in the heap and with which policies copying collectors will achieve their best performance. |
BibTeX:
@inproceedings{Stefanovic1999,
author = {Stefanović, Darko and McKinley, Kathryn S. and Moss, J. Eliot B.},
title = {Age-based garbage collection},
booktitle = {Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications},
publisher = {ACM},
year = {1999},
pages = {370--381},
doi = {10.1145/320384.320425}
}
|
| Stefanovic D (1999), "Properties of Age-Based Automatic Memory Reclamation Algorithms". PhD thesis, University of Massachusetts., February, 1999.
[Abstract] [BibTeX] [PDF]
|
| Abstract: Dynamic memory management enables a programmer to allocate objects for arbitrary preiods of time. It is an important feature of modern programming languages, and is fundamental to object-oriented languages. Automatic reclamation, also known as garbage collection, automates the detection of the time when a data item can no longer be used. The work described herein considers garbage collection algorithms that base their decisions solely upon the relative age of data. This age-based class of algorithms generalizes previously defined generational garbage collection algorithms and includes promising new algorithms. The work identifies relevant performance factors and reports them for a set of object-oriented benchmark programs, establishing a fair comparison by imposing uniform maximum space constraints. A precise tracing and garbage collection algorithm evaluation framework provides accurate results and thus meaningful comparisons. The results indicate, contrary to assumptions in the literature, that the new algorithms copy less data than the generational algorithms, even though they retain a higher percentage of reclaimable data. In agreement with the assumptions in the literature, the results indicate that generational algorithms do less pointer-tracking work. Thus, given suitable relative costs of copying and pointer-tracking, the new algorithms perform better. Estimations of the relative costs for a typical modern processor suggest that the new algorithms are usually superior. |
BibTeX:
@phdthesis{Stefanovic1999a,
author = {Darko Stefanovic},
title = {Properties of Age-Based Automatic Memory Reclamation Algorithms},
school = {University of Massachusetts},
year = {1999}
}
|
| Stefanovic D, Moss JEB and McKinley KS (1998), "Oldest-First Garbage Collection". Technical report, Department of Computer Science, University of Massachusetts., April, 1998. (98-81)
[Abstract] [BibTeX]
|
| Abstract: An oldest-first generational garbage collector leaves intact the most recently allocated object space, and instead collects the remaining, older objects. Because these older objects have had more time to die, an oldest-first copying collector will generally do less copying than a traditional generational collector (which operates youngest-first), a non-generational collector, and even Clinger and Hansen’s non-predictive collector (which does wait a little while for objects to die). To explore the performance of oldest-first collection, we present a mathematical analysis, simulation results for a variety of mature object lifetime distributions, and simulation results for mature object lifetimes drawn from real programs and for real mature object traces. These results demonstrate that oldest-first collection does perform significantly better than youngest-first or non-generational collection for mature objects. Although some previous work pointed in this direction, it provided very little evidence of our conclusion. We also find that oldest-first collection works well for lifetime distributions that satisfy the generational hypothesis, which suggests we should also consider oldest-first collection in the young object space. |
BibTeX:
@techreport{Stefanovic1998,
author = {Darko Stefanovic and J. Eliot B. Moss and Kathryn. S. McKinley},
title = {Oldest-First Garbage Collection},
school = {Department of Computer Science, University of Massachusetts},
year = {1998},
number = {98-81}
}
|
| Stefanovic D (1997), "The character of the instruction scheduling problem". Technical report, Department of Computer Science, University of Massachusetts., March, 1997.
[Abstract] [BibTeX] [PDF]
|
| Abstract: Here I present some measurements that serve to characterize the nature of the problem of basic block instruction scheduling, as it is encountered in practice. Finding optimal schedules is known to be NP-hard [Hennessy and Gross, 1983]; but it is worth knowing how hard the task is in an average sense, where the average is with respect to an input space of problems (basic blocks) found in the everyday practice of compiling. The space I consider is the set of all basic blocks in all of SPEC95 benchmarks, produced by compiling on the Digital Alpha architecture [Bhandarkar, 1996]. It is also worth knowing how close a heuristic scheduler comes to the optimum, especially when one wants to design a new heuristic scheduler; I present one such evaluation for a scheduler made available by Digital and show that it is almost optimal (with respect to its own cost measure). |
BibTeX:
@techreport{Stefanovic1997,
author = {Darko Stefanovic},
title = {The character of the instruction scheduling problem},
school = {Department of Computer Science, University of Massachusetts},
year = {1997}
}
|
| Moss JEB, Utgoff P, Cavazos J, Precup D, Stefanovic D, Brodley C and Scheeff D (1997), "Learning to Schedule Straight-Line Code", In Neural Information Processing Systems - Natural and Synthetic.
[Abstract] [BibTeX] [URL]
|
| Abstract: Program execution speed on modern computers is sensitive, by a factor of two or more, to the order in which instructions are presented to the processor. To realize potential execution efficiency, an optimizing compiler must employ a heuristic algorithm for instruction scheduling. Such algorithms are painstakingly hand-crafted, which is expensive and time-consuming. We show how to cast the instruction scheduling problem as a learning task, obtaining the heuristic scheduling algorithm automatically. Our focus is the narrower problem of scheduling straight-line code (also called basic blocks of instructions). Our empirical results show that just a few features are adequate for quite good performance at this task for a real modern processor, and that any of several supervised learning methods perform nearly optimally with respect to the features used. |
BibTeX:
@inproceedings{Moss1997,
author = {J. Eliot B. Moss and Paul Utgoff and John Cavazos and Doina Precup and Darko Stefanovic and Carla Brodley and David Scheeff},
title = {Learning to Schedule Straight-Line Code},
booktitle = {Neural Information Processing Systems - Natural and Synthetic},
year = {1997},
url = {https://papers.nips.cc/paper/1349-learning-to-schedule-straight-line-code}
}
|
| Stefanovic D and Moss JEB (1994), "Characterization of object behaviour in Standard ML of New Jersey", In Proceedings of the 1994 ACM conference on LISP and functional programming - LFP ’94. , pp. 43-54. ACM Press.
[Abstract] [BibTeX] [DOI]
|
| Abstract: We describe a method of measuring lifetime characteristics of heap objects, and discuss ways in which such quantitative object behaviour measurements can help improve language implementations, especially garbage collection performance. For Standard ML of New Jersey, we find that certain primary aspects of object behaviour are qualitatively the same across benchmark programs, in particular the rapid object decay. We show that the heap-only allocation implementation model is the cause of this similarity. We confirm the weak generational hypothesis for SML/NJ and discuss garbage collector configuration tuning. Our approach is to obtain object statistics directly from program execution, rather than simulation, for reasons of simplicity and speed. Towards this end, we exploit the flexibility of the garbage collector toolkit as a measurement tool. Careful numerical analysis of the acquired data is necessary to arrive at relevant object lifetime measures. This study fills a gap in quantitative knowledge of the workings of heap-based compilers and their run-time systems, and should be useful to functional language implementors. |
BibTeX:
@inproceedings{Stefanovic1994,
author = {Stefanovic, Darko and Moss, J. Eliot B.},
title = {Characterization of object behaviour in Standard ML of New Jersey},
booktitle = {Proceedings of the 1994 ACM conference on LISP and functional programming - LFP ’94},
publisher = {ACM Press},
year = {1994},
pages = {43--54},
doi = {10.1145/182409.182428}
}
|
| Stefanovic D (1993), "Generational copying garbage collection for Standard ML: a quantitative study". MS thesis, University of Massachusetts., December, 1993.
[BibTeX] [PDF]
|
BibTeX:
@mastersthesis{Stefanovic1993,
author = {Darko Stefanovic},
title = {Generational copying garbage collection for Standard ML: a quantitative study},
school = {University of Massachusetts},
year = {1993}
}
|
| Stefanovic D (1993), "The Garbage Collection Toolkit as an Experimentation Tool", In Object-Oriented Programming Systems, Languages, and Applications: Workshop on Memory Management and Garbage Collection., September, 1993.
[BibTeX] [PDF]
|
BibTeX:
@inproceedings{Stefanovic1993a,
author = {Darko Stefanovic},
title = {The Garbage Collection Toolkit as an Experimentation Tool},
booktitle = {Object-Oriented Programming Systems, Languages, and Applications: Workshop on Memory Management and Garbage Collection},
year = {1993}
}
|
| Hosking AL, Moss JEB and Stefanovic D (1992), "A comparative performance evaluation of write barrier implementation", ACM SIGPLAN Notices., October, 1992. Vol. 27(10), pp. 92-109. Association for Computing Machinery (ACM).
[Abstract] [BibTeX] [DOI]
|
| Abstract: Generational garbage collectors are able to achieve very small pause times by concentrating on the youngest (most recently allocated) objects when collecting, since objects have been observed to die young in many systems. Generational collectors must keep track of all pointers from older to younger generations, by “monitoring” all stores into the heap. This write barrier has been implemented in a number of ways, varying essentially in the granularity of the information observed and stored. Here we examine a range of write barrier implementations and evaluate their relative performance within a generation scavenging garbage collector for Smalltalk. |
BibTeX:
@article{Hosking1992,
author = {Hosking, Antony L. and Moss, J. Eliot B. and Stefanovic, Darko},
title = {A comparative performance evaluation of write barrier implementation},
journal = {ACM SIGPLAN Notices},
publisher = {Association for Computing Machinery (ACM)},
year = {1992},
volume = {27},
number = {10},
pages = {92--109},
doi = {10.1145/141937.141946}
}
|