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},
}