Search

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.

The simple intramolecular model for gene assembly in ciliates consists of three molecular operations, simple ld, simple hi and simple dlad. 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. Brijder and Hoogeboom introduced a new model in terms of overlap-inclusion graphs which could describe two of the three operations of the model and their combinatorial properties. To capture the third operation, we extended their framework to directed overlap-inclusion (DOI) graphs in Azimi et al. (2011) [1]. In this paper we introduce DOI graph-based rewriting rules that capture all three operations of the simple gene assembly model and prove that they are equivalent to the string-based formalization of the model.

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.

We consider a graph-based model for the process of gene assembly in ciliates, as proposed in [A. Ehrenfeucht, T. Harju, I. Petre, D. M. Prescott, G. Rozenberg, Computation in Living Cells: Gene Assembly in Ciliates, Springer, 2003]. The model consists of three operations, each reducing the order of the signed graph. Reducing the graph to the empty graph through a sequence of operations corresponds to assembling a gene. We investigate parallel reductions of a given signed graph, where the graph is reduced through a sequence of parallel steps. A parallel step consists of operations such that any of their sequential compositions are applicable to the current graph. We improve the basic exhaustive search algorithm reported in [A. Alhazov, C. Li, I. Petre, Computing the graph-based parallel complexity of gene assembly, Theoretical Computer Science, 2008 (in press)] to compute the parallel complexity of signed graphs. On the one hand, we reduce the number of sets of operations which should be checked for parallel applicability. On the other hand, we speed up the parallel applicability check procedure. We prove also that deciding whether a given parallel composition of operations is applicable to a given signed graph is a coNP problem. Deciding whether the parallel complexity (the length of a shortest parallel reduction) of a signed graph is bounded by a given constant is in NPNP.

The intramolecular model for gene assembly in ciliates considers three operations, ld, hi, and dlad that can assemble any gene pattern through folding and recombination: the molecule is folded so that two occurrences of a pointer (short nucleotide sequence) get aligned and then the sequence is rearranged through recombination of pointers. In general, the sequence rearranged by one operation can be arbitrarily long and consist of many coding and noncoding blocks. We consider in this paper simple variants of the three operations, where only one coding block is rearranged at a time. We characterize in this paper the gene patterns that can be assembled through these variants. Our characterization is in terms of signed permutations and dependency graphs. Interestingly, we show that simple assemblies possess rather involved properties: a gene pattern may have both successful and unsuccessful assemblies and also more than one successful assembling strategy.

Using the fact that the Parikh matrix mapping is not an injective mapping, the paper investigates some properties of the set of words with the same Parikh matrix; these words are called “amiable”. The presented results extend the results obtained in [A. Atanasiu, Binary amiable words, Int. J. Found. Comput. Sci. 18 (2) (2007) 387–400] for the binary case. In particular it is shown that all the words having the same Parikh matrix can be obtained one from another by applying only two types of transformations. Moreover, the mirrors of two amiable words are also amiable (thus forming a symmetrical class of words).

We consider a graph-based model for the study of parallelism in ciliate gene assembly, where a signed graph is associated to each micronuclear gene and the gene assembly is modeled as a graph rewriting process. A natural measure of complexity for gene assembly counts the minimal number of parallel steps needed to reduce the associated signed graph. We investigate the complexity of several classes of the graphs, so far found graphs of parallel complexity up to six. The general problem of whether there exists a finite upper bound for the graph parallel complexity still remains open.

Self-assembly is the process in which simple objects autonomously aggregate into large structures and it has become one of the major tools for nano-scale engineering. We propose in this paper a string-based framework inspired by the principle of self-assembly: two strings with a common overlap, say uv and vw, yield a string uvw; we say that string uvw has been assembled from strings uv and vw. The operation may be extended in a natural way also to sets of strings. We answer several questions: what is the assembly power of a given set of strings, can a given set of strings be generated through assembly and if so, what is a minimal generator for it?

Summary Ciliates have developed a puzzling genomic organization. Genes are broken into many pieces in the micronucleus, separated by non-coding sequences, and sometimes also shuffled and inverted. During sexual reproduction, all pieces are precisely assembled in the orthodox order to yield the transcriptionally active macronuclear genes. We give in this paper a brief survey of the genome structure in stichotrichous ciliates and present two molecular models proposed for gene assembly. We then establish a set of invariants for gene assembly. We prove that in any model based on the paradigm of pointer-directed assembly, the set of molecules excised during the assembly of a given gene, the linearity of the assembled gene, and its IES context are all uniquely defined by the micronuclear structure of the gene and thus, are invariants of the gene assembly process.

We prove that for any nonperiodic set of words F \subseteq Σ+ with at most three elements, the centralizer of F, i.e., the largest set commuting with F, is F*. Moreover, any set X commuting with F is of the form X = FI, for some I \subseteq ℕ. A boundary point is thus established, as these results do not hold for all languages with at least four words. This solves a conjecture of Karhumaki and Petre, and provides positive answers to special cases of some intriguing questions on commutation of languages, raised by Ratoandromanana and Conway.

We survey in this paper the main differences among three variants of an intramolecular model for gene assembly: the general, the simple, and the elementary models. We present all of them in terms of sorting signed permutations and compare their behavior with respect to: (i) completeness, (ii) confluence (with the notion defined in three different setups), (iii) decidability, (iv) characterization of the sortable permutations in each model, (v) sequential complexity, and (vi) experimental validation.

In this chapter we shall introduce two formalizations of the MDS structure of genes, viz., MDS arrangements and MDS descriptors. MDS arrangements result from representing each elementary or composite MDS by its own symbol, and then by representing the MDS structure of a micronuclear or an intermediate gene by the string of symbols corresponding to the sequence of MDSs. On the other hand. MDS descriptors follow the key observation concerning gene assembly (stated in Chap. 2) that it is not the whole structure of MDSs but only their repeat sequences (pointers) that guide gene assembly. Therefore, in the framework of MDS descriptors each MDS is represented by the pair of its pointers, with each pointer represented by its own symbol. Correspondingly, the IUS descriptor of a micronuclear or an intermediate gene is the string of pairs of pointers corresponding to the sequence of MDSs.

Gene assembly in ciliates is a life process fascinating from both the biological and the computational points of view. Several formal models of this process have been formulated and investigated, among them a model based on (legal) strings and a model based on (overlap) graphs. The latter is more abstract because the translation of legal strings into overlap graphs is not injective. In this paper we consider and solve the overlap equivalence problem for realistic strings: when do two different realistic legal strings translate into the same overlap graph? Realistic legal strings are legal strings that “really” correspond to genes generated during the gene assembly process.

A word u appears as a factor of another word v as it is: in one piece. When u is a subword of v, u may be scattered as several factors. We consider the case in between and put some restrictions on the number of factors as to which u is allowed to be scattered. A large class of partial orders which are generalizations of factors and subwords is obtained. Investigating the borderline between their finite and infinite antichains, we are able to fully characterize the property of being well partial order. The result generalizes Higman’s theorem.

The centralizer of a set of words X is the largest set of words C(X)commuting with X: XC(X)=C(X)X. It has been a long standing open question due to [J.H. Conway, Regular Algebra and Finite Machines, Chapman & Hall, London (1971).], whether the centralizer of any rational set is rational. While the answer turned out to be negative in general, see [M. Kunc, Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, Springer, Berlin, 2004, pp. 870–881.], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. This result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [B. Ratoandromanana, RAIRO Inform. Theor. 23(4) (1989) 425–444.]—many of the techniques we use in this paper follow her ideas. We also give in this paper an elementary proof for the prefix case.

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.