Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Solutions to Computational Pro...

Solutions to Computational Problems Through Gene Assembly

Artiom Alhazov, Ion Petre, Vladimir Rogojin, Solutions to Computational Problems Through Gene Assembly. In: Hao Yan Max Garzon (Ed.), DNA Computing, 13th International Meeting on DNA Computing, Lecture Notes in Computer Science 4848, 36–45, Springer Berlin, 2008.

Abstract:

Gene assembly in ciliates is an impressive computational process. Ciliates have a unique way of storing their genetic information in two fundamentally different forms within their two types of nuclei. Micronuclear genes are broken into blocks (called MDSs), with MDSs shuffled and separated by non-coding material; some of the MDSs may even be inverted. During gene assembly, all MDSs are sorted in the correct order to yield the transcription-able macronuclear gene. Based on the intramolecular model for gene assembly, we prove in this paper that gene assembly may be used in principle to solve computational problems. We prove that any given instance of the hamiltonian path problem may be encoded in a suitable way in the form of an ‘artificial’ gene so that gene assembly is successful on that gene-like pattern if and only if the given problem has an affirmative answer.

Files:

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpAlPeRo08a,
  title = {Solutions to Computational Problems Through Gene Assembly},
  booktitle = {DNA Computing, 13th International Meeting on DNA Computing},
  author = {Alhazov, Artiom and Petre, Ion and Rogojin, Vladimir},
  volume = {4848},
  series = {Lecture Notes in Computer Science},
  editor = {Max Garzon, Hao Yan},
  publisher = {Springer Berlin},
  pages = {36–45},
  year = {2008},
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Publication Forum rating of this publication: level 1

Edit publication