Warning: strtotime(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /var/www/html/www_publications/index.php on line 342

Warning: Cannot modify header information - headers already sent by (output started at /var/www/html/www_publications/index.php:342) in /var/www/html/www_publications/index.php on line 4076
Computational Efficiency of Intermolecular Gene Assembly (bibtex)
Computational Efficiency of Intermolecular Gene Assembly (bibtex)
by Ishdorj, Tseren-Onolt, Loos, Remco and Petre, Ion
Abstract:
In this paper, we investigate the computational efficiency of gene rearrangement operations found in ciliates, a type of unicellular organisms. We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, we prove that these systems can uniformly solve SAT in time O(nm) for a boolean formula of m clauses over n variables.
Reference:
Computational Efficiency of Intermolecular Gene Assembly (Ishdorj, Tseren-Onolt, Loos, Remco and Petre, Ion), In Int. Workshop on Language Theory in Biocomputing (Michael Domaratzki, Kai Salomaa, eds.), Queen's University, Kingston, Canada, 2007.
Bibtex Entry:
@InProceedings{inp102,
author    = {Ishdorj, Tseren-Onolt AND Loos, Remco AND Petre, Ion},
title     = {Computational Efficiency of Intermolecular Gene Assembly},
booktitle = {Int. Workshop on Language Theory in Biocomputing},
year      = {2007},
editor    = {Michael Domaratzki and Kai Salomaa},
pages     = {39-49},
publisher = {Queen's University, Kingston, Canada},
abstract  = {In this paper, we investigate the computational efficiency of gene rearrangement operations found in ciliates, a type of unicellular organisms. We show how the so-called guided recombination systems, which model this gene rearrangement, can be used as problem solvers. Specifically, we prove that these systems can uniformly solve SAT in time O(nm) for a boolean formula of m clauses over n variables.},
keywords  = {computational efficiency; intermolecular gene assembly in ciliates},
pdf       = {pdfs/ILP2007a.pdf},
}