Definitionen

• the whole hereditary information of an organism that is encoded in the DNA (or, for some viruses, RNA)

• includes both the genes and the non-coding sequences

• a complete DNA sequence of one set of chromosomes, for example, one of the two sets that a diploid individual carries in every cell

• nuclear genome, mitochondrial genome, chloroplast genome

• Based on rRNA sequences, weil diese in jedem Gen enthalten sind

• Archaea

• Bacteria

• Eucarya

• 1976: first viral genome, ~5000 bp

• 1981: Human mitochondrial genome, ~16.500 bp

• 1986: Chloroplast genome, ~156.000 bp

• 1995: first genome of a free-living organism

• 1996: First eukaryotic genome (S. cerevisiae)

• 1998: first multicellular organism

• 1999: first human chromosome

• 2000: D. melanogaster

• 2001: first draft sequence of human genome

• 3.200.000.000 nucleotides of DNA

• 24 linear molecules, the shortest 50.000.000 nucleotides in length and the longest 260.000.000 nucleotides, each contained in a different chromosome

• These 24 chromosomes consost of 22 autosomes and the two sex chromosomes, X and Y

• a circular DNA molecule of 16.569 nucleotides, multiple copies of which are located in the energy-generating organelles called mitochondria

• Construction of clone-based physical maps produces overlapping series of clones (that is, contigs), each of which spans a large, contiguous region of the source genome.

• Individual mapped clones are subcloned into smaller insert librariesm from which sequence reads are randomly derived -> thousands sequence reads per clone

• The resulting sequence data set is then used to assemble the complete sequence of that clone

• an individual clone, such as a bacterial artificial chromosome (BAC), is selected

• Large amount of BAC DNA is purified and fragmented

• The random DNA fragments (typically 2-5 kb in size) are subcloned

• sequence reads are generated from one or both ends of randomly selected subclones

• the random reads are then assembled on the basis of sequence overlaps, yielding preliminary sequence assemblies (prefinished sequence)

• such sequence is imperfect

  • gaps (breaks between the horizontal lines)

  • areas of poor sequence quality (thinner horizontal lines)

• often, the order and orientation of some of the sequence contigs is not known

• Subsequent customized sequence finishing, involving the generation of additional sequence data for closing gaps and bolstering areas of poor sequence quality, yields finished, highly accurate sequence across the entire clone

• shotgun sequencing is a method used for sequencing random DNA strands

• whole-genome sequencing is the process of determining the entirety, or nearly the entirety, of the DNA sequence of an organism's genome at a single time

Whole-genome shotgun sequencing:

• the mapping phase is skipped

• shotgun sequencing proceeds using subclone libraries prepared from the entire genome

• typically, tens of millions of sequence reads are generated

• computer-based assembly used to generate contiguous sequences of various sizes

• computational assembly of redundant collections of sequence reads, from which an accurate consensus sequence can be deduced

• problems with tandemly repeated DNA or genome-wide repeats: can result in incorrect overlap

• Generate BAC shotgun reads and generate whole-genome shotgun reads -> Combine overlapping whole-genome and BAC-derived reads -> assemble and finish

short interspersed nuclear elements

long interspersed nuclear elements

• database similarity search

• All-against-all comparison within proteome

• Protein comparison between proteoms

• Search of clusters

• Short, recurring patterns in DNA that are presumed to have a biological function

• often they indicate sequence specific binding sites for proteins such as nucleases and transcription factors (TF)

• Others are involved in important processes at the RNA level

  • ribosome binding

  • mRNA processing (splicing, editing, polyadenylation)

  • transcription termination

• fewer TFs

• long motifs

• affinity depends on match

• more TFs per gene

• shorter motifs

• Much more noncoding seq

• regulatory modules

• long range effects

• often dimer, tetramer: palindromic binding size (Reliefpfeiler)

• binding

  • stochastic

  • affinity = structural / sequence match

  • high affinity not always desirable (!)

• combinatorial regulation (esp. eukaryotes)

  • order important

  • site spacing important

• 1 genome: sequence overrepresentation

• Functional Genomics: predict regulons

• N genomes: phylogenetic footprinting

• N genomes + Functional Genomics: Phylocon, new ideas…

• Binding sites for proteins

• short substrings (5-25 nucleotides)

• up to 1000 nucleotides (or farther) from gene

• Inexactly repeating patterns (“motifs”)

showing the frequencies scaled relative to the information content (measure of conservation) at each position

• idea: scale each stack of letters with some measure of conservation at each base

• positions that are perfectly conserved contain 2 bits of information

• those where two of the four bases occur 50% of the time each contain 1 bit

• those where all four bases occur equally often contain no information

using relative entropy to adjust for low GC content

Assume that each base type occurs at least once in each alignment position. If we treat all bases and all alignment columns the same way: p_i,b = (n_i,b + 1) / (N_seq + 4) (künstlich counts hinzufügen, so tun als ob wir mehr Daten haben)

additional data to overcome lack of data

take advantage of the knowledge we have of the properties of sequences

Pb - frequency of occurrence of base of type b

beta: a simple scaling parameter that determines the total number of pseudocounts in an alignment column. Advantage is that we can easily adjust the relative weighting of the pseudocounts and real data. When there are a lot of data (Nseq large) there is little need for pseudocounts, and beta should be smaller than Nseq whereas when there are less data, beta should be larger relative to Nseq.

• A popular solution: beta = sqrt(Nseq). At large values of NSeq we get p_i,b = (n_i,b / N_seq)

Regular expression: /[AT][GC][AC][ACGT]*A[TG][CG]/

• The regular expression is able to find all possible sequences, but do not distinguish between the consesnsus sequence and the highly unlikely sequence: ACAC-ATC or TGCT- -AAG

• weight matrixes can be used to score the sequence but do not deal with insertions and deletions

• Sammlung von Motifen und Mustern, die aus Proteinsequenzen gewonnen wurden und durch Durchsicht von Proteinfamilien verfeinert wurden

• Database of protein domains, families and functional sites

• the probability of a sequence x

  • depends on sequence length

  • get infinitely small as the x becomes longer

• Solution: NULL (background) model

  • Treats sequences as random strings of nucleotides

  • For example a random distribution: A=T=C=G=0.25, or overall nucleotide frequencies in the organism

  • The probability of sequence of length L is 0.25^L

• A high log-odds score corresponds to a sequence that looks more like a gene model than the background model

• HMM generates a sequence

• When we visit a state, we emit a residue from the state’s emission probability distribution

• The model thus generates two strings of information:

  • the underlying state path (the labels), as we transition from state to state

  • the observed sequence, each residue being emitted from one state in the state path

• The state path is a Markov chain: what state we go next depends only on what state we are in

• Since we are only given the observed sequence, this underlying state path is hidden: these are residue labels we’d like to infer

• The state path is a hidden Markov chain

finds the most probably state paths given a sequence and a HMM using dynamic programming

• Affiniry of a DNA binding protein to a specific binding site is typically correlated with how well the site matches the consensus sequence

• But..

  • not all positions in a binding site are equally forgiving of mismatches

  • not all mismatches at a given position have the same effect

• Genes are turned on or off by regulatory proteins

• These proteins bind to upstream regulatory regions of genes to either attract or block an RNA polymerase

• Regulatory protein X binds to a short DNA sequence called a motif

• So finding the same motif in multiple genes’ regulatory regions suggests a regulatory relationship amongst those genes

• We do not know the motif sequence

• we do not know where it is located relative to the genes start

• Motifs can differ slightly from one gene to the next

• How to discern it from “random” motifs?

• Given a random sample of DNA sequences

• Find the pattern that is implanted in each of the individual arrays, namely, the motif

• Additional information:

  • The hidden sequence is of length 8

  • The pattern is not exactly the same in each array because random point mutations may occur in the sequences

• The problem: Can we still find the motif, now that we have 2 mutations? What is the consesus sequence?

• to define a motif, lets say we know where the motif starts in the sequence

• the motif start positions in their sequences can be represented as s = (s1, s2, s3, …, st)

• Line up the patterns by their start indexes

• Construct matrix profile with frequencies of each nucleotide in columns

• Consensus nucleotide in each position has the highest score in column

• Consensus sequences help in finding motifs

• Think of consensus as an “ancestor” motif, from which mutated motifs emerged

• The distance between a real motif and the consensus sequence is generally less than that for two real motifs

• we have a guess about the motif starting points and consensus sequence, but how “good” is this consensus?

• Need to introduce a scoring function to compare different guesses and choose the “best” one

• Given a set of DNA sequences, find a set of l-mers, one from each sequence, that maximizes the consensus score

• Input: A t x n matrix of DNA, and l, the length of the pattern to find

• Output: An array of t starting positions s = (s1, s2, …, st) maximizing Score(s, DNA)

• Compute the scores for each possible combination of starting positions s

• the best score will determine the best profile and the consensus pattern in DNA

• The goal is to maximize Score (s, DNA) by varying the starting positions si, where si = [l, …, n-l+1] for i = [1, …, t]

• Run time = O(ln^t)

• the weight matrix for the motif is initialized with a single n-mer subsequence, plus a small amount of background nucleotide frequencies

• for each n-mer in the target sequences, we calculate the probability that it was generated by the motif, rather than by the background sequence distribution

• expectation maximization then takes a weighted average across these probabilities to generate a more refined motif model

• the algorithm iterates between calculating the probability of each site based on the current motif model, and calculating a new motif model based on the probabilities

• procedure converging to a maximum of the log likelihood of the resulting model

• Given: set of sequences that are expected to have a common sequence pattern

• initial guess: location and size in each sequence: these parts are aligned

• the alignment provides an estimate of the base composition of each column

Step 1: expectation

• column-by-column composition of the site already available is used to estimate the probability of finding the site at any position of the seqs

• these probabilities are used in turn to provide new information as to the expected base distribution for each column

Step 2: Maximization

• new counts of bases for each position in the site found in step 1 are substituted for the previous set

Repeat until convergence, no more changes

Result:

• best location of the site in each seq

• best estimate of the base composition of each column in the site

• Locates one or more ungapped patterns in a single sequence of a series of sequences

• Three motif models:

  • one expected occurrence of motif per sequence

  • zero or one occurrence

  • any number of occurrences

• Can use prior knowledge

  • motif present in all or only some sequences

  • motif length

  • palindrome or not

  • expected patterns in individual motif positions (which bases are interchangeable)

• Stochastic implementation of expectation maximization

• Takes a weighted sample of subsequences (not ALL sequences)

• The motif model is initialized with a randomly selected set of sites, and every site in the target sequences is scored against this initial motif model

• At each iteration, the algorithm probabilistically decides whether to ass a new site and / or remoce an old site from the motif model, weighted by the binding probability for those sites

• The resulting motif model is then updated, and the binding probabilities recalculated

• Given sufficient iterations, the algorithm will efficiently sample the joint probability distribution of motif models and sited assigned to the motif, focusing in on the best fitting combinations

• Set of N sequences S1,…,Sn

• Task: find in each sequence mutually similar segments of specified width W

• Algorithm maintains two evolving data structures

  • Pattern description

    • Probabilistic model of residue frequencies for each position i from 1 to W, consisting of probabilities qi,1, …, qi,20

    • Background frequencies p1, …, p20 with which residues occur in sites not described by the pattern

  • Set of positions a_k (k=1,N) for the common pattern

• Task: find the “best” (most probable) pattern

  • Locate the alignment that maximizes the ratio of the pattern probability to background probability

• Initialization: random starting positions within various sequences

• Exclude sequence z at random

• Calculate pattern description q_ij and background frequencies p_i from the current positions a_k in all sequences excluding z

• every possible segment of width W within sequence z is considered as a possible instance of the pattern

• calculate:

  • the probabilities Q_x of generating each segment x according to the current pattern probabilities q_i,j

  • the probabilities P_x of generating these segments by the background probabilities p_i

• The weight Ax = Q_x / P_x is assigned to each segment x

• Select a random one, its position becomes the new a_z

• the more accurate pattern description in step 1, the more accurate the determination of its location in step 2, and vice versa

• Given random positions a_k, in step 2 the pattern description q_i,j will tend to favor no particular segment

• Once some correct a_k have been selected by chance, the q_i,j begin to reflect, albeit imperfectly, a pattern extant within other sequences

• This process tends to recruit further correct a_k, which in turn improve the discriminating power of the evolving pattern

Functional sequences evolve slower than nonfunctional ones

• Consider a set of orthologous sequences from different species

• Identify unusually well conserved regions

-> capable of identifying regulatory elements specific even to a single gene, as long as they are sufficiently conserved across many of the species considered

-> requires a reliable method for assembling the requisite collection of coregulated genes

• regions of non-coding DNA which regulate the transcription of neighboring genes. CREs are vital components of genetic regulatory networks, which in turn control morphogenesis, the development of anatomy, and other aspects of embryonic development, studied in evolutionary developmental biology.

• CREs are found in the vicinity of the genes that they regulate. CREs typically regulate gene transcription by binding to transcription factors. A single transcription factor may bind to many CREs, and hence control the expression of many genes (pleiotropy).

• CRMs are stretches of DNA, usually 100–1000 DNA base pairs in length, where a number of transcription factors can bind and regulate expression of nearby genes and regulate their transcription rates. They are labeled as cis because they are typically located on the same DNA strand as the genes they control as opposed to trans, which refers to effects on genes not located on the same strand or farther away, such as transcription factors. One cis-regulatory element can regulate several genes, and conversely, one gene can have several cis-regulatory modules. Cis-regulatory modules carry out their function by integrating the active transcription factors and the associated co-factors at a specific time and place in the cell where this information is read and an output is given.

• CREs are often but not always upstream of the transcription site. CREs contrast with trans-regulatory elements (TREs). TREs code for transcription factors

• Real genomic promoter sequence containing real annotated transcription factor binding sites

  • drawback: complete correct answer not known

• Artificially constructed sequences

  • drawback: “correct” stochastic process that nature uses unknown, bias will favor certain tools over others

• Solution chosen

  • TRANSFAC database

  • real transcription factors, their known binding sites, positions and orientations

  • three types of data:

    • binding sites of real promoter sequences (real)

    • randomly chosen promoter sequences from the same genome (generic)

    • sequences generated by a Markov chain of order 3 (markov)

• Cytoplasm

• Ribosomes

• Nucleoid

• Plasma membrane

• Cell wall (Peptidoglycan, Outer membrane)

• Capsule

Obtain new genomic DNA sequence -> 1. Translate in all six reading frames and compare to porten sequence database 2. Perform database similarity search of expressed sequence tag (EST) database of same organism, or cDNA sequences if available -> use gene prediction program to locate genes -> Analyze regulatory sequence in the gene

DNA transcribed to RNA translated to Protein

• Translation is handled by a molecular complex, the ribosome, which consists of both proteins & ribosomal RNA (rRNA)

• Ribosome reads mRNA & the translation starts at a start codon (the translation start site)

• With help of tRNA, each codon is translated to an amino acid

• Translation stops once ribosome reads a stop codon (the translation stop site)

• DNA segments upstream of transcripts that initiate transcription

• Promoter attracts RNA Polymerase to the transcription start site

Transcription starts at offset 0

• Pribnow Box (-10)

• Gilbert Box (-30)

• Ribosomal Binding Site (+10)

• The ribosome binds to the messenger RNA through basepairing to the 30S ribosomal subunit

• The binding site is the Shine-Dalgarno sequence (SD)

• The SD is a purine-rich sequence (consensus sequence: AGGAG) at the 5’ end of most prokaryotic mRNAs

• The SD is found 5-10 basepairs upstream from the start codon

• Dense Genomes

• Short intergenic regions

• Uninterrupted ORFs

• Conserved signals

• Abundant comparative information

• Complete genomes

• intrinsic evidence

  • sufficient ORF length. Long ORFs rarely occur by chance

  • Specific patterns of codon usage that are different from triplet frequencies in non-coding regions ('“coding potential”)

  • The presence of ribosome binding sites (RBS) ind the (-20)…(-1) regions upstream of the start codon that help to direct ribosomes to the correct translation start positions. A part of the RBS is formed by the pruine-rich Shine-Dalgarno (SD) sequence which is complementary to the 3’ end of the 16S rRNA

• extrinsic evidence

  • Similarity to known, especially experimentally characterized, gene products

Genomic Sequence -> Content-Based / Site-Based / Comparative

• Content-Based: Bulk properties of sequence: Open reading frames, Codon usage, Repeat periodicity, Compositional complexity

• Site-Based: Absolute properties of sequence: Consensus sequences, Donor and acceptor splice sites, Transcription factor binding sites, Polyadenylation signals, “Right” ATG start, Stop codons out-of-context

• Comparative: Inferences based on sequence homology: Protein sequence with similarity to translated product of query, Modular structure of proteins usually precludes finding complete gene

• GeneMark

• GLIMMER

• EcoParse

• …

• non-homogeneous Markov models for DNA regions that code for proteins or are complementary to them

• homogeneous Markov models for non-coding regions

• coding capactity of sliding windows is deduced throguh a Bayesian decision rule

• interpolated Markov Models

• takes into account DNA oligomers of varying length dependent on the local composition of the sequence

• hidden Markov models

• finds the maximum likelihood parse of a DNA sequence into coding and non-coding regions

• no sliding windows used

• Detect potential coding regions by looking at ORFs

  • A genome of length n is comprised of n/3 codons

  • Stop codons break genome into segments between consecutive Stop codons

  • the subsegments of these that start from the start codon (ATG) ar ORFs

  • ORFs in different frames may overlap

• Long open reading frames may be a gene:

  • at random, we should expect one stop codon every (63/3) ~= 21 codons

  • However, genes are usually much longer than this

  • A basic approach is to scan for ORFs whose length exceeds certain threshold

    • this is naive because some genes (e.g. some neural and immune system genes) are relatively short

• Factors that contribute to the unequal usage of codons in a coding sequence:

  • Unequal use of amino acids

  • Unequal number of codons for different amino acids

  • Codon preference

• If reading frame 1 encodes a protein, it will influence the following factors:

  • The amino acid composition in both the coding frame and the other two frames (frames 2 and 3)

  • The codon composition of all three frames

  • Positional base frequency: the frequency with which each of the four bases occupies each of the three positions within codons

• In protein coding regions every third base tends to be the same one much more often than by chance alone due to non-random use of codons

Method:

• Count the number of each base at every third position starting at positions 1, 2, and 3, and going to the end of the sequence window

• The assymetry statistic for each base is calculated as the ratio of the maximum count of the three possible reading frames divided by the minimum count for the same base plus 1

• The frequency of each base is the window is also calculated

• The resulting assymetry and frequency scores are converted to probabilities of being found in a coding region

• HMMs are able to model grammar

• Many problems in biological sequence analysis have a grammatical structure

• Example: the grammar of eukaryotic gene structure (simplified)

  • Exons and introns are “words”

  • Sentences: exon-intron-exon-…-intron-exon

  • Sentences can never end with an intron

  • Exon can never follow an exon without an intron in between

  • Other constraints…

How HMM generates a sequence of nucleotides:

• Process: random walk starting in the middle of any of the HMMs

  • begin at any state (e.g. central) and enter any of the rings

  • each such state transition has an associated probability

  • transitions out of the central state are chosen at random according to these probabilities (they sum to one)

  • subsequently, a new transition out of the central state is selected randomly and independently of the previous transition

• Choosing one of the 61 codon models repeatedly results in a ‘random gene’

• Gene termination

  • entry into one of the rings below the central state

  • low probability

  • one stop codon HMM generates both TAA and TGA,each according to its frequency of occurrence in E. coli, and the other TAG

• Intergenic region

  • produced independently and at random by looping in the state labelles ‘Intergene model’

• Start codon HMM

  • generates either ATG, GTG or TTG, each with the appropriate probability (TGG is very rare in E. coli)

• A transition is made back to the central state and the whole process repeated

• Result: a sequence of nucleotides that is statistically similar to a contig of E. coli DNA consisting of a collection of genes interspersed with intergenic regions

• A dynamic programming method known as the Viterbi algorithm

• Generates a parse of the contig: labels genes in the DNA by identifying portions of the path that begin with the start codon at the end of the intergenic ring, pass through several amino acid codon HMMs, and return to one of the stop codons at the beginning of the intergenic ring

• The model parses a gene in one direction only and thus finds all genes on the direct strand

• To locate genes on the opposite strand, the reverse complement is parsed

• GeneMark

• Glimmer

• 
  

Fifth-order Markov model

• uses sequence information from the previous five bases

• the frequency of hexamers is used to differentiate between coding and noncoding sequences

• limitation: there must be many representatives of each hexameric sequence in genes

• uses a Markov chain model to represent the statistics of coding and noncoding reading frames

• Uses dicodon statistics to identify codon regions

• fifth-order Markov chains consist of terms P(a|x1x2x3x4x5) which represent the probability of the sixth base of sequence x being a given that the previous five bases were x1x2x3x4x5

GeneMark text output:

GeneMark graphical output:

Homogeneous fifth-order Markov model, with the five states i-5 to i-1 generating state i. Each state corresponds to a nucleotide.

Three-periodic fifth-order Markov models, each modeling a different DNA reading frame. The probabilities are dependent on the position of the base within the codon. Each state is labeled with the codon position of the represented base.

• Three classes: class I, II, III

• differ not only in the statistical but in the biological sense

• intermediate codon usage bias

• maintain a low or intermediate level of expression

• some genes may occasionally be expressed at a very high level in environmentally triggered (rare) conditions

• high codon uasge bias

• highly expressed under exponential growth conditions

• low codon usage bias

• mainly belong to plasmids and insertions sequences

• also includes genes coding for fimbriae, major pili, many membrane proteins, restriction endonucleases and lambdoid phage lysogeny control proteins

• can be expressed at a fairly high level

• Protein-coding sequences in a bacterial genome may not be homogeneous in their compositional features

• Program using models trained on the bulk set of protein-coding sequences will be insensitive in finding genes of minor inhomogeneity classes

• If preliminary information on gene classes is available, class-specific models of protein-coding regions improve the performance of the gene-finding method

• possible solution:

  • use a set of “long” ORFs to obtain parameters of Markov models of protein-coding and noncoding regions

  • initial models used to score the putative sequences and to form the cluster seeds for the class-specific training sets

  • run clusterization procedure until convergence

  • obtain several sets of presumably coding sequences with more homogeneous compositional features

• Interpolated Markov Model

• finds a sufficient number of patterns by searching for the longest possible patterns that are represented in the known gene sequences up to a length of eight bases

• if there are not enough hexameric sequences, then pentamers or smaller may be more highly represented

• in other cases many representative patterns even longer than six bases may be found

• the longer the patterns, the more accurate the prediction

• combines porbability estimates from the different-sized patterns, giving emphasis to longer patterns and weighting more heavily the patterns that are well represented in the training sequences

• Gene prediction in bacterial genomes

• incorporation of extrinsic and intrinsic information

• Consideration of coding potential and ribosome-binding sites

• high accuracy

• precise identification of gene starts

• completely automatic prediction

• Promoter prediction

• Splice site prediction

• Coding potential

• Exon-intron structure

All the signals are short sequences that bind enzymes involved in this complex process

• a binding site for RNA polymerase and general transcription factors

• RNA polymerase I transcribes genes encoding ribosomal RNA

• RNA polymerase II transcribes genes encoding mRNA and certain small nuclear RNAs

• RNA polymerase III transcribes genes encoding tRNAs and other small RNAs

TBP - TATA binding protein

DPE - downstream promoter element

BRE - TFIIB recognition element

• 5’ Splicing Site = GU

• Branch Point = A

• 3’ Splicing Site = AG

The splicing reaction proceeds in two steps

1. step:

   • cleavage at the 5’ splice site (SS)

   • joining of the 5’ end of the intron to an A within the intron (the branch point)

   • this reaction yields a lariat-like intermediate in which the intron forms a loop

2. step:

   • cleavage at the 3’ splice site and simultaneous ligation of the exons

   • result: excision of the intron as a lariat-like structure

large assembly of 5 RNA and over 150 proteins that performs pre-mRNA splicing in eukaryotic cells (50-60S)

• most introns start with a GT dinucleotide (donor splice site)

• the 3’ end of introns is mostly AG dinucleotide (acceptor splice site)

• Locating occurances of AG and GT would identify all possible splice sites, but in addition there would be about 30 to 100 false predicted sites for every true one

• Key issue: the properties of the surrounding sequence

• There are extensive species specific sequence signals available to help detect splice sites

• Exon-intron structure of genes

• Models of gene grammar

• Models of exon-intron sequence

• Integrating intrinsic, extrinsic information

• the RNA splicing code

• Need the correct reading frame

  • introns can interrupt an exon in mid-codon

• There is no hard and fast rule for identifying donor and acceptor splice sites

  • signals are very weak

• Easy to predict all exons

• Report all sequences flanked by ..AG and GT.. as exons

• Sensitivity = 100%

• Specificity ~ 0%

• “isolated” methods

  • predict individual features

    • e.g. splice sites, coding regions

    • NetGene (Neural network)

• “integrated” methods

  • predict genes in context

    • “grammar” of genes

    • Certain elements in specific order are required

    • HMMgene

    • GenScan (HMM-based)

• very long stretches of DNA that are homogeneous in base composition

• are compositionally orrelated with the coding sequences that they embed

• isochore organization reflects some fundamental aspects of genome organization and evolution

• the nuclear genomes of vertebrates are mosaics of isochores

• isochores can be partitioned into a small number of families that cover a range of GC levels (30-60%)

determining the underlying mechanism driving the evolution of isochores is a major issue in understanding the organization of genomes

• gene density

• intron length

• replication timing

• recombination

• methylation pattern

• distribution of transposable elements

• Designed to predict complete gene structures

  • introns and exons, promoter sites, polyadenylation signals

• Incorporates:

  • Descriptions of transcriptional, translational and splicing signal

  • Length distributions (Explicit State Duration HMMs)

  • Compositional features of exons, introns, intergenic, C+G regions

• Larger predictive scope

  • Deal with partial and complete genes

  • Multiple genes separated by intergenic DNA in a seq

  • Consistent sets of genes on either / both DNA strands

• Based on a general probabilistic model of genomix sequences composition and gene structure

  • Assigns probability to every possible gene structure compatible with the sequence

  • uses dynamic programming to determine the most probable gene structure

• It is based on Generalized HMM (GHMM)

• Model noth strands at once

  • other models: predict on one strand first, then on the other strand

  • avoids prediction of overlapping genes on the two strands (rare)

• Each state may output a string of symbols (according to some probability distribution)

• Explicit intron / exon length modeling

• Special sensors for Cap-site and TATA-box

• Advanced splice site sensors

• all parameters of the model with reduced architecture are initialized

• GeneMark is run to determine a genomic sequence parse into “coding” and “non-coding” regions and the input genomic sequence is labeled according to this parse

• the subsets of uniformly labeled fragments are used for re-estimation of parameters

• Repeat until convergence

• Donor (acceptor): just two canonic GT (AG) dinucleotides

• Initiation (termination) sites: canonic (ATG, TGA, TAG, TAA)

• Sequences emitted by non-site states: uniform length distributions

• Non-coding: zero-oder Markov model, parameters estimated based on nucleotide frequencies in the genome

• Coding: different approaches, e.g. trained on long ORFs

• Comparison to EST databases

• Comparison of genomic sequence translated to protein database

• Spliced alignment

• Comparison of translated genomic sequence to translated genome / cDNA sequence

• Comparison of genomic sequence with homologous genomic sequence from close organisms

the alignment of a cDNA sequence to the locus that matches it best in its source genome - the presumed template for its transcription

The alignment of a cDNA or protein sequence to a homologous locus other than the one from which it was transcribed

• cDNA is created by reverse transcription of RNA to DNA, a process that often terminates before reaching the 5 end of the RNA

• Currently, the most abundand type of cDNA sequence in databases is obtained by creating a cDNA library and selecting clones at random for sequencing. This often results in high-copy-number mRNAs being overrepresented whereas low-copy-number mRNAs are missed entirely (each cDNA color represents a different gene)

• Within this category of ‘random clone’ cDNA, most of the available sequences are ESTs - single sequencing reads of typically 500-700 nucleotides that are taken from one end of the clone insert. Clones can be sequenced from both ends, but even two end-reads might not cover the entire insert

• genes in different organisms are similar

• the similarity-based approach uses known genes in one genome to predict (unknown) genes in another genome

• Given a known gene (or a protein) and a genome sequence, find a set of substrings of the genomic sequence whose concatenation best fits the gene

• find substrings that match a given gene sequence (candidate exons)

• define structure of candidate exons as (l, r, w) (left, right, weight defined as score of local alignment)

• look for a maximum chain of substrings

  • chain: a set of non-overlapping nonadjacent intervals

• Exon Chaining Problem: Given a set of putative exons, find a maximum set of non-overlapping putative exons

• Locate the beginning and end of each interval (2n points)

• find the “best” path

• Input: a set of weighted intervals (putative exons)

• Output: a maximum chain of intervals from this set

• this problem can be solved with dynamic programming in O(n) time

• Idea: combine information from mouse-human alignments with models of the DNA sequences that characterize splice donors and acceptors, start and stop codons and other biological features

• the first programs to outperform GENSCAN by using mouse-human comparison were TWINSCAN and SGP2

• their success resulted, in part, from using genome alignments to modify the scoring schemes of successful single-genome de novo gene predictors

• included models of conservation in splice sites and start and stop codons

• considered only the conservation in protein-coding regions

• Substitutions per synonymous site might not be a good predictor of the usefulness of informant genomes

  • the number of substitutions per synonymous site is calculated using only proteins that can be aligned

  • does not account for the loss of alignability at greater evolutionary distances

• for flies, a good predictor is the total number of mismatches in the whole-genome alignment divided by the length of the target genome

• when two genomes are too diverged to be useful, the number of mismatches is low because most of the sequence cannot be aligned; when they are too close to be useful, the number of mismatches is low because most of the sequence is unchanged. However, better models for the dependence of informant utility on divergence are needed

• When multiple mammalian genomes became available, using them to improve on the stat-of-the-art in de novo gene prediction proved more difficult than anticipated

• The first program that could make use of multiple informant genomes and could predict entire ORFs more accurately than TWINSCAN was N-SCAN (N-SCAN more accurate than TWINSCAN)

• Recently, a program called CONTRAST has extracted bigger gains in human gene prediction from multi-genome alignments. This work suggests that using both the mouse and the opossum, which is slightly more diverged, will give the best improvement over using the mouse alone

• Source: GeneBank, vertebrate divisions

• extract all genomic DNA sequences encoding at least one complete protein coding gene

• Discard sequences:

  • encoding at least one incomplete protein product

  • ambiguous location of protein coding regions

  • encoding protein coding genes in the complementary strand

  • encoding genes defined in other entries

  • pseudogenes

  • more than one alternatively spliced forms

  • encoding genes without introns

  • protein coding sequences not starting with ATG

  • no stop codon

  • genelerngth != 3*proteinlength

  • … etc

• Result: 570 genes (set ALLSEQ)

• Additionally: NEWSEQ (no similarity to sequences deposited before 1993)

• by nucleotide

  • Sensitivity / Specificity (Sn/Sp)

• by exon

  • Sn/Sp

  • Missed exons (ME), wrong exons (WE)

• By gene

  • Sn/Sp

  • Missed genes (MG), wrong genes (WG)

  • Average overlap statistics

Sn = TP / (TP + FN)

Sp = TP / (TP + FP)

JG = #Actual genes that overlap predicted genes / #Predicted genes that overlap one or more actual genes

• JG > 1, tendency to join multiple actual genes into one prediction

SG = #Predicted genes that overlap actual genes / #Actual genes that overlap one or more predicted genes

• SG > 1, tendency to split actual genes into separate gene predictions

• Nonfunctional sequences of genomic DNA that are originally derived from functional genes, but exhibit such degenerative features as premature stop codons and frameshift mutations that prevent their expression

• Characterized by close similarities to one or more paralogous genes, yet is non-functional (failure of transcription or translation)

• A fundamental feature of pseudogenes is that their nucleotide sequences differ from those of the paralogous functional genes at crucial points

• Two types of pseudogenes:

  • Conventional

  • Processed

• Gene that has been inactivated because its nucleotide sequence has changed by mutation

• many mutations have only minor effects on the activity of a gene but some are more important and it is quite possible for a single nucleotide change to result in a gene becoming completely non-functional

• Once a pseudogene has become non-functional it will degrade through accumulation of more mutations and eventually will no longer be recognizable as a gene relic

• Duplication of gene A results in two equivalent gene copies

• Selection pressure need be applies to only one gene copy (top) to maintain the presence of the original functional gene product

• the other copy (bottom), will continue to be expressed but, in the absence of selection pressure to conserve its sequence, will accumulate mutations (vertical bars) relatively rapidly

• It may acquire deleterious mutations and become a nonfunctional pseudogene which may continue to be expressed at the RNA level for some time, but which will eventually be transcriptionally silent (ψA)

• In some cases, however, the mutational differences may lead to a different expression pattern or other property that is selectively advantageous (A2)

• In the case of tandem gene duplication, subsequent sequence exchanges between the two copies (by mechanisms such as unequal crossover) will act as a brake on the rate of sequence divergence between the two gene copies

• Arises not by evolutionary decay, but by an abnormal adjunct to gene expression

• Derived from the mRNA copy of a gene by synthesis of a DNA copy which subsequently re-inserts into the genome

• Because a processed pseudogene is a copy of an mRNA molecule, it does not contain any introns that were present in its parent gene

• It also lacks the nucleotide sequences immediately upstream of the 5’-UTR of the parent gene, which is the region in which the signals used to switch on expression of the parent gene are located

• The absence of these signals means that a processed pseudogene is inactive

The majority of vertebrate pseudogenes are probably derived from functional genes

The majority of vertebrate pseudogenes are a result of retrotransposition of transcripts derived from genes that encode functional proteins

Pseudogenes persist in parts of the genome where they do not have a deleterious effect on fitness of the organism

Most pseudogenes undergo genetic drift and are never transcribed. By contrast, in some instances there appears to selectional pressures that prevent major changes to the pseudogene sequence. A few pseudogenes are involved in gene conversion and a few can be transcribed. Accordingly, not all pseudogenes are unequivocally functionless.

• Because of their high sequence similarity to the corresponding functional genes, pseudogenes can often interfere with PCR or in situ hybridization experiments intended for the functional genes

• Pseudogenes provide a molecular record on the dynamics and evolution of genomes

  • rate of nucleotide substitutions

  • the rate of DNA loss

• Improvement of the gene prediction and annotation efforts

• “True” processed pseudogene (high confidence)

  1. shares high sequence similarity with a known human protein from SWISS-PROT or TrEMBL

  2. when aligned with the functional human protein sequence, the alignment does not contain gaps longer than 60 bp

  3. covers >70% of the protein-coding sequence (CDS)

  4. contains frame disruptions such as frameshifts or in-frame stop codons

• “Putative” processed pseudogenes

  • conditions 1-3 fulfilles

  • condition 4 not fulfilles

  • probably young processed pseudogenes that were inserted into the genome so recently that they have not accumulated frame disruptions yet

• “Disrupted” processed pseudogenes

  • conditions 1, 3, 4 fulfilled

  • contition 2 not fulfilled

• the number of processed pseudogenes on each chromosome is proportional to the chromosome length (correlation coefficient 0.92)

• Consistent with the random nature of the retrotransposition process that gave rise to the processed pseudogenes

• As a comparison, the correlation between the numbers of the functional genes and chromosome length is much lower at 0.69

• defined as the ratio between the length of the predicted protein sequence from the pseudogene and the length of the closest matching protein sequence from SWISS-PROT or TrEMBL

• Altough 70% was used as the sequence completeness threshold to separate the processed psuedogenes from the pseudogenic fragments, the majority of the processed pseudogenes are practically full length

• There is a very significant correlation between the sequence completeness and the nucleotide sequence identities

• this is because the most recent pseudogenes should be more complete and have higher sequence identities than the older ones

Negative control, in which a repressor protein binds to the primary RNA transcript in tissue 2, thereby preventing the splicing machinery from removing an intron sequence

Positive control, in whcih the splicing machinery is unable to efficiently remove a particular intron sequence without assistance from an activator protein

• the assumption that each pre-mRNA follows a single splicing pathway was shown to be incorrect when alternative splicing was discovered

• there is also sex-specific alternative splicing, e.g. of sxl pre-mRNA

• is common in many eukaryotes

• the primary transcripts of some genes can follow two or more alternative splicing pathways, enabling a single transcript to be processed into related but different mRNAs and hence to direct synthesis of a range of proteins

• it is now believed that at least 35% of the genes in the human genome undergo alternative splicing

• some splice sites are used only some of the time

• Types of AS:

  • constitutive: more than one product is always made from the transcribed gene

  • regulated: different forms are generated at different times, under different conditions, or different cell tissue types

• add new protein parts: 75% of alternative splicing involves the protein coding region, in addition to truncations you can change overall protein sequence

• Influence RNA function: alternative splicing does occur to alter 5’ and 3’ UTR regions - proposed roles in subcellular localization and RNA stability

• Coordinated Regulation of Biological Events

  • Neuron development (Dscam)

  • Channel activity associated with hearing (slo)

  • Muscle contraction

  • Neurite growth

  • Cell differentiation

  • Apoptosis

• Alter protein binding properties, e.g. receptor / ligand

• Alter intracellular localization, e.g. membrane insertion

• Alter extracellular localization, e.g. secretion

• Alter enzymatic or signaling activities

• Alter protein stability, e.g. inclusion of cleavage sites

• Insertion of post-translation modification domains

• Change ion channel properties

• Insertion and deletion in ESTs relative to mRNA are identified as potential alternative splices

• Splices are identified and intronic splice junction donor and acceptor sites are checked

  • Alternative splices are detected when two splices are mutually exclusive (intron inclusions are not identified as alternative splices). As intronic seqeunces at splice junctions are highly conserved, they can be used to verify candidate splices

Computation of splice junction difference ratio (SJD).

The SJD value for a pair of transcripts is computed as the number of splice junctions in each transcript that are not represented in the other transcript, divided by the total number of splice junctions in the two transcripts, in both cases considerung only those splice junctions that occur in portions of the two transcripts that overlap.

• Specific human tissues such as the brain, testis and liver, make more extensive use of AS in gene regulation

• These tissues have also diverged most from other tissues in the set of spliced isoforms they express

• Generate mRNA isoform sequences

• Generate protein isoform sequences

• find annotations from databases like Swissprot, by homology

• Search protein domain databases like SMART, PFAM

• Goals:

  • quantify the effect of alternative splicing on protein domains

  • map alternative splicing regions on protein functional and structural units

• Approach:

  • extract all alternatively spliced protein isoforms in higher organisms with fully sequenced genomes (H. sapiens, M. musculus, D. melanogaster, C. elegans)

  • 4804 splicing variants of 1780 proteins

  • map the alternatively spliced regions onto protein domain annotations of the InterPro resource

• Alternative Splicing Gallery (ASG): viele Daten in komprimierter Darstellung: je dicker der Pfad desto mehr

defined as the fraction of the gene’s transcripts that include this exon

• Constitutive exons:

  • Exons included in every transcript of a gene

  • are almost always found to be conserved in the other genome

• major-form exons:

  • included in the majority of transcripts

  • are almost always found to be conserved in the other genome

• minor-form exons:

  • included in only a minority of transcripts

  • are mostly not conserved in the other genome

There are different categories of DNA sequence variations

• Single nucleotide polymorphisms (SNiPs)

  • agcttctatct

  • agcttctctct

• Single Tandom Repeat Polymorphisms (STRs)

  • agtctctctctctctctctctctctatacg : (CT)_11

  • agtctctctctctctctctatacg : (CT)_8

• Insertions / Deletions (Indels)

• SNP occurs when a single nucleotide replaces one of the other three nucleotide letters

• e.g. the alteration of the DNA segment AAGGTTA to ATGGTTA

• Most SNPs are found outside of “coding seqs”

=> SNPs found in a coding seq are of great interest as they are more likely to alter function of a protein

• SNPs are the most common type of genetic variation in humans. They account for 90% of the variation between individuals

• Most are neutral polymorphisms. Some cause disease

• The density of SNPs is about 1 every 100 to 300 bases

• SNPs may occur anywhere

  • in coding regions (cSNPs)

  • in introns

  • in regulatory regions of genes

  • in intergenic regions

• In coding regions, changes may be synonymous or nonsynonymous

SNPs may be informative with respect to disease:

1. Functional variation. A SNP associated with a nonsynonymous substitution in a coding region will change the amino acid sequence of a protein

2. Regulatory variation. A SNP in a noncoding region can influence gene expression

3. Association. SNPs can be used in whole-genome association studies. SNP frequency is compared between affected and control populations

One of the forms of a variant that occurs at a given locus

In a region of the genome that is transcribed

The organisation of variation across a chromosome (Gesamtzahl and Mutationen ?)

A variant alters a codon to substitute one amino acid for another

A mutation that introduces a stop codon

A variation where the least common allele occurs less than 1 per cent in the population

An inherited single nucleotide substitution between individuals of a species. Commonly defined as having the least frequent allele occur at a rate greater than 1 per cent in a population. The most common form of human variation.

• Coding SNPs (cSNP): Positions that fall within the coding regions of genes

• Regulatory SNPs (rSNP): Positions that fall in regulatory regions of genes

• Synonymous SNPs (sSNP): Positions in exons that do not change the codon to substitute an amino acid

• Non-synonymous SNPs (nsSNP): Positions that incur an amino acid substitution

• Intronic SNPs (iSNP): Positions that fall within introns

by sequencing DNA and comparing the sequences

Online Mendelian Inheritance in Man

An online catalog of Human genes and genetic disorders

• a nonsynonymous or msisense variant is a single base change in a coding region that causes an amino acid change in the corresponding protein

• If a nonsynonymous variant alters protein function, the change can have drastic phenotypic consequences

• Most alterations are deleterious and so are eventually eliminated through purifying selection

• However, beneficial mutations can sweep through the population and become fixed, thus contributing to species differentiation

• Online Mendelian Inheritance in Man (OMIM)

• Human Gene Mutation Database (HGMD)

In both databases, nonsynonymous changes account for approximately half of the genetic changes known to cause disease

Although these databases contain information primarily concerning disorders caused by single Mendelian lesions, it is likely that nonsynonympus changes will play a similarly important role in complex diseases because of their potentially large impact

• Use the matrix of neighbor-dependent nucleotide mutation rates

  • calculated on the basis of substitutions in aligned human gene sequences

  • the relative mutation rates were calculated for the four nucleotides in all 16 possible 5’ and 3’ neighborhoods

• Obtaining the expected amino-acid mutation frequencies for a given collection of genes

  • simulate all possible single nucleotide mutations with appropriate rates

  • record the corresponding amino-acid changes

where the summation is over all amino-acid types n in the alignment; P(n) is the probability of the amino acid n in the column corresponding to mutation; Q(n) is the probability of the amino acid n in all columns of the multiple sequence alignment

a measure of dissimilarity between a human amino acid and the residues seen at the same site in homologs

where D(A,B) is the Grantham measure of chemical dissimilarities between amino-acid residues A and B, Human_RES is the human residues at the mutation site, RES(i) is the amino acid from the i-th aligned sequence homolog at the mutation site, and n is the number of aligned sequences

• ‘descriptor‘: solvent accessibility or evolutionary conservation of the mutation site

• P(descriptor|disease): the probability that a disease mutation has a given descriptor value

• P(descriptor): the probability that a random mutation (disease or non-disease) has a given descriptor value

• P(disease): the probability that a random mutation will cause a genetic disease

• Importantly, because P(disease) is unknown, we can only estimate P(disease|descriptor) up to a constant (assuming certain P(disease) value). Consequently, P(disease|descriptor) is a relative mutation probability. The probability that a random mutation has a given descriptor value P(descriptor) can be estimated by simulating random single-nucleotide mutations using the expected amino-acid mutation frequencies

• Assumptions:

  • each class of protein has a core structure that is defined by internal residues

  • external, solvent-contacting residues contribute to the stability of the structure, are of primary importance to function, but do not determine the architecture of the core portions of the polypeptide chain

• Goal: supply a list of permitted sequences of internal residues compatible with a known core structure

• the template is derived using the fixed positions for the main-chain and beta-carbon atoms in the test structure and selected stereochemical rules

• use of two packing criteria:

  • avoidance of steric overlap

  • complete filling of available space

• Additional criteria

  • potential polar group interactions

  • disulfide bonds

  • possible burial of charges

• Side-chain rotamer library

• Templates help in deciding whether a sequence of unknown tertiary structure fits any of the known core classes

• Size changes in the hydrophobic core

• Introduction of buried charged residues

• Disruption of protein-protein interactions

• Disruption of a hydrogen-bonding network

• Interference with DNA binding

• Breaking disulphide covalent bonds

• Mutation of catalytic residues

• Mutation of metal-binding residues

• Disrupting quartenary structure

• Input: Protein sequence and AAS, Protein sequence alignment and AAS, dbSNP id, or protein id

• Output: Score ranges from 0 to 1, where 0 is damaging and 1 is neutral

• Algorithm: Using sequency homology, scores are calculated using position-specific scoring matrices with Dirichlet priors

SIFT: sort intolerant from tolerant substitutions

• takes a query sequence and uses multiple alignment information to predict tolerated and deleterious substitutions for every position of the query sequence

• Procedure:

  • search for similar sequences (BLAST)

  • choose closely related sequences that may share similar function

  • obtains multiple alignment

  • calculate normalized probabilities for all possible substitutions at each position

• Substitutions at each position with normalized probabilities less than a chosen cutoff are predicted to be deleterious; those greater than or equal to the cutoff are predicted to be tolerated

PolyPhen: prediction of functional effect of human nsSNPs

• Input: Protein sequence and AAS, dbSNP id, or protein id

• Output: Score ranges from 0 to a positive number, where 0 is neutral, and a high positive number is damaging

• Algorithm: Uses sequence conservation, structure to model position of amino acid substitution, and SWISS-Prot annotation

PolyPhen: Structural consequences of the respective non-synonymous mutations in proteins

• Map known disease mutations onto known three-dimensional structures of proteins

• Compare results with a control set of substitutions observed between these proteins and their closely related homologs from other species that are unlikely to cause severe effects on the phenotype

• Map a large number of non-synonymous SNPs onto protein structures

  • thought to be neutral

  • or to be the cause of only minor phenotypic effects

• Goal: to obtain a lower limit estimate for the quantity of non-synonymous SNPs that might have phenotypic effects

  • How many SNPs are associated with multifactorial human disorders?

• Disease-causing mutations are much more likely to occur at sites with low solvent accessibility

  • disease-causing mutations often affect intrinsic structural features of proteins

• ~70% of the disease-causing mutations are located in sites likely to be structurally and functionally important, namely sites with

  • <5% solvent accessibility

  • beta-strands

  • active sites

  • sites involved in disulphide bonds

  • evolutionarily conservative sites

• Folding

• Interaction sites

• Solubility

• Stability

Check if substitution is

• in an annotated active or binding site

• affects interaction with ligands present in the crystallographic structure

• leads to hydrophobicity or electrostatic charge change in a buried site

• destroys a disulphide bond

• affects the protein’s solubility

• inserts proline in an alpha-helix

• is incompatible with the profile of amino acid substitutions abserved at this site in the set of homologous proteins

(Empirical rules, work well!)

Disease variants and protein structure database

Genetic tolerance predictors

• amino acid substitutions

• Synonymous variations

• Insertions and / or deletions

• Noncoding variations

Specific (tolerance) predictors for

• Genes

• Proteins

• Families

• Functional complexes

• Diseases

Mechanism / effect predictors

• DNA

  • Transcription factor binding sites

• RNA

  • Splicing

  • miRNA targets

• Protein

  • Aggregation

  • Solubility

  • Stability

  • Localization

  • Post translation modification

  • Electrostatics

PolyPhen, PolyPhen-2, SIFT

• functional RNA

• essentially synonymous with non-coding RNA

• MicroRNA

• putative translational regulatory gene family

• Non-coding RNA

• all RNAs other than mRNA

• ribosomal RNA

• small interfering RNA

• active molecules in RNA interference

• small nuclear RNA

• includes spliceosomal RNAs

• small non-mRNA

• essentially synonymous with small ncRNAs

• small nucleolar RNA

• most known snoRNAs are involved in rRNA modification

• small temporal RNA

• for example, lin-4 and let-7 in C. elegans

transfer RNA

• Structure comparison & classification

• Structure-based alignments

• RNA features, predicting secondary structure

• RNA databases

• RNA motif searching

• Specialized RNA gene finding

• Generalized RNA gene finders

• the codons in an mRNA molecule do not directly recognize the amino acids they specify

• the translation of mRNA into protein depends on adaptor molecules that can recognize and bind both to the codon and, at another site on their surface, to the amino acid

• these adaptors consist of a set of small RNA molecules known as transfer RNAs (tRNAs), each about 80 nucleotides in length

• Two regions of unpaired nucleotides situated at either end of the L-shaped molecule are cruicial to the function of tRNA in protein synthesis

  • Anticodon: a set of three consecutive nucleotides that pairs with the complementary codon in an mRNA molecule

  • Short single-stranded region at the 3’ end of the molecule; this is the site where the amino acid that matches the codon is attached to the tRNA

• the genetic code is redundant

  • several different codons can specify a single amino acid

• two possible implications:

  • more than one tRNA for many of the amino acids

  • some tRNA molecules can base-pair with more than one codon

• Both are true!

  • some amino acids have more than one tRNA

  • some tRNAs are constructed so that they require accurate base-pairing only at the first two positions of the codon and can tolerate a musmatch (or wobble) at the third position

• In bacteria, wobble base-pairings make it possible to fit the 20 amino acids to their 61 codons with as few as 31 kinds of tRNA molecules

• the exact number of different kinds of tRNAs differs from one species to the next

• RNA bases: A, C, G, U

• Canonical Base Pairs:

  • A-U (2 hydrogen bonds)

  • G-C (3 hydrogen bonds)

  • G-U (wobble pairing)

• Bases can only pair with one other base

• XYU and XYC always encode the same amino acid

• XYA and XYG usually do

• Francis Crick surmised from these data that the steric criteria might be less stringent for pairing of the third base than for the other two

• Ionisine in the wobble position can become paired with A, U, C

• Bacteria, archaea, and eucaryotes have available to them a 21st amino acid that can be incorporated directly into a growing polypeptide chain

• is essential for the efficient function of a varuety of enzymes, contains a selenium atom in place of the sulfur atom of cysteine

• is produced from a serine attached to a special tRNA molecule that base-pairs with the UGA codon, a codon normally used to signal a translation stop

• requires a selenocysteine-specific translation factor

• RNA secondary structure: intermediate step in the formation of a 3D structure (like proteins)

• RNA secondary structure is primarily the double-stranded regions of the molecule formed by folding the single-stranded molecule back to itself to form loops

• A run of bases downstream in the RNA sequence must be complementary to another upstream run

  • Watson-Crick base pairing between the complementary nucleotides G/C and A/U

  • Non-Watson-Crick G/U wobble base pairs

• Complementary sequence in RNA molecules maintain RNA secondary structure

• the double-stranded regions will most likely form where a series of bases in the sequence can pair with a complementary set elsewhere in the sequence

• more base pairing = increased energetic stability

• Single-stranded regions destabilize neighboring double-stranded regions

• Linear RNA strand folded back on itself to create secondary structure

• Corcularized representation uses this requirement

  • Arcs represent base pairing

• Primary sequence based techniques that generally work quite well for protein sequence analysis are not well suited for studying RNA

• Most functional RNAs appear to be selected more for maintenance of a particular base-paired structure than conservation of primary sequence

• RNA secondary structure induces strong pairwise correlation in RNA sequence, usually manifested as Watson-Crick complementarity

• RNA sequence analysis therefore must work with this pattern of correlation in addition to primary sequence conservation

• More flexible methods needed:

  • capture both primary and secondary structure consensus information

  • flexibly scoring insertions, deletions, and mismatches

• Applications:

  • database searching for new RNAs

  • multiple RNA sequence alignment

• Ab initio prediction from sequence

• Two possible approaches:

  • Energy minimization methods: choose complementary sequence sets that provide the most energetically stable molecules

    • advantage: accomodation of experimental data and alignment data

    • disadvantages: no tertiary interactions predicted, very computationally expensive

  • take into account patterns of base-pairing that are conserved during evolution

    • patterns of covariation on RNA molecules are a manifestation of secondary structure

    • the computational challenge is to discover these covariable positions against the background of other sequence changes

    • advantages: simple, both secondary and tertiary interactions predicted

    • limitation: need a sufficient number of sequences that can be aligned

• for single-stranded RNA repeats represent regions that can potentially self-hybridize to form double strands

• dot matrix analysis:

  • first axis: direct strand 5’ -> 3’

  • second axis: complementary strand 5’ -> 3’

  • find identities

• Bases pair in order to form backbones and determine the secondary structure

• aligning bases based on their ability to pair with each other gives an algorithmic approach to determining the optimal structure

• Scoring system

  • +1 per base pair

  • 0 anything else

• Calculate the best structure for a continuous subsequence from i to j in a complete sequence of length N

• Key idea: the optimal score S(i,j) can be defined recursively in terms of optimal scores of smaller subsequences

• i,j are a base pair, added on to a structure for i+1…j-1

  • Score = +1

• i is unpaired, added on to a structrue for i+1…j

  • Score = 0

• j is unpaired, added on to a structrue for i…j-1

  • Score = 0

• i,j are paired, but not to each other: the structure for i…j adds together substructures for two sub-sequences, i…k and k+1…j (bifurcation)

  • Optimal Score S(i,k) is independent of anything going on in k+1,…j, and vice versa

  • S(i,k) + S(k+1,j) is the score of the optimal structure on i,j conditional on i,j being paired, but not to each other

• Optimal score is the maximum of all 4 possibilities

• Tabulate the scores S(i,j) in a triangular matrix

• Initialize on the diagonal: subsequences of length 0 or 1 have no base pairs, so S(i,i) = S(i,i-1) = 0

• By convention, the i, i-1 cells represent zero length sequences; the recursion must never access an empty matrix

• Base pair maximization will not necessarily lead to the nost stable structure

  • may create structure with many interior loops or hairpins which are energetically unfavorable

• Comparable to aligning sequences with scattered matches - not biologically reasonable

• Pseudoknots cause a breakdown in the Dynamic Programming Algorithm

• In order to form a pseudoknot, checks must be made to ensure base is not already paired - this breaks down the recurrence relations

• the most likely structure - energetically most stable

• energy associated with any position in the structure is only influenced by local sequence and structure

  • Energy associated with a particular base pair in a double-stranded region is influenced only by the previous base pair

• Thermodynamic Stability

  • Estimated using experimental techniques

  • Theory: Most stable is the most likely

• No Pseudoknots due to algorithm limitations

• uses dynamic programming alignment technique

• Attempts to maximize the score taking into account thermodynamics

• MFOLD and ViennaRNA

• Every base is compared for complementarity to every other base

• the energy of each predicted structure is estimated by the nearest-neighbor rule:

  • sum the negative base-stacking energies for each pair of bases in the predicted double-stranded regions

  • add positive energies of destabilizing (unpaired) regions

• The complementary regions are evaluated by a dynamic programming algorithm to predict the most energetically stable molecule

• Obtaining dynamic programming matrix values

  • consider the minimum energy values obtained by all previous complementary base pairs

  • decrease by stacking energy

  • increase by the destabilizing energy associated with noncomplementary bases

• Repeat for the entire matrix

• The increase depends on the type and length of loop that is introduced by the noncomplementary base pair

  • internal loop

  • bulge loop

  • hairpin loop

• derives energy dot plot

• the method can be instructed to find structures within a certain percentage of the minimum free energy

• Describes bith the secondary structure and the primary sequence consensus of an RNA

• Can be applied to several RNA analysis problems

  • consensus secondary structure prediction

  • multiple sequence alignment

  • database similarity searching

• Covariance models are constructed automatically

  • from existing RNA sequence alignments

  • even from initially unaligned example sequences

• Iterative training procedure

• Optimal algorithm for RNA secondary structure prediction based on pairwise covariations in multiple alignments

-> Covariation ensures ability to base pair is maintained and RNA structure is conserved

• Need to allow for insertions, deletions, and mismatches to describe a family of related RNAs

• Each node describes columns in a multiple alignment instead of bases in an individual sequence

• Specific base assingments are replaced with symbol emission probabilities assigned to the 16 possible pairwise nucleotide combinations or 4 singlet nucleotides

• first step is to calculate a multiple sequence alignment

• Requires sequences be similar enough so that they can be initially aligned

• Sequences should be dissimilar enough for covarying substitutions to be detected

• can capture all pairwise interactions

• cannot capture other tertiary structural interactions

  • non-pairwise interactions (base triples)

  • non-nested pairs (pseudoknots)

• The primary sequence can be regenerated (emitted) by a traversal of the tree from root to leaves and left to right

• inflexible description of a single RNA

• to accomodate minor variations in structure such as insertions and deletions, each node is replaced with a number of different states with particular properties

  • ‘Match’ states (MATP (pair), MATL (left), MATR (right)) account for the conserved consensus columns of an alignment

  • ‘Insert’ states (INSL, INSR) account for insertions relative to the consensus

  • ‘Delete’ states (DEL) emit nothing and allow for the possibility of deletions relative to the consensus

  • MATL and MATR singlet states are included in pairwise nodes to allow for the possibility that either side of a consensus base pair may be deleted to leave a bulge

• States are connected to each other by state transition probabilities, which are scores for transiting to one of several possible new states

• After entering an insert state, there is a state transition probability for staying in it (corresponds to a gap-open and gap-extend penalty)

• Special nonemitting states describe the tree structure itself

  • bifiurcation states with forced transitions into two new states

  • dummy begin and end states

• the final model consists of

  • a number of states M

  • symbol emission probabilities P

  • state transition probabilities T

• Probabilistic machine that generates representative sequences of an RNA family

• Describes an RNA multiple sequence alignment in terms of both primary sequence consensus and pairwise covariations induced by consensus secondary structure

• Needs to be well trained

• Not suitable for searches of large RNA and for database searches

  • Structural complexity of large RNA cannot be modeled

  • Runtime

  • Memory requirements

• Can be used for scanning candidate RNAs identified by other methods

• A family of 21 - 25-nucleotide small RNAs

• Function: altering the expression levels of a diverse repertoire of genes in a sequence-dependent manner

  • at the transcriptional or post-transcriptional level

  • regulate many aspects of development and physiology

• Large family: hundreds of members in worms, flies, plants and mammals…

• Primary miRNAs (pri-miRNAs) are initially processed by the Drosha/Pasha complex (‘microprocessor’) into ~60-70 nucleotide precursor miRNAs (pre-miRNAs) in the nucleus

• These pre-miRNAs are transported into the cytoplasm by Exportin 5

• in a next step, they are cleaved by Dicer into an imperfect double-stranded duplex

• one strand of this duplex is incorporated into the RISC (RNA-induced silencing complex)

• This complex binds to the target gene and will lead to tranlational repression

• However, in some cases, miRNAs regulate gene expression by mRNA cleavage rather than by translational repression

• RNA-induced silencing complex

• include

  • Dicer

  • Argonaute proteins

  • TRBP (HIV-1 transactivation responsive element (TAR) RNA-binding protein)

  • double-stranded (ds) RNA-binding protein (PACT)

• miRNAs are encoded in genomes either as independent transcriptional units with their own promoters (solo miRNAs) or as clusters of several miRNA genes transcribed as a single pri-miRNA

• A substantial fraction of animal miRNA genes are located in introns of protein-coding genes

• Whereas some intronic miRNAs have antisense orientation relative to their host genes and thus do not directly depend on host gene transcription, sense-oriented intronic miRNAs are thought to be processed as part of the host-gene mRNA and their expression correlates with that of their hosts

• Mirtrons, which are encoded in introns, do not rely on Drosha processing and instead use the splicing machinery to generate pre-miRNAs

• Splicing can result in tailed mirtrons, which require additional trimming by the exosome to produce a functional pre-miRNA

• family of proteins that contain two conserved domains termed PAZ and PIWI

• Multiple paralogs are typically present in each organism

• Argonaute proteins are crucial for the maturation and function of microRNAs (miRNAs) and are essential for RNA interference

• elF2C2 is a human Argonaute protein

• RNAse III-type nuclease that also contains RNA helicase, PAZ and double-stranded RNA (dsRNA)-binding domains

• Dicer processes linear, dsRNA into small interfering RNA (siRNA) duplexes and also excises mature miRNAs from pre-miRNAs

• ribonucleoprotein complex containing mirRNAs, and Argonaute protein (elF2C2) and the proteins Gemin3 (and RNA helicase) and Gemin4

• ~22nt noncoding RNAs derived from endogenous genes. Processed from one of the strands of longer (~75nt) hairpin-like precursors termed pre-miRNAs

• miRNAs assemble in complexes termed miRNPs and recognize their mRNA targets by antisense complementarity. If the complementarity is extensive, the target mRNA is cleaved and the miRNA acts as an siRNA; if the complementarity is partial, the translation of the targte mRNA is repressed

• argonaute protein bound to miRNAs or siRNAs

• Multisubunit nuclease that directs target RNA destruction in RNA interference (RNAi)

• the core components of RISCs are siRNAs and Argonaute proteins

• Initially defined as a technique in which experimental introduction in C. elegans of dsRNA homologous to a target mRNA led to degradation of the targeted mRNA

• More broadly defined as degradation of target mRNAs by homologous siRNAs

• ~22 to 25nt RNAs derived from processing of linear dsRNA

• siRNAs assemble in complexes termed RISCs and target homologous RNA sequences for endonucleolytic cleavage

• Synthetic siRNAs also incorporate RISCs and cleave homologous RNA sequences

• miRscan

• miRseeker

• srnaloop

• …

• Slide a 100-nt window along both strands of the C. elegans genome, discarding

  • repetitive elements

  • segments with skewed base compositions not observed in known miRNA stem loops

  • segments overlapping with annotated coding regions

• Fold the window with the secondary structure-prediction program RNAfold

• Identify predicted stem-loop structures with a minimum of 25bp and a folding free energy of at least 25 kcal/mole

• Identify similar C. briggsae sequences by BLAST and fold them by RNAfold

• This procedure yielded ~40.000 pairs of potential miRNA hairpins

• For each pair of potential miRNA hairpins, generate a consensus C. elegans / C. briggsae structure

Seven features derived from the consensus hairpin structure (example for mir232):

• base pairing of the miRNA portion of the fold-back

• base pairing of the rest of the fold-back

• stringent sequence conservation in the 3’ half of the miRNA

• sequence biases in the first five bases of the miRNA (especially a U at the first position)

• a tendency toward having symmetric rather than asymmetric internal loops and bulges in the miRNA region

• the presence of two to nine consensus base pairs between the miRNA and the terminal loop region, with a preference for 4-6 bp

-> miRNA base pairing; extension of base pairing; 5’ conservation; 3’ conservation; bulge symmetry; distance from loop; initial parameter

-> for a given feature i with a value x_i, MiRsan assigns a log-odds score -> the overall score assigned to a candidate miRNA is simply the sum of the log-odds scores for the seven features

• 2300 true human mature miRNAs

• TargetScan

  • thermodynamics-based modeling of RNA:RNA duplex interactions

  • comparative sequence analysis

• Input:

  • miRNA that is conserved in multiple organisms

  • a set of orthologous 3’ UTR sequences from these organisms

• search the UTRs in the first organism for segments of prefect Watson-Crick complementarity to bases 2-8 of the miRNA: “miRNA seed” and “seed matches”

• extend each seed match with additional base pairs to the miRNA as far as possible in each direction, allowing G:U pairs, but stopping at mismatches

• optimize basepairing of the remaining 3’ portion if the miRNA to the 35 bases of the UTR immediately 5’ of each seed match using the RNAfold program

• assign a folding free energy G to each such miRNA:target site interaction

• assign a Z score to each UTR

• sort the UTRs in this organism by Z score and assign a rank R_i to each predict as targets those genes for which both Z_i >= Z_c and R_i <= R_c for an orhtologous UTR sequence in each organism, where Z_c and R_c are pre-chosen Z score and rank

• Predictions have yielded larger and more variable precursor miRNA molecules for plants than for animals

• The Drosha gene that processes the primiRNA to the pre-miRNA in animals is absent from plant genomes

• In plants, the Dicer-like 1 (DCL1, a RNase-III-like protein) appears to catalyze the processing of the primary miRNA transcript to form the miRNA:miRNA* complex

• Source data consisting of miRNAs and 3’ UTRs are processed initially by the miRanda algorithm, which searches for complementarity matches between miRNAs and 3’ UTRs using dynamic programming alignment and thermodynamic calculation.

• all results are then post-processed by first filtering out results not consistently conserved accoridng to target sequence similarity with D. pseudoobscura and A. gambiae, then by sorting and ranking all remaining results.

• Finally, all miRNA targte gene predictions are annotated using data from FlyBase and stored for further analysis

• One miRNA can target more than one gene (multiplicity). Some miRNAs appear to be very promiscuous, with hundreds of predicted targets, but most miRNAs control only a few genes

• One gene can be controlled by more than one miRNA (cooperativity). Some target genes appear to be subject to highly cooperative control, but most genes do not have more than four targets sites. Although specific values are likely to change with refinement of target prediction rules, the overall character of the distribution may well be a biologically relevant feature reflecting system properties of regulation by miRNAs.

• the benchmark set

• a database for experimentally supported miRNA-target gene interactions, reports aroung 130 mammalian entries

• TarBase also reports the experiments that were performed to provide support for each miRNA-target gene interaction, which range from in vitro reporter silencing assays to in vivo miRNA overexpression studies

• only the subset of mammalian miRNA-target gene interactions in TarBase was considered for which the strongest experimental evidence - a direct miRNA effect - has been shown

  • 84 such interactions involving 32 different miRNAs

• Current

  • all 84 interactions

• Unbiased current

  • interactions that were not chosen for verification during the experimental testing phase of the program(s) or were not chosen for verification based on a specific run of the program(s)

• Conserved current

  • 61 interactions that meet the conservation requirements of the programs

• Conserved unbiased current

  • all of the interactions in the corresponding unbiased current data set except those that are not conserved in other species

• the microRNA database

• microRNA sequences, targets and gene nomenclature

sequences that are unique: there is only one copy in a haploid genome

sequences that are present in more than one copy in each genome

• moderately repetitive DNA, complex repeats: short sequences (10-1000 copies, typically dispersed throughout the genome)

• highly repetitive DNA, simple repeats: very short sequences (<100 bp), many thousand of copies in the genome, often organized as long tandem repeats

• tandemly repeated DNA (minisatellites, microsatellites, centromeric and telomeric repeats)

• long interspersed nuclear element (LINE) retro(trans)posons

• short interspersed nuclear element (SINE) retro(trans)posons

• autonomous and nonautonomous endogenous retroviral elements

• autonomous and nonautonomous DNA transposons

-> jede 2. Base steckt in so einem repeat: 50% des Genoms (in Pflanzen 80% sogar)

• Microsatellites

• Minisatellites

• ‘Cryptically simple repeats’: result from reshuffling of a limited number of DNA sequence motifs in various orientations

• ‘Low-complexity repeats’: usually derived from other simple repeats, although their periodic character may be obscured by mutations

• Satellite and telomeric repeats

• Microsatellites

  • from one to a dozen base pairs

  • examples: (A)n, (CA)n, (CGG)n

  • these may be formed by replication slippage

• Minisatellites: a dozen to 500 base pairs

• Simple sequence repeats of a particular length and composition occur preferentially in different species

• In humans, an expansion of triplet repeats such as CAG is associated with at least 14 disorders (including Huntington’s disease)

• Micro- and minisatellites are often polymorphic and the biological mechanisms behind this phenomenon are thought to be different for the two groups. Owing to the polymorphism and relatively uniform distribution in chromosomal DNA, micro- and minisatellites are ampng the most informative genetic markers

• a separate category of tandem repeats is represented by satellite and telomeric repeats

  • unlike micro- and minisatellites, these repeats are confined to well-defined chromosomal regions

  • satellites are primarily found in the centromeric regions of chromosomes

  • telomeric repeats occupy chromosomal ends, or telomeres

• Example of a telomeric repeat: TTAGGG (in humans)

• Centromeric repeats (e.g. a 171 base pair repeat of a satellite DNA in humans)

• Such repetitive DNA can span millions of base pairs, and it is often species-specific

• Simple sequence repeats (SSR) are perfect (or slightly imperfect) tandem repeats of k-mers. Microsatellites have k=1 to 12, while minisatellites have k from about a dozen to 500 base pairs

• Micro- and minisatellites comprise 3% of the genome

• AC, AT, and AG are the most common dinucleotide repeats

• Constitute ~45% of the human genome

• Derived from biologically active ‚transposable elements‘ (TEs)

• Involve RNA intermediates (retroelements) or DNA intermediates (DNA transposons)

• Retroelements: reproduce via reverse transcription followed by intergration into the host DNA

  • long-terminal repeat transposons (LTR)

  • long interspersed elements (LINEs): these encode a reverse transcriptase

  • short interspersed elements (SINEs): these include Alu repeats

• DNA transposons: capable of integrating themselves to, and excising themselves from, the host genome, thus taking advantage of the host replication through this ‚cut-and-paste‘ mechanism

  • DNA transposons constitute 3% of the human genome