The Structure of Elementary Strategies for Gene Assembly in Ciliates

Issue title: Special issue in memoriam of Yurii Rogozhin

Article type: Research Article

Authors: Rogojin, Vladimir | Petre, Ion

Affiliations: Computational Biomodeling Laboratory, Turku Centre for Computer Science and Department of Information Technologies, Åbo Akademi University, 20520 Turku, Finland. [email protected], [email protected]

Note: [] Address for correspondence: Computational Biomodeling Laboratory, Turku Centre for Computer Science and, Department of Information Technologies, Åbo Akademi University, 20520 Turku, Finland

Abstract: 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 ī 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.

DOI: 10.3233/FI-2015-1204

Journal: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 145-158, 2015