Transcript PPT3
Biochemistry, computing in biology Course outline 1 Introduction 2 Theoretical background Biochemistry/molecular biology 3 Theoretical background computer science 4 History of the field 5 Splicing systems 6 P systems 7 Hairpins 8 Detection techniques 9 Micro technology introduction 10 Microchips and fluidics 11 Self assembly 12 Regulatory networks 13 Molecular motors 14 DNA nanowires 15 Protein computers 16 DNA computing - summery 17 Presentation of essay and discussion Recombination Recombination and crossover Recombination and crossover Recombination and crossover If no exchange of genes (i.e. phenotypic marker) occurs, recombination event can not be detected Recombination and crossover Introduction to ciliates literature Genome Gymnastics: Unique Modes of DNA Evolution and Processing in Ciliates. David M. Prescott, Nature Reviews Genetics Computational power of gene rearrangement. Lila Kari and Laura Landweber, DIMACS series in discreet mathematics and theoretical computer science The ciliate Very ancient ( ~ 2 . 109 years ago) Very rich group ( ~ 10000 genetically different organisms) Very important from the evolutionary point of view The ciliate DNA molecules in micronucleus are very long (hundreds of kilo bps) DNA molecules in macronucleus are genesize, short (average ~ 2000 bps) The ciliate The ciliate tree Baldauf et al. 2000. Science 290:972. Urostyla grandis Eschaneustyla sp. Holosticha kessleri Uroleptus Bar: 50 mm Scrambled Genes sp. S.Found lemnae O. trifallax O. nova Bar: 25 mm Bar: 100 mm Bar: 100 mm The ciliate The ciliate Dapi staining of the ciliate Nuclei Micronucleus the small nucleus containing a single copy of the genome that is used for sexual reproduction Macronucleus the large nucleus that carries up to several hundred copies of the genome and controls metabolism and asexual reproduction Lifecycle of a ciliate Micronucleus Macronucleus Cutting, splicing, elimination, reordering, and amplification of DNA Prescott, 2000 The ciliate, meiosis The ciliate, reproduction MIC MAC Cell Pairing Meiosis and Nuclear Exchange Nuclear Fusion and Duplication of the Zygotic Nucleus Macronuclear Development and Nuclear Degeneration Polytenization Chromatid breakage De novo telomere formation Modified from Larry Klobutcher & Carolyn Jahn Ann. Review Microbiology, 2002 Computing in ciliates The ciliate Astounding feats of ‘DNA computing’ are routine in this ‘simple’ single -celled organism— a protozoan. In initial micronucleus, DNA is‘junky’ and scrambled, but…. ….it reassembles itself in proper sequence by means of computer-like acrobatics (unscrambling, throwing out genetic ‘junk’)—in macronucleus The complexity of spirotrich biology Telomere Pointers MAC MIC MDS: macronuclear destined sequences IES: internal eliminated segments Splicing Fractioned genes The complexity of gene scrambling Intervening non-coding DNA regions (IES: internal eliminated segments) interrupt protein-coding sequences (MDS macronuclear destined sequences) IESs are removed during macronuclear development MDSs are unscrambled Prescott, 2000 Scramble genes -TBP, actin I, DNA pol -TBP Prescott et al., 1998 Actin I Oxytricha nova Hogan et al., 2001 DNA polymerase Landweber et al., 2000 Degree of scrambling in -TBP Prescott et al, 1998 Unscrambling of actin I Hogan et al, 2001 Degree of scrambling in DNA pol Landweber et al, 2000 DNA folding and recombination DNA pol DNA folding and recombination DNA folding and recombination DNA pol DNA pol : Hairpin loop Prescott, 2000 Recombination -TBP Prescott et al, 1998 Tracing evolutionary scrambling (i) Isolate the micronuclear and macronuclear forms of the -TBP gene (ii) Compare the micronuclear and macronuclear gene structures (MDS and IESs) to determine whether the gene is scrambled (iii) Compare homologous MDSs and scrambling patterns in various stichotrich species (earlier diverging species vs later diverging species) (iv) Trace a parsimonious evolutionary scrambling pathway Comparisons of scrambling complexity Oxytrichidae and Paraurostyla weissei Uroleptus sp. The evolution of recombination Paraurostyla weissei Uroleptus sp. Stylonychia mytilus 100 100 Oxytricha nova 100 Oxytricha trifallax Evolutionary scrambling pathway Holosticha sp. S. mytilus O. nova O. trifallax P. weissei Uroleptus sp. Formal theory Ciliate computing The process of gene unscrambling in hypotrichous ciliates represents one of nature’s ingenious solutions to the computational problem of gene assembly. With some essential genes fragmented in as many as 50 pieces, these organisms rely on a set of sequence and structural detangle their coding regions. clues to For example, pointer sequences present at the junctions between coding and non-coding sequences permit reassembly of the functional copy. As the process of gene unscrambling appears to follow a precise algorithm or set of algorithms, the question remains: what is the actual problem being solved? The problem in the cell Genomic Copies of some Protein-coding genes are obscured by intervening nonprotein-coding DNA sequence elements (internally eliminated sequences, IES) Protein-coding sequences (macronuclear destined sequences, MDS) are present in a permuted order, and must be rearranged. Assumption By clever structural alignment…, the cell decides which sequences are IES and MDS, as well as which are guides. After this decision, the process is simply sorting, O(n). Decision process unknown, but amounts to finding the correct path. Most Costly. Ciliate computing there is some as yet undiscovered “oracle”mechanism within the cell, or the cell simulates non-determinism the former solution lacks biological credibility and the latter implies exponential time and space explosion. What we want is a deterministic algorithm for applying the inter- and intramolecular recombination operations to descramble an arbitrary gene. Ciliate computing The first proposed step in gene unscrambling— alignment or combinatorial pattern matching— may involve searches through several possible matches, via either intra-molecular or intermolecular strand associations. This part could be similar to Adleman’s (1994) DNA solution of a directed Hamiltonian path problem. Ciliate computing The second step—homologous recombination at aligned repeats—involves the choice of whether to retain the coding or the non-coding segment between each pair of recombination junctions. This decision process could even be equivalent to solving an n-bit instance of a satisfiability problem, where n is the number of scrambled segments. Ciliate computing We use develop our knowledge a model for of the first step to the guided homologous recombinations and prove that such a model has the computational power of a Turing machine, the accepted formal model of computation. This indicates that, in principle, these unicellular organisms may have the capacity to perform at least any computation electronic computer. carried out by an Ciliate computing, the naïve model Assume the cell simply reconstructs the genes by matching up pointers. Just one problem... pointer sequences are not unique. In fact, may have multiplicities greater than 13. The proposed solution to this was that the cell would simply try every possible combination of pointers until it found the right two. How the cell computes Relies on short repeat sequences to act as guides in homologous recombination events Splints analogous to edges in Adleman One example represents solution city HP (50 pieces reordered) of 50 Formal model Guided recombination system uxwxv uxv wx Formal model Context necessary for a recombination between repeats x (p, x, q) ~ (p’, x, q’) Formal model, splicing operation Formal Language Model uxwxv uxv wx Where u=u’p, w=qw’=w’’p’, v=q’v’ Intramolecular recombination. x. The guide is Delete x wx from original. Intermolecuar recombination. Exchange. Strand This is a universal Turing machine (proven by Tom Head) Formal model, splicing operation Gene unscrambling algorithm Ciliate computing Gene assembly in ciliates Micronucleus: cell mating Macronucleus: RNA transcripts (expression) Micro: I0 M1 I1 M2 I2 M3 … Ik Mk Ik+1 M = P1 N P2 Macro: permutation of (possibly rotated) M1,…, Mk and I0 ,…, Ik+1are removed Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Molecular operators Pointers The pointer sequences must be in spatial proximity during unscrambling Topology must be faithfully reproduced somehow Relocation of a locus Recombination event attaches Minor Locus to end of Major Locus