Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
363--373
Opis fizyczny
bibliogr. 16 poz.
Twórcy
autor
autor
autor
- Computational Biomodelling Laboratory, Department of Information Technologies, Abo Akademi University, FIN-20520 Turku, Finland, tishdorj@abo.fi
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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS5-0015-0079