Affiliations: Comp. Biomodelling Labor., Dep. of Information
Technologies Åbo Akademi University, Turku 20520, Finland.
E-mail: tishdorj@abo.fi | Research Group on Mathematical Linguistics, Rovira i
Virgili University Plaça Imperial Tàrraco 1, 43005 Tarragona, Spain.
E-mail: remcogerard.loos@urv.cat | Comp. Biomodelling Labor., Dep. of Information
Technologies Åbo Akademi University, Turku 20520, Finland.
E-mail: ipetre@abo.fi
Note: [] Address for correspondence: Computational Biomodelling
Laboratory, Department of Information Technologies, Åbo Akademi
University, Turku 20520, Finland
Abstract: 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.
Keywords: Parallel time complexity, non-determinism, gene assembly in ciliates
