Combinatorial Models for DNA Rearrangements in Ciliates

The talk presents a novel trend of the DNA computing, regarding the modelling of simple DNA recombinations present in nature. Motivated by  genome rearrangements that take place in some species of ciliates we introduce a combinatorial model for these processes based on spatial graphs. 


We investigate spatial graphs that consist of 4-valent rigid vertices, called assembly graphs.  An assembly graph can be seen as a representation of DNA  molecule during certain recombination processes, in which 4-valent vertices represent molecular  alignment of the recombination sites. We introduce a notion of polygonal path in assembly graph as a model for a single gene.  Polygonal paths are defined as  paths that make "90-degrees-turn'' at each vertex of the assembly graph and define smoothing of the vertices visited by the paths. Such vertex smoothing models a homologous DNA recombination. We investigate the minimal number of polygonal paths that visit all vertices of a given graph exactly once, called assembly number and we also study the relationship between the number of vertices in assembly graph and its assembly number. 


We study the recombination strategies  by subsets of vertices. Such a subset is called successful set if smoothing of all vertices from the set with respect to a polygonal path results in a graph that contains the polygonal path in a single component. We characterize the successful sets in a given assembly graph and we define a smoothing strategy in assembly graph relative to a polygonal path as a sequence of successful sets which model a successive DNA recombinations  for correct gene assembly.



Joint work with: N. Jonoska and M. Saito.