Tag: Natural Computing

Editorial for special issue on the interaction between computation and biology

Editorial for special issue on the interaction between computation and biology
Content Type Journal ArticlePages 187-188DOI 10.1007/s11047-010-9243-8Authors
Jon Timmis, University of York, Heslington, York, UKPaul Andrews, University of York, Heslin…

Editorial for special issue on the interaction between computation and biology

  • Content Type Journal Article
  • Pages 187-188
  • DOI 10.1007/s11047-010-9243-8
  • Authors
    • Jon Timmis, University of York, Heslington, York, UK
    • Paul Andrews, University of York, Heslington, York, UK
    • Susan Stepney, University of York, Heslington, York, UK

Distributed quantum programming

Abstract  In this paper we explore the structure and applicability of the Distributed Measurement Calculus (DMC), an assembly language
for distributed measurement-based quantum computations. We describe the formal language’s syntax and sem…

Abstract  

In this paper we explore the structure and applicability of the Distributed Measurement Calculus (DMC), an assembly language
for distributed measurement-based quantum computations. We describe the formal language’s syntax and semantics, both operational
and denotational, and state several properties that are crucial to the practical usability of our language, such as equivalence
of our semantics, as well as compositionality and context-freeness of DMC programs. We show how to put these properties to
use by constructing a composite program that implements distributed controlled operations, in the knowledge that the semantics
of this program does not change under the various composition operations. Our formal model is the basis of a quantum virtual
machine construction for distributed quantum computations, which we elaborate upon in the latter part of this work. This virtual
machine embodies the formal semantics of DMC such that programming execution no longer needs to be analysed by hand. Far from
a literal translation, it requires a substantial concretisation of the formal model at the level of data structures, naming
conventions and abstraction mechanisms. At the same time we provide automatisation techniques for program specification where
possible to obtain an expressive and user-friendly programming environment.

  • Content Type Journal Article
  • Pages 1-31
  • DOI 10.1007/s11047-010-9242-9
  • Authors
    • Ellie D’Hondt, Software Languages Lab, Vrije Universiteit Brussel, 10F719, Pleinlaan 2, 1050 Elsene, Belgium
    • Yves Vandriessche, Software Languages Lab, Vrije Universiteit Brussel, 10F719, Pleinlaan 2, 1050 Elsene, Belgium

DNA chips for species identification and biological phylogenies

Abstract  The codeword design problem is an important problem in DNA computing and its applications. Several theoretical analyses as
well as practical solutions for short oligonucleotides (up to 20-mers) have been generated recently. These s…

Abstract  

The codeword design problem is an important problem in DNA computing and its applications. Several theoretical analyses as
well as practical solutions for short oligonucleotides (up to 20-mers) have been generated recently. These solutions have,
in turn, suggested new applications to DNA-based indexing and natural language processing, in addition to the obvious applications
to the problems of reliability and scalability that generated them. Here we continue the exploration of this type of DNA-based
indexing for biological applications and show that DNA noncrosshybridizing (nxh) sets can be successfully applied to infer
ab initio phylogenetic trees by providing a way to measure distances among different genomes indexed by sets of short oligonucleotides
selected so as to minimize crosshybridization. These phylogenies are solidly established and well accepted in biology. The
new technique is much more effective in terms of signal-to-noise ratio, cost and time than current methods. Second, it is
demonstrated that DNA indexing does provide novel and principled insights into the phylogenesis of organisms hitherto inaccessible
by current methods, such as a prediction of the origin of the Salmonella plasmid 50 as being acquired horizontally, likely
from some bacteria somewhat related to Yesinia. Finally, DNA indexing can be scaled up to newly available universal DNA chips readily available both in vitro and in silico. In particular, we show how a recently obtained such set of nxh 16-mers can be used as a universal coordinate system in DNA
spaces to characterize very large groups (families, genera, and even phylla) of organisms on a uniform biomarker reference
system, a veritable and comprehensive “Atlas of Life”, as it is or as it could be on earth.

  • Content Type Journal Article
  • Pages 375-389
  • DOI 10.1007/s11047-010-9232-y
  • Authors
    • Max H. Garzon, Department of Computer Science, The University of Memphis, Memphis, TN 38152, USA
    • Tit-Yee Wong, Department of Biology, The University of Memphis, Memphis, TN 38152, USA

Quantum value indefiniteness

Abstract  The indeterministic outcome of a measurement of an individual quantum is certified by the impossibility of the simultaneous,
unique, definite, deterministic pre-existence of all conceivable observables from physical conditions of t…

Abstract  

The indeterministic outcome of a measurement of an individual quantum is certified by the impossibility of the simultaneous,
unique, definite, deterministic pre-existence of all conceivable observables from physical conditions of that quantum alone.

  • Content Type Journal Article
  • Pages 1-12
  • DOI 10.1007/s11047-010-9241-x
  • Authors
    • Karl Svozil, Institute for Theoretical Physics, Vienna University of Technology, Wiedner Hauptstraße 8-10/136, 1040 Vienna, Austria

A renewable, modular, and time-responsive DNA circuit

Abstract  In this article, we introduce a new design for DNA logic gates based on enzymatic restriction of DNA strands. We present a
construction for a set of one and two-input logic gates and argue that our construction can be generalized t…

Abstract  

In this article, we introduce a new design for DNA logic gates based on enzymatic restriction of DNA strands. We present a
construction for a set of one and two-input logic gates and argue that our construction can be generalized to implement any
Boolean operation. A key feature of our design is its time-responsiveness, in the presence of appropriate fuels our circuit
can operate continuously and generate a time-dependent output in response to a time-dependent input. Moreover, modulo connectivity
information, the strand design and circuit design phases are decoupled.

  • Content Type Journal Article
  • Pages 467-485
  • DOI 10.1007/s11047-010-9237-6
  • Authors
    • Ashish Goel, Departments of Management Science and Engineering and (by courtesy) Computer Science, Stanford University, Stanford, CA USA
    • Morteza Ibrahimi, Departments of Electrical Engineering, Stanford University, Stanford, CA USA

Abstract geometrical computation 5: embedding computable analysis

Abstract  Extended Signal machines are proven capable to compute any computable function in the understanding of recursive/computable
analysis (CA), represented here with type-2 Turing machines (T2-TM) and signed binary. This relies on a mix…

Abstract  

Extended Signal machines are proven capable to compute any computable function in the understanding of recursive/computable
analysis (CA), represented here with type-2 Turing machines (T2-TM) and signed binary. This relies on a mixed representation
of any real number as an integer (in signed binary) plus an exact value in (−1, 1). This permits to have only finitely many
signals present simultaneously. Extracting a (signed) bit, improving the precision by one bit and iterating a T2-TM only involve
standard signal machines. For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely
many iterations to produce an infinite output. This infinite duration can be provided by an infinite acceleration construction.
Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling
of accumulations.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s11047-010-9229-6
  • Authors
    • Jérôme Durand-Lose, LIFO, Université d’Orléans, B.P. 6759, 45067 Orléans Cedex 2, France

Strand algebras for DNA computing

Abstract  We present a process algebra for DNA computing, discussing compilation of other formal systems into the algebra, and compilation
of the algebra into DNA structures.

Content Type Journal ArticlePages 407-428DOI 10.1007/s11047-0…

Abstract  

We present a process algebra for DNA computing, discussing compilation of other formal systems into the algebra, and compilation
of the algebra into DNA structures.

  • Content Type Journal Article
  • Pages 407-428
  • DOI 10.1007/s11047-010-9236-7
  • Authors
    • Luca Cardelli, Microsoft Research, Cambridge, UK

NP-completeness of the energy barrier problem without pseudoknots and temporary arcs

Abstract  Knowledge of energy barriers between pairs of secondary structures for a given DNA or RNA molecule is useful, both in understanding
RNA function in biological settings and in design of programmed molecular systems. Current heuristi…

Abstract  

Knowledge of energy barriers between pairs of secondary structures for a given DNA or RNA molecule is useful, both in understanding
RNA function in biological settings and in design of programmed molecular systems. Current heuristics are not guaranteed to
find the exact energy barrier, raising the question whether the energy barrier can be calculated efficiently. In this paper,
we study the computational complexity of a simple formulation of the energy barrier problem, in which each base pair contributes
an energy of −1 and only base pairs in the initial and final structures may be used on a folding pathway from initial to final
structure. We show that this problem is NP-complete.

  • Content Type Journal Article
  • Pages 391-405
  • DOI 10.1007/s11047-010-9239-4
  • Authors
    • Ján Maňuch, Department of Mathematics, Simon Fraser University, Burnaby, BC Canada
    • Chris Thachuk, Department of Computer Science, University of British Columbia, Vancouver, BC Canada
    • Ladislav Stacho, Department of Mathematics, Simon Fraser University, Burnaby, BC Canada
    • Anne Condon, Department of Computer Science, University of British Columbia, Vancouver, BC Canada

Distributed agreement in tile self-assembly

Abstract  Laboratory investigations have shown that a formal theory of fault-tolerance will be essential to harness nanoscale self-assembly
as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena…

Abstract  

Laboratory investigations have shown that a formal theory of fault-tolerance will be essential to harness nanoscale self-assembly
as a medium of computation. Several researchers have voiced an intuition that self-assembly phenomena are related to the field
of distributed computing. This paper formalizes some of that intuition. We construct tile assembly systems that are able to
simulate the solution of the wait-free consensus problem in some distributed systems. (For potential future work, this may
allow binding errors in tile assembly to be analyzed, and managed, with positive results in distributed computing, as a “blockage”
in our tile assembly model is analogous to a crash failure in a distributed computing model.) We also define a strengthening
of the “traditional” consensus problem, to make explicit an expectation about consensus algorithms that is often implicit
in distributed computing literature. We show that solution of this strengthened consensus problem can be simulated by a two-dimensional
tile assembly model only for two processes, whereas a three-dimensional tile assembly model can simulate its solution in a
distributed system with any number of processes.

  • Content Type Journal Article
  • Pages 337-355
  • DOI 10.1007/s11047-010-9233-x
  • Authors
    • Aaron Sterling, Department of Computer Science, Iowa State University, Ames, IA USA

Forward

Forward
Content Type Journal ArticlePages 1-2DOI 10.1007/s11047-010-9240-yAuthors
Russell Deaton, Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA

Journal Natural ComputingOnline ISS…

Forward

  • Content Type Journal Article
  • Pages 1-2
  • DOI 10.1007/s11047-010-9240-y
  • Authors
    • Russell Deaton, Department of Computer Science and Computer Engineering, University of Arkansas, Fayetteville, AR 72701, USA