Skip to main content
Journal cover image

Micro flow bio-molecular computation.

Publication ,  Journal Article
Gehani, A; Reif, J
Published in: Bio Systems
October 1999

In this paper we provide a model for micro-flow based bio-molecular computation (MF-BMC). It provides an abstraction for the design of algorithms which account for the constraints of the model. Our MF-BMC model uses abstractions of both the recombinant DNA (RDNA) technology as well as of the micro-flow technology and takes into account both of their limitations. For example, when considering the efficiency of the recombinant DNA operation of annealing, we take into account the limitation imposed by the concentration of the reactants. The fabrication technology used to construct MEMS is limited to constructing relatively thin 3D structures. We abstract this by limiting the model to a small constant number of layers (as is done with VLSI models). Besides our contribution of the MF-BMC model, the paper contains two other classes of results. The main result is the volume and time efficient algorithm for message routing in the MF-BMC model, specifically useful for PA-Match. We will show that routing of strands between chambers will occur in time O(N x D/ m x n), where N is the number of strands in the MF-BMC, n is the number of chambers where RDNA operations are occurring, D is the diameter of the topology of the layout of the chambers, and m is proportional to the channel width. Operations that need annealing, such as PA-Match, are shown feasible in O(N2logN/n/n) volume instead of the previous use of omega(N2) volume, with reasonable time constraints. Applications of the volume efficient algorithm include the use of the Join operation for databases, logarithmic depth solutions to SAT (Boolean formula satisfiability) problems and parallel algorithms that execute on a PRAM. Existent algorithms can be mapped to ones that work efficiently in the MF-BMC model, whereas previous methods for applications such as PRAM simulation in BMC were not both time and volume efficient. Our other class of results are theoretical lower bounds on the quantities of DNA and the time needed to solve a problem in the MF-BMC model, analogous to lower bounds in VLSI. We bound the product BT from below, and further show that BT2 has a stronger lower bound of I2. Here B is the maximum amount of information encoded in the MF-BMC system at a time. T is the time for an algorithm to complete, and I is the information content of a problem.

Duke Scholars

Published In

Bio Systems

DOI

EISSN

1872-8324

ISSN

0303-2647

Publication Date

October 1999

Volume

52

Issue

1-3

Start / End Page

197 / 216

Related Subject Headings

  • Models, Molecular
  • Humans
  • DNA, Recombinant
  • DNA
  • Computer Simulation
  • Computational Biology
  • Bioinformatics
  • Animals
  • 40 Engineering
  • 31 Biological sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Gehani, A., & Reif, J. (1999). Micro flow bio-molecular computation. Bio Systems, 52(1–3), 197–216. https://doi.org/10.1016/s0303-2647(99)00048-9
Gehani, A., and J. Reif. “Micro flow bio-molecular computation.Bio Systems 52, no. 1–3 (October 1999): 197–216. https://doi.org/10.1016/s0303-2647(99)00048-9.
Gehani A, Reif J. Micro flow bio-molecular computation. Bio Systems. 1999 Oct;52(1–3):197–216.
Gehani, A., and J. Reif. “Micro flow bio-molecular computation.Bio Systems, vol. 52, no. 1–3, Oct. 1999, pp. 197–216. Epmc, doi:10.1016/s0303-2647(99)00048-9.
Gehani A, Reif J. Micro flow bio-molecular computation. Bio Systems. 1999 Oct;52(1–3):197–216.
Journal cover image

Published In

Bio Systems

DOI

EISSN

1872-8324

ISSN

0303-2647

Publication Date

October 1999

Volume

52

Issue

1-3

Start / End Page

197 / 216

Related Subject Headings

  • Models, Molecular
  • Humans
  • DNA, Recombinant
  • DNA
  • Computer Simulation
  • Computational Biology
  • Bioinformatics
  • Animals
  • 40 Engineering
  • 31 Biological sciences