Computational Efficiency of Intermolecular Gene Assembly

• Autorzy: Ishdorj T-O. , Loos R. , Petre I.
• Języki publikacji: EN

Abstrakty

EN

We investigate here the computational efficiency of gene rearrangement found in ciliates (unicellular organisms). We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, these systems can uniformly solve SAT with time complexity O(nźm) for a Boolean formula of m clauses over n variables.

Słowa kluczowe

EN

parallel time complexity; nondeterminism; gene assembly in ciliates

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 3-4
• Strony: 363--373
• Opis fizyczny: bibliogr. 16 poz.

Twórcy

autor

Ishdorj T-O.

autor

Loos R.

autor

Petre I.

• Computational Biomodelling Laboratory, Department of Information Technologies, Abo Akademi University, FIN-20520 Turku, Finland,

Bibliografia

• [1] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D. M., Rozenberg, G.: Computation in Living Cells: GeneAssembly in Ciliates, Springer, 2003.
• [2] Ehrenfeucht, A., Harju, T., Prescott, D. M., Rozenberg, G.: Computational aspects of gene (un)scrambling in ciliates, in: Evolution as Computation, (L. F. Landweber, E. Winfree Eds.), Springer, 2001, 216-256.
• [3] Garey, M., Johnson, D., Computers and Intractability. A Guide to the Theory of NP-completeness, Freeman, San Francisco, CA, 1979.
• [4] Harju, T., Petre, I., Rozenberg, G.: Two models for gene assembly in ciliates, in: Theory is forever, LNCS 3113, Springer, 2004, 89-101.
• [5] Head, T., Formal Language Theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, in: Bull. Math. Biology 49, 1987, 737-759.
• [6] Ishdorj, T.-O.: Membrane Computing, Neural Inspirations, Gene Assembly in Ciliates, PhD Thesis, Sevilla University, March 2007.
• [7] Ishdorj, T.-O., Petre, I.: Computing through gene assembly, TUCS Report 816, Proc. 6th Int. Conf. Unconventional Computation, (S. G. Akl, et. al. Eds.), Kingston, Canada, LNCS 4618, Springer, 2007, 91-105.
• [8] Ishdorj, T.-O., Petre, I., Rogojin, V.: Computational power of intramolecular gene assembly, International Journal of Foundations of Computer Science, World Scientific, 18(5)(2007), 1123-1136.
• [9] Kari, L., Landweber, L. F.: Computational power of gene rearrangement, in: Proceedings of DNA Based Computers, V (E. Winfree and D. K. Gifford, Eds.), American Mathematical Society, 1999, 207-216.
• [10] Kari, L., Thierrin, G.: Contextual insertion/deletions and computability, Information and Computation 131, 1996,47-61.
• [11] Landweber, L. F., Kari, L.: The evolution of cellular computing: Nature's solution to a computational problem, in: Proc. The 4th DIMACS Meeting on DNA-Based Computers, Philadelphia, PA, 1998, 3-15.
• [12] Loos, R., Martin-Vide, C, Mitrana, V.: Solving SAT and HPP with accepting splicing systems, PPSNIX, LNCS 4193, Springer, 2006, 771-777.
• [13] Papadimitriou, Ch. P.: Computational Complexity, Addison-Wesley, Reading, MA, 1994.
• [14] Paun, Gh., Rozenberg, G., Salomaa, A.: DNA Computing - New computing paradigms, Springer, 1998.
• [15] Prescott, D. M., Ehrenfeucht, A., Rozenberg, G.: Molecular operations for DNA processing in hypotrichous ciliates. Europ. J. Protistology 37, (2001), 241-260.
• [16] Salomaa, Formal Languages, Academic Press, New York, 1973