Where academic tradition
meets the exciting future

Directed Overlap-Inclusion Graphs as Representations of Ciliate Genes

Sepinoud Azimi, Tero Harju, Miika Langille, Ion Petre, Vladimir Rogojin, Directed Overlap-Inclusion Graphs as Representations of Ciliate Genes. Fundamenta Informaticae 110(1-4), 29–44, 2011.


The simple intramolecular model for gene assembly in ciliates consists of three molecular operations based on local DNA manipulations. It was shown to predict correctly the assembly of all currently known ciliate gene patterns. Mathematical models in terms of signed permutations and signed strings proved limited in capturing some of the combinatorial details of the simple gene
assembly process. A different formalization in terms of overlap-inclusion graphs, recently introduced
by Brijder and Hoogeboom, proved well-suited to describe two of the three operations of the model and their combinatorial properties. We introduce in this paper an extension of the framework of Brijder and Hoogeboom in terms of directed overlap-inclusion graphs where more of the linear
structure of the ciliate genes is described. We investigate a number of combinatorial properties of
these graphs, including a necessary property in terms of forbidden induced subgraphs.

BibTeX entry:

  title = {Directed Overlap-Inclusion Graphs as Representations of Ciliate Genes},
  author = {Azimi, Sepinoud and Harju, Tero and Langille, Miika and Petre, Ion and Rogojin, Vladimir},
  journal = {Fundamenta Informaticae},
  volume = {110},
  number = {1-4},
  pages = {29–44},
  year = {2011},
  keywords = {Directed overlap-inclusion graphs, gene assembly in Ciliates, simple operations},

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

Publication Forum rating of this publication: level 2

Edit publication