Extended strings and graphs for simple gene assembly

The simple intramolecular model for gene assembly in ciliates is particularly interesting because it can predict the correct assembly of all available experimental data, although it is not universal. The simple model also has a confluence property that is not shared by the general model. A previous formalization of the simple model through sorting of signed permutations is unsatisfactory because it effectively ignores one operation of the model and thus, it cannot be used to answer questions about parallelism in the model, or about measures of complexity. We propose in this paper a string-based model in which a gene is represented through its sequence of pointers and markers and its assembly is represented as a string rewriting process. We prove that this string-based model is equivalent to the permutation-based model as far as gene assembly is concerned, while it tracks all operations of the simple model. We also consider overlap graphs for these strings and prove the results with respect to the overlap of markers.

Authors

• Robert Brijder
• Miika Langille
• Ion Petre

Keywords

• Ciliates
• Simple gene assembly
• Strings