This uses a sub-string search, so that "graph" matches both "graph" and "graphical".
This search only searches by keyword. If you'd like, you can also search by researcher.
Found 6 results.
Listing from newest to oldest
TR-CS-2005-41
Games, Strategies, and Boolean Formula Manipulation
Ben Andrews
Biomolecular automata based on chemical logic gates can play two-player games of perfect information provided that a legal strategy for the game can be expressed in terms of Boolean formulas. To facilitate the construction of such automata, we developed a formal procedure for the analysis of game strategies, their translation into Boolean formulas, and the manipulation of the resultant formulas into canonical forms determined by the available logic primitives. As a case study in the application of this procedure, we generated strategies for the first player in the game of tic-tac-toe that, by construction, are favorable (do not admit a loss), and we found that many can be translated into Boolean formulas. Moreover, the resultant formulas can be expressed in logic with a fan-in of five, but, apparently, not in simpler logic. Additionally, we studied the combinatorics of strategies and, for the first player in the game of tic-tac-toe, we computed the number of all strategies, about 1.423e124, and the number of favorable strategies, about 2.648e103.
TR-CS-2005-07
Towards practical biomolecular computers using microfluidic deoxyribozyme logic gate networks
Joseph Farfel and Darko Stefanovic
We propose a new 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 too expensive because the reagent volume is too large. 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 the microfluidic setting. Liquid in a microfluidic setting exhibits laminar flow, and is more difficult to mix than in the CSTR. We use a rotary mixer, and 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 simulation.
TR-CS-2004-33
Building the components for a biomolecular computer
Clint Morgan, Darko Stefanovic, Cristopher Moore and Milan N. Stojanovic
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.
TR-CS-2001-30
Improved bounding and searching for phylogeny reconstruction from
gene-order data
Bernard M.E. Moret and Jijun Tang
A phylogeny is the evolutionary history of a group of organisms; systematists (and other biologists) attempt to reconstruct this history from various forms of data about contemporary organisms. Phylogeny reconstruction is a crucial step in the understanding of evolution as well as an important tool in biological, pharmaceutical, and medical research. Phylogeny reconstruction from molecular data is very difficult: almost all optimization models give rise to NP-hard (and thus computationally intractable) problems. Yet approximations must be of very high quality in order to avoid outright biological nonsense. Thus many biologists have been willing to run farms of processors for many months in order to analyze just one dataset.
Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet very few techniques are available for such phylogenetic reconstructions---and all involved NP-hard optimization problems. One method is breakpoint analysis, developed by Blanchette and Sankoff for solving the "breakpoint phylogeny." We had reimplemented their approach to produce the GRAPPA software suite, which ran three orders of magnitude faster thanks to the application of algorithm engineering techniques and, in its parallel version, demonstrated a one-million-fold speedup on a dataset of flowering plants.
We report here on improvements to the bounding and searching techniques used in GRAPPA that have brought on an additional speedup by another two orders of magnitude. Such speedups, while modest from a theoretical standpoint (the exponential behavior is simply pushed back to slightly larger instance sizes), nevertheless have important practical consequences, as they allow research biologists to analyze in a few hours or days data that could not have been analyzed at all just one year ago. Our searching method is of independent interest, as it is applicable to any optimization problem of modest size where lower bounds are expected to be tight.
TR-CS-2001-10
Industrial Applications of High-Performance Computing for
Phylogeny Reconstruction
David A. Bader, Bernard M.E. Moret, and Lisa Vawter
Phylogenies (that is, tree-of-life relationships) derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Real-world interest is strong in determining these relationships. For example, pharmaceutical companies may use phylogeny reconstruction in drug discovery for finding plants with similar gene production. Health organizations study the evolution and spread of viruses such as HIV to gain understanding of future outbreaks. And governments are interested in aiding the production of foodstuffs like rice, wheat, and corn, by understanding the genetic code. Yet very few techniques are available for such phylogenetic reconstructions. Appropriate tools for analyzing such data may help resolve some difficult phylogenetic reconstruction problems; indeed, this new source of data has been embraced by many biologists in their phylogenetic work.
With the rapid accumulation of whole genome sequences for a wide diversity of taxa, phylogenetic reconstruction based on changes in gene order and gene content is showing promise, particularly for resolving deep (i.e., old) branches. However, reconstruction from gene-order data is even more computationally intensive than reconstruction from sequence data, particularly in groups with large numbers of genes and highly rearranged genomes. We have developed a software suite, GRAPPA, that extends the breakpoint analysis (BPAnalysis) method of Sankoff and Blanchette while running much faster: in a recent analysis of a collection of chloroplast data for species of Campanulaceae on a 512-processor Linux supercluster with Myrinet, we achieved a one-million-fold speedup over BPAnalysis. GRAPPA currently can use either breakpoint or inversion distance (computed exactly) for its computation and runs on single-processor machines as well as parallel and high-performance computers.
TR-CS-2000-31
Phylogenies from Gene Order Data: A Detailed Study of Breakpoint Analysis
Bernard M.E. Moret, Stacia Wyman, David A. Bader, Tandy Warnow, and Mi Yan
Gene order data and phylogenies derived from them may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet there are very few techniques available for such phylogenetic reconstructions. One method is \emph{breakpoint analysis}, developed by Blanchette and Sankoff \cite{BBS} for reconstructing the ``breakpoint phylogeny.'' Our earlier studies \cite{ismb2000,dcaf} confirmed the usefulness of the breakpoint phylogeny approach, but also found that {\tt BPAnalysis}, the implementation of breakpoint analysis developed by Blanchette and Sankoff, was too slow to use on all but very small datasets. In this paper, we report on a new implementation of breakpoint analysis. Our faster (by two orders of magnitude) and flexible implementation allowed us to conduct studies on the characteristics of breakpoint analysis, in terms of running time, quality, and robustness, as well as to analyze datasets that had been considered out of reach of such approaches until now. We report on these findings and also discuss future steps that our new implementation will enable us to take.
News & Events | People | Academics | Research | Jobs | Companies | Visitors | Computer Facilities | Home
