Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: simple operations

Sortuj według:

Ogranicz wyniki do:

Directed Overlap-inclusion Graphs as Representations of Ciliate Genes

Azimi S., Harju T., Langille M., Petre I., Rogojin V.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

29-44

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.

Simple Gene Assembly Is Deterministic

Langille M., Petre I.

Fundamenta Informaticae

2006

Vol. 73, nr 1-2

179-190

We investigate in this paper a simple intramolecular model for gene assembly in ciliates. Unlike the general intramolecular model, the folds that a micronuclear chromosome may form to assemble the genes is very restricted (minimal) here: between any two pointers there may be at most one coding block. It has been known that the general model is universal, being able to assemble any gene pattern (to sort any signed permutation). The simple model on the other hand is not universal: there exist signed permutations that cannot be sorted in this model. Remarkably though, all known micronuclear gene patterns in ciliates can indeed be assembled in the simple model. We prove in this paper that while the general model is non-deterministic, the simple model is ``weakly deterministic'': any gene pattern either has only successful or only unsuccessful sorting strategies. Moreover, although different strategies may lead to different permutations for the same input, these final results have the same structure.