Where academic tradition
meets the exciting future

The Structure of Elementary Strategies for Gene Assembly in Ciliates

Vladimir Rogojin, Ion Petre, The Structure of Elementary Strategies for Gene Assembly in Ciliates. Fundamenta Informaticae 137, 1–14, 2015.



We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and i stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 ... n, while its micronuclear form is an arbitrary signed
permutation. We focus on the elementary gene assembly model consisting of two operations on
signed permutations: eh (elementary hairpin inverting) and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the
elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation.

BibTeX entry:

  title = {The Structure of Elementary Strategies for Gene Assembly in Ciliates},
  author = {Rogojin, Vladimir and Petre, Ion},
  journal = {Fundamenta Informaticae},
  volume = {137},
  publisher = {IOS Press},
  pages = {1–14},
  year = {2015},

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

Publication Forum rating of this publication: level 2

Edit publication