Extending the Overlap Graph for Gene Assembly in Ciliates
From MaRDI portal
Publication:3540104
DOI10.1007/978-3-540-88282-4_14zbMATH Open1156.68420arXiv0712.3380OpenAlexW1534477878MaRDI QIDQ3540104FDOQ3540104
Authors: Robert Brijder, Hendrik Jan Hoogeboom 
Publication date: 20 November 2008
Published in: Language and Automata Theory and Applications (Search for Journal in Brave)
Abstract: Gene assembly is an intricate biological process that has been studied formally and modeled through string and graph rewriting systems. Recently, a restriction of the general (intramolecular) model, called simple gene assembly, has been introduced. This restriction has subsequently been defined as a string rewriting system. We show that by extending the notion of overlap graph it is possible to define a graph rewriting system for two of the three types of rules that make up simple gene assembly. It turns out that this graph rewriting system is less involved than its corresponding string rewriting system. Finally, we give characterizations of the `power' of both types of graph rewriting rules. Because of the equivalence of these string and graph rewriting systems, the given characterizations can be carried over to the string rewriting system.
Full work available at URL: https://arxiv.org/abs/0712.3380
Recommendations
- Combining overlap and containment for gene assembly in ciliates
- REDUCTION GRAPHS FROM OVERLAP GRAPHS FOR GENE ASSEMBLY IN CILIATES
- Directed overlap-inclusion graphs as representations of ciliate genes
- Characterizing Reduction Graphs for Gene Assembly in Ciliates
- String and graph reduction systems for gene assembly in ciliates
- Gene Assembly Algorithms for Ciliates
- On computational properties of gene assembly in ciliates
- scientific article; zbMATH DE number 2156288
- scientific article; zbMATH DE number 1836434
- Gene assembly in ciliates: Computing by folding and recombination
Cites Work
- Circle graph obstructions
- Computation in living cells. Gene assembly in ciliates
- Formal systems for gene assembly in ciliates.
- String and graph reduction systems for gene assembly in ciliates
- A String-Based Model for Simple Gene Assembly
- Reducibility of gene patterns in ciliates using the breakpoint graph.
- Simple gene assembly is deterministic
Cited In (7)
- Aspects of Molecular Computing
- Combining overlap and containment for gene assembly in ciliates
- Graph Polynomials Motivated by Gene Rearrangements in Ciliates
- Characterizing Reduction Graphs for Gene Assembly in Ciliates
- From Micro to Macro: How the Overlap Graph Determines the Reduction Graph in Ciliates
- REDUCTION GRAPHS FROM OVERLAP GRAPHS FOR GENE ASSEMBLY IN CILIATES
- Overlapping genes in vertebrate genomes
This page was built for publication: Extending the Overlap Graph for Gene Assembly in Ciliates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540104)
