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. TUCS Technical Reports 1001, Turku Centre for Computer Science, 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.


Full publication in PDF-format

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},
  number = {1001},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2011},

Belongs to TUCS Research Unit(s): Turku BioNLP Group, Computational Biomodeling Laboratory (Combio Lab)

Edit publication