Simple gene assembly as a rewriting of directed overlap-inclusion graphs

Journal article (2012)

Authors

Sepinoud Azimi Åbo Akademi University
Tero Harju University of Turku, Turku Centre for Computer Science
Miika Langille Åbo Akademi University
Ion Petre Åbo Akademi University, Turku Centre for Computer Science
Affiliation
External organisation
Directed overlap inclusion graphs Graph-based simple operations Simple gene assembly
More Info
expand_more

Published Date

2012

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

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.