Extending the Overlap Graph for Gene Assembly in Ciliates

DOI10.1007/978-3-540-88282-4_14MaRDI QIDQ3540104zbMATH OpenOpenAlexFDO

Authors Robert Brijder, Hendrik Jan Hoogeboom

Publication date 20 November 2008

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.3380

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Grammars and rewriting systems (68Q42)

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.

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

• A String-Based Model for Simple Gene Assembly
• Circle graph obstructions
• Computation in living cells. Gene assembly in ciliates
• Formal systems for gene assembly in ciliates.
• Reducibility of gene patterns in ciliates using the breakpoint graph.
• Simple gene assembly is deterministic
• String and graph reduction systems for gene assembly in ciliates

Cited in

(7)

• Combining overlap and containment for gene assembly in ciliates
• Aspects of Molecular Computing
• 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)