2 resultados para Region growing algorithms
em CaltechTHESIS
Resumo:
Computer science and electrical engineering have been the great success story of the twentieth century. The neat modularity and mapping of a language onto circuits has led to robots on Mars, desktop computers and smartphones. But these devices are not yet able to do some of the things that life takes for granted: repair a scratch, reproduce, regenerate, or grow exponentially fast–all while remaining functional.
This thesis explores and develops algorithms, molecular implementations, and theoretical proofs in the context of “active self-assembly” of molecular systems. The long-term vision of active self-assembly is the theoretical and physical implementation of materials that are composed of reconfigurable units with the programmability and adaptability of biology’s numerous molecular machines. En route to this goal, we must first find a way to overcome the memory limitations of molecular systems, and to discover the limits of complexity that can be achieved with individual molecules.
One of the main thrusts in molecular programming is to use computer science as a tool for figuring out what can be achieved. While molecular systems that are Turing-complete have been demonstrated [Winfree, 1996], these systems still cannot achieve some of the feats biology has achieved.
One might think that because a system is Turing-complete, capable of computing “anything,” that it can do any arbitrary task. But while it can simulate any digital computational problem, there are many behaviors that are not “computations” in a classical sense, and cannot be directly implemented. Examples include exponential growth and molecular motion relative to a surface.
Passive self-assembly systems cannot implement these behaviors because (a) molecular motion relative to a surface requires a source of fuel that is external to the system, and (b) passive systems are too slow to assemble exponentially-fast-growing structures. We call these behaviors “energetically incomplete” programmable behaviors. This class of behaviors includes any behavior where a passive physical system simply does not have enough physical energy to perform the specified tasks in the requisite amount of time.
As we will demonstrate and prove, a sufficiently expressive implementation of an “active” molecular self-assembly approach can achieve these behaviors. Using an external source of fuel solves part of the the problem, so the system is not “energetically incomplete.” But the programmable system also needs to have sufficient expressive power to achieve the specified behaviors. Perhaps surprisingly, some of these systems do not even require Turing completeness to be sufficiently expressive.
Building on a large variety of work by other scientists in the fields of DNA nanotechnology, chemistry and reconfigurable robotics, this thesis introduces several research contributions in the context of active self-assembly.
We show that simple primitives such as insertion and deletion are able to generate complex and interesting results such as the growth of a linear polymer in logarithmic time and the ability of a linear polymer to treadmill. To this end we developed a formal model for active-self assembly that is directly implementable with DNA molecules. We show that this model is computationally equivalent to a machine capable of producing strings that are stronger than regular languages and, at most, as strong as context-free grammars. This is a great advance in the theory of active self- assembly as prior models were either entirely theoretical or only implementable in the context of macro-scale robotics.
We developed a chain reaction method for the autonomous exponential growth of a linear DNA polymer. Our method is based on the insertion of molecules into the assembly, which generates two new insertion sites for every initial one employed. The building of a line in logarithmic time is a first step toward building a shape in logarithmic time. We demonstrate the first construction of a synthetic linear polymer that grows exponentially fast via insertion. We show that monomer molecules are converted into the polymer in logarithmic time via spectrofluorimetry and gel electrophoresis experiments. We also demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism. This shows the growth of a population of polymers in logarithmic time. We characterize the DNA insertion mechanism that we utilize in Chapter 4. We experimentally demonstrate that we can control the kinetics of this re- action over at least seven orders of magnitude, by programming the sequences of DNA that initiate the reaction.
In addition, we review co-authored work on programming molecular robots using prescriptive landscapes of DNA origami; this was the first microscopic demonstration of programming a molec- ular robot to walk on a 2-dimensional surface. We developed a snapshot method for imaging these random walking molecular robots and a CAPTCHA-like analysis method for difficult-to-interpret imaging data.
Resumo:
A composite stock of alkaline gabbro and syenite is intrusive into limestone of the Del Carmen, Sue Peake and Santa Elena Formations at the northwest end of the Christmas Mountains. There is abundant evidence of solution of wallrock by magma but nowhere are gabbro and limestone in direct contact. The sequence of lithologies developed across the intrusive contact and across xenoliths is gabbro, pyroxenite, calc-silicate skarn, marble. Pyroxenite is made up of euhedral crystals of titanaugite and sphene in a leucocratic matrix of nepheline, Wollastonite and alkali feldspar. The uneven modal distribution of phases in pyroxenite and the occurrence' of nepheline syenite dikes, intrusive into pyroxenite and skarn, suggest that pyroxenite represents an accumulation of clinopyroxene "cemented" together by late-solidifying residual magma of nepheline syenite composition. Assimilation of limestone by gabbroic magma involves reactions between calcite and magma and/or crystals in equilibrium with magma and crystallization of phases in which the magma is saturated, to supply energy for the solution reaction. Gabbroic magma was saturated with plagioclase and clinopyroxene at the time of emplacement. The textural and mineralogic features of pyroxenite can be produced by the reaction 2( 1-X) CALCITE + ANXABl-X = (1-X) NEPHELINE+ 2(1-X) WOLLASTONITE+ X ANORTHITE+ 2(1-X) CO2. Plagioclase in pyroxenite has corroded margins and is rimmed by nepheline, suggestive of resorption by magma. Anorthite and wollastonite enter solid solution in titanaugite. For each mole of calcite dissolved, approximately one mole of clinopyroxene was crystallized. Thus the amount of limestone that may be assimilated is limited by the concentration of potential clinopyroxene in the magma. Wollastonite appears as a phase when magma has been depleted in iron and magnesium by crystallization of titanaugite. The predominance of mafic and ultramafic compositions among contaminated rocks and their restriction to a narrow zone along the intrusive contact provides little evidence for the generation of a significant volume of desilicated magma as a result of limestone assimilation.
Within 60 m of the intrusive contact with the gabbro, nodular chert in the Santa Elena Limestone reacted with the enveloping marble to form spherical nodules of high-temperature calc-silicate minerals. The phases wollastonite, rankinite, spurrite, tilleyite and calcite, form a series of sharply-bounded, concentric monomineralic and two-phase shells which record a step-wise decrease in silica content from the core of a nodule to its rim. Mineral zones in the nodules vary 'with distance from the gabbro as follows:
0-5 m CALCITE + SPURRITE + RANKINITE + WOLLASTONITE
5-16 m CALCITE + TILLEYITE ± SPURRITE + RANKINITE + WOLLASTONITE
16-31 m CALCITE + TILLEYITE + WOLLASTONITE
31-60 m CALCITE + WOLLASTONITE
60-plus CALCITE + QUARTZ
The mineral of a one-phase zone is compatible with the phases bounding it on either side but these phases are incompatible in the same volume of P-T-XCO2.
Growth of a monomineralio zone is initiated by reaction between minerals of adjacent one-phase zones which become unstable with rising temperature to form a thin layer of a new single phase that separates the reactants and is compatible with both of them. Because the mineral of the new zone is in equilibrium with the phases at both of its contacts, gradients in the chemical potentials of the exchangeable components are established across it. Although zone boundaries mark discontinuities in the gradients of bulk composition, two-phase equilibria at the contacts demonstrate that the chemical potentials are continuous. Hence, Ca, Si and CO2 were redistributed in the growing nodule by diffusion. A monomineralic zone grows at the expense of an adjacent zone by reaction between diffusing components and the mineral of the adjacent zone. Equilibria between two phases at zone boundaries buffers the chemical potentials of the diffusing species. Thus, within a monomineralic zone, the chemical potentials of the diffusing components are controlled external to the local assemblage by the two-phase equilibria at the zone boundaries.
Mineralogically zoned calc-silicate skarn occurs as a narrow band that separates pyroxenite and marble along the intrusive contact and forms a rim on marble xenoliths in gabbro. Skarn consists of melilite or idocrase pseudomorphs of melili te, one or two . stoichiometric calcsilicate phases and accessory Ti-Zr garnet, perovskite and magnetite. The sequence of mineral zones from pyroxenite to marble, defined by a characteristic calc-silicate, is wollastonite, rankinite, spurrite, calcite. Mineral assemblages of adjacent skarn zones are compatible and the set of zones in a skarn band defines a facies type, indicating that the different mineral assemblages represent different bulk compositions recrystallized under identical conditions. The number of phases in each zone is less than the number that might be expected to result from metamorphism of a general bulk composition under conditions of equilibrium, trivariant in P, T and uCO2. The "special" bulk composition of each zone is controlled by reaction between phases of the zones bounding it on either side. The continuity of the gradients of composition of melilite and garnet solid solutions across the skarn is consistent with the local equilibrium hypothesis and verifies that diffusion was the mechanism of mass transport. The formula proportions of Ti and Zr in garnet from skarn vary antithetically with that of Si Which systematically decreases from pyroxenite to marble. The chemical potential of Si in each skarn zone was controlled by the coexisting stoichiometric calc-silicate phases in the assemblage. Thus the formula proportion of Si in garnet is a direct measure of the chemical potential of Si from point to point in skarn. Reaction between gabbroic magma saturated with plagioclase and clinopyroxene produced nepheline pyroxenite and melilite-wollastonite skarn. The calcsilicate zones result from reaction between calcite and wollastonite to form spurrite and rankinite.