Bio-informatica Genpredictie

Bio-informatica Genpredictie

9

Genpredictie ●

Genpredictie –

opsporen van functionele gebieden en elementen die verantwoordelijk zijn voor de genstructuur, genregulatie en gentranscriptie in genomische sequenties

Prokaryoten ●

Bacteriele genomen –

Dense, compacte genomen ● ● ●

–

85-88% coderend Continue genen Korte intergenische afstanden

Elementen prokaryote genen ●

Promotor –

– –

Een beperkt aantal σ factoren ● Herkenning specifieke promotors ● Consensus rond -35 en -10 t.o.v transcriptie start ● Meest courante σ70 consensus TATAAT op -10 Andere regulatoren in/achter promotor, vaak negatieve regulatie Verschillende genen vaak samen afgeschreven in 1 operon Promotor 5' CDS

DNA

Prokaryoten ●

Start translatie –

Shine-Delgarno sequentie (AGGAGGU) ●

–

Start codon ●

●

Vaak vlak achter promotor, vlak voor start codon AUG (zelden UUG of GUG)

Terminatie transcriptie –

Geinverteerde repeat ● ●

–

Kan haarspeld structuur vormen Kan RNA polymerase doen pauzeren

Een zestal opeenvoldende Uracil nucleotiden vlak na deze repeat ●

Zwakkere binding

Prokaryoten ●

Open Reading Frame (ORF) –

= Stuk sequentie zonder stopcodons (in coderend stuk zitten er nl. Geen stopcodons) Detectie van genen door grotere ORF te zoeken ● ● ●

Meeste genen > 60 codons Willekeurig: 1 stopcodon per 21 codons (3/64) > 60 codons -> ws. Gen

Prokaryoten ●

Genpredictie in prokaryoten – – – – –

●

Continue genen Meestal lange ORFs (> 60 codons) Relatief simpel herkenbare promotors Herkenbaar einde transcriptie Meeste nucleotiden zijn coderend

Problemen – – –

Korte genen (~korter dan 60 codons) Sequentie fouten (ORF is hier gevoelig voor) Overlappende genen op beide strands

Eukaryoten ●

Eukaryote genomen – –

Slechts enkele procenten zijn coderend Complexe genstructuur ● ● ●

–

Lange genen ●

– –

splicing Geneste en overlappende genen Alternatieve splicing ~ verschillende isovormen CDS verspreid over grote gebieden (lange intronen)

Niet simpelweg zoeken naar ORFs Promotor ●

geconserveerde sequenties diffuser en veel verder van start

Van DNA tot proteine Upstream Genomisch DNA 5'

Promotor Exon 1

Intron 1

Intron 2 Exon 2

Intron 3 Exon 3

Downstream Genomisch DNA 3'

Intron 4 Exon 4

Exon 5

DNA

Transcriptie en processing Intron 1 Intron 2 Intron 3 Intron 4 CAP PolyA (7-methylguanosine) Exon 1 Exon 2 Exon 3 Exon 4 Exon 5

pre-mRNA

Splicing CAP 5'UTR

3'UTR PolyA

mRNA

CDS

Translatie Proteïne Posttranslationele processing

GFF ●

GFF – –

“General Feature Format” (vroeger “Gene Feature Format”) Eenvoudig, standaard formaat voor identificatie regios in een sequentie (exon, CDS, ...) ●

●

●

–

Verschillende velden met vaste volgorde (gescheiden door TAB karakters) Eerste lijn → commentaar (begint met #) die file formaat en versie aanduid Volgende lijnen → data

Gemakkelijk te bekijken, vergelijken, testen, integreren

GFF

– – – – – – – – –

##gff-version 3 SEQ1 EMBL SEQ1 EMBL SEQ1 EMBL SEQ1 netgene SEQ1 EMBL

mRNA CDS splice5 splice5 CDS

seqid

feature start

322 173 174 174 322

. . . 0.94 .

+ + + + +

. 0 . . 2

einde score streng fase

ID=gene1 Parent=gene1 Parent=gene1 attributen

seqid: naam van de sequentie bron: programma, publieke database annotatie, experimenteel feature: feature type, karaktereigenschappen start: getal dat begin van feature op sequentie aangeeft (nummering start met 1) einde: getal dat einde feature aangeeft score: getal → waarschijnlijkheid dat deze voorspelling correct is (. voor geen score) streng: +, - or . (“.” wordt gebruikt wanneer niet relevant) fase: 0,1,2 or . Geeft aan waar deze feature zit t.o.v. het reading frame → hoeveel nucleotiden vanaf start feature horen nog bij vorige codon [group/attributen]: optioneel, in de vorm van tag1=value1;tag2=value2; … ●

–

bron

103 103 173 173 263

ID en Parent tags kunnen worden gebruikt om een hierarchie aan te geven

[comments]: optionele string

Accuraatheid ●

Vergelijking methoden –

Met gekende genen (test set) voorspellingen van verschillende methoden vergelijken ●

– ●

testset eigenlijk liefst zo representatief mogelijk voor wat je gaat vergelijken

Standaard test en trainings datasets (Burset and Guigo, Reese)

Maar – – – – –

Bias in training data door welke genen aanwezig zijn in de databases Bias naar standaard test sets/genen 1 gen per sequentie vs meerdere/partiele in reëele data Toelaten organisme specifieke training? In hoeverre zijn deze standaard test/training sets representatief

Accuraatheid ●

EGASP – –

ENCODE Genome Annotation Assessment Project Workshop om accuraatheid voorspellingen na te gaan ●

● ●

● ●

ENCODE, HAVANA → hoge kwaliteit annotatie op manuele en experimentele basis (langdurig en kostelijk) een deel hiervan vrij gegeven (als trainings data) deelnemers werden gevraagd om met hun methoden de overige encode regios te annoteren (zonder kennis van de experimentele annotatie) vergelijking automatische predictie met annotatie verschillende categorien: –

–

1. eender welke informatie 2. enkel ab-initio 3. extrinsieke methoden 4. comparatieve methoden 5. nieuwe genen 6. ongewone genen 7. exon-only

Doel ● ●

Hoe goed reproduceren verschillende automatische methodes deze annotatie hoe ver rijkt onze kennis: predicties niet in de manuele annotaties worden uitgebreid experimenteel gecontroleerd via RT-PCR

Accuraatheid ●

Categorie: Exon level – –

–

Sensitiviteit: Sn = TP/(TP+FN) ●

–

Proportie van echte exonen die correct voorspeld werd (beide einden exact correct)(start-stop op juiste positie)

Specificiteit (volgens EGASP): Sp = TP/(TP+FP) –

●

–

TP = True Positives, TN = True Negatives FP = False Positives, FN = False Negatives

Volgens klassieke definities heet deze maat eigenlijk de “precision”, de “specificiy” volgens klasieke definitie, TN/(TN+FN), kan hier niet gemakkelijk berekend worden

Proportie van voorspelde exonen die correct voorspeld werd

→ Hoe hoger Sp: hoe minder vals positieven → Hoe hoger Sn: hoe minder vals negatieven Andere ● ● ●

Hoeveel missing exons (niet voorspelde exonen)? Hoeveel wrong exons (volledig incorrecte voorspelling)? Hoeveel half exons (een uiteinde correct)?

Accuraatheid ●

Categorie: Nucleotide level –

Sensitiviteit (Sn) ● ●

–

= TP / (TP + FN) Proportie van exonische nucleotiden die correct voorspeld werd

Specificiteit (Sp) (volgens EGASP) ● ●

= TP / (TP + FP) Proportie van nucleotiden die voorspeld werden exonisch te zijn waarbij die voorspelling correct is

Accuraatheid –

Matthews Correlatie coefficient ●

●

Probeert Sn en Sp samen te vatten in 1 getal → 1 maat voor de globale accuraatheid van nucleotide predictie CC=(TP x TN – FP x FN)/(ANxAPxPPxPN)-2 – – – –

●

Tussen -1 and 1 – –

●

AN = Actual Negatives (FP+TN) AP = Actual Positives (TP+FN) PP = Predicted Positives (TP+FP) PN = Predicted Negatives (TN+FN) 1: perfecte predictie -1: perfect verkeerde predictie

Waarde 0 betekent geen correlatie tussen predictie en werkelijkheid: ~ random toewijzing

Typische problemen ●

Training – –

Species specificiteit van signalen, training, parameters Goede datasets zijn moeilijk te vinden ● ●

● ●

Experimenteel geverifieerd Representatief ?!

Alternatieve splicing is moeilijk te voorspellen Geneste genen

Overzicht methoden ●

Extrinsieke methoden – –

Vergelijking met cDNA, ESTs, gekende proteinen Externe data ● ●

●

BLAST, FASTA met databases -> exonen Spliced alignment

Intrinsieke methoden –

Patroonherkenning ●

Signal sensors –

●

Content sensors –

– ●

Coderende regios

Geintegreerde methoden

Comparative genomics ●

●

Splice sites, start en stop codons, polyA site, ...

Conservatie bij vergelijking van verschillende genomen

Analyse pipelines

Extrinsieke methode: Spliced alignement ●

Spliced alignement – –

Alignatie van cDNA (→ enkel exonen), proteïne t.o.v. genomische sequentie Rekening houdend met intronen ● ●

Grote gaps Positionering van gaps op intron grenzen –

Upstream Genomisch DNA 5'

Moeilijker door mogelijke overlap van alignmenten

Downstream Promotor Intron 1 Intron 2 Intron 3 Intron 4 Exon 1 Exon 2 Exon 3 Exon 4 Exon 5 Genomisch DNA 3'

CAP 5'UTR

3'UTR PolyA

mRNA

DNA

Spliced RNA alignement ●

Soorten RNA –

EST ● ●

–

mRNA, geclusterde ESTs ● ● ● ●

●

Veel Lage sequentie kwaliteit, korte stukken transcript Langer/volledig transcript Gen structuren Minder beschikbaar Interessantste → goede spliced alignment van mRNA ~ experimenteel bewijs!

Annotatie van genomische regio –

Geschikte RNA sequenties evt. Vinden in databanken met bv. BLAST

Spliced RNA alignement ●

Problemen –

Bias naar sterk geexpresseerde genen ● ●

– –

Sequentie kwaliteit – bij fouten in de sequentie is correct alignatie moeilijker Contaminatie met genomische sequenties ●

–

Meer informatie over sterk geëxpresseerde genen Weinig/facultatief geexpresseerde genen worden gemakkelijker gemist

Wanneer er nog een intron in een mRNA sequentie zit).

Modellering splice sites

Spliced RNA alignement ●

Programma's –

Spidey (zie oefeningen) – –

–

GeneSeqer –

–

Alignatie mRNA, ESTS (lokaal alignement exonen) Gebaseerd op BLAST algoritme ● Construct genomic windows: stringente BLAST, sorteren, consistente hits ● Alignement in windows: weinig stringente BLAST + Dotview ● Detectie splice sites (met PWM) in gebieden waar alignementen van exonen overlappen ● Beste splice sites (score) die de alignementen het minst verstoren ● Niet consistente hits worden eruit gefilterd.

sim4

Ook minder verwante ESTs

Spliced proteïne alignement – –

Spliced alignement met verwante, gekende proteïne sequenties Programma's ●

Procrustes –

●

Genewise (WISE2) –

–

beste combinatie mogelijke exonen met dynamic programming dynamic programming, statistische modellen van splice sites

Problemen ● ●

●

Bias naar gekende genen/genfamilies Databases (SWISS PROT/TrEMBLE) met b.v. ook hypothetische/verkeerd geannoteerde proteïnen Modellering splice sites

Intrinsieke methoden ●

Patroonherkenning –

Signal sensors ● ● ●

–

Content sensors ● ● ●

●

Patronen in een regio (dus niet 1 specifieke positie) in genstructuur Coderende regios Methoden: Statistische analyse in window, HMM, …

Geintegreerde systemen –

●

Patronen met specifieke positie in genstructuur Splice sites, start en stop codons, polyA site, ... Methoden: Consensus sequenties, weight matrices, HMM, NN, ...

Integratie van verschillende sensoren tot volledige genstructuur predictie → meest gebruikt

Ook wel eens ab-initio methoden genoemd = Vanuit eerste beginselen, zonder gebruik te maken van extra data (Maar: veel methoden gebruiken wel trainingsdata om patronen te leren ...)

Promotor herkenning ●

Polymerasen ● ● ●

●

RNA polymerase I RNA polymerase II RNA polymerase III

-40 tot +20 ... tot -25 +50 tot +100

simpel zeer complex simpel

rRNA, snRNA coderende genen (belangrijkste) tRNA, small RNAs

Herkenbare elementen (~ niet altijd aanwezig) – –

CpG eilanden bij sommige promotoren Initiator (Inr) sequentie ●

–

[CT][CT]CA[GA][GA] rond +1

Transcriptie factoren (TF) ● ● ● ● ●

Basale transcriptie factor bindende site rond -25 consensus TATA[AT]A[AT] → TATA box Vele andere TF binding sites, en combinaties Dicht bij transcriptie start b.v. CAAT-box: zelfde orientatie, -80 Enhancers kunnen werken op grote afstand van transcriptie start, en in verschillende orientaties

Promoter herkenning ●

TF databases – –

TF binding sites gebaseerd op profielen/matrices TRANSFAC ●

–

Zeer uitgebreid, commercieel

JASPAR ●

Open alternatief, kleiner, niet redundant, curated

Promoter herkenning ●

Problemen – –

TATA-loze promoters Transcriptie factor binding sites ● ● ●

– – –

zijn zeer kort komen veelvuldig voor, ook buiten promotoren Zoeken naar combinaties

Promotor kan groot gebied beslaan Context is belangrijk! Niet zoveel uitgebreid experimenteel bepaald

Promoter herkenning Programma's –

PromoterScan –

–

MatInd en MatInspector –

–

–

QDA (Quadratic Discrimination Analysis) Zoekt TSS en core promoter in sequentie van beperkte lengte

Neural Network Promoter Prediction –

–

Neurale netwerken geoptimaliseerd m.b.v genetische algoritmen

CorePromoter –

–

LDA combinatie van herkenning verschillende features (TATA-box, Inr signaal, upstream regio)

CBS Promoter 2.0 –

–

Consensus matches met gekende TF bindingsplaatsen (TRANSFAC)

TSSG/TSSW –

–

database van bindingssites van gekende transcriptie factoren

“time-delay neural network”

Markov Chain Promoter Finder

Splice sites ●

Herkenbare elementen –

Donor consensus ●

–

Acceptor consensus ●

–

●

(T>C)nN(C>T)AG^gt

Branch site ●

–

[CA]AG^GT[AG]AGt

tussen 18 en 40 basen upstream van 3' splice junctie

Meestal in combinatie met coding bias

Problemen – – – –

overpredictie Context ! U12 afhankelijke (AT-AC) splice sites Andere types intronen (vnl. In non-coding genes)

Splice site programma's ●

NetGene2 ●

●

NNSPLICE ●

●

“Multi-layered feed-forward neural network”

BCM Genefinder HSPL (human) ●

●

Combinatie neurale netwerken en en “rule-based” systemen

Triplet frequenties in de functionele gebieden van de splice regio in combinatie met codon statistieken

SplicePredictor ●

“Logitlinear models” – –

Match t.o.v. Splice site consensus Lokaal compositioneel contrast

Startcodon ●

Kozak rules – –

●

Meestal eerste methionine van 5' dat je in transcript tegen komt = startcodon Consensus [AG]CCAUGG

Programma's –

Netstart ●

●

–

Neuraal netwerk gebaseerd op lokale start codon informatie en globale sequentie informatie Getraind op cDNA sequenties

ATGpr ●

lineaire discriminant analyse

PolyA ●

PolyA – –

Herkenning plaats waar poly-A tail (200-250 A's) wordt aangehangen herkenning sequenties ● ● ● ●

●

A[AT]TAAA ~20 basen voor knipplaats Zwak geconserveerd GT gebaseerd motief Werkt enkel in de juiste context ! dikwijls laatste exon

Programma's –

BCM GeneFinder POLYAH ● ●

Triplet frequenties in functionele delen LDA

Coding potential –

Hoe coderend is een sequentie? ●

–

Moet werkzaam proteïne produceren → Evolutie van coderende sequenties wordt sterk beinvloed door het gecodeerde product

Vele methoden om de “coderendheid” van sequenties te herkennen ● ● ●

Van statistiek over een window van een bepaalde grootte Tot complexe machine learning technieken Moeilijker exacte grenzen te bepalen ~ combinatie met splice donor/acceptor

Coding potential –

Methoden gebaseerd op de (vertaalde) AZ sequentie – –

–

Codon gebruik – –

–

ORF: afwezigheid van stop codons AZ of diAZ gebruik Codon usage vector: frequentie van 64 mogelijke codons Verschillen o.w.v. verschillend AZ gebruik, codon voorkeuren

Bias in base samenstelling tussen codon posities – – –

Meest frequente codons RNY ([AG][UCAG][UC]) Positie assymetrie: assymetrie in basensamenstelling op de drie verschillende codon posities Periodiciteit ● Coderende sequence (CDS) heeft een inherente periodiciteit van 3 ● Vooral duidelijk in lange CDS; moeilijk voor korte CDS ● Auto-correlatie, FFT (fourier transformaties), ...

Coding potential –

Invloed reading frame – – –

–

“In-phase” woorden – –

– –

–

AZ samenstelling in coding frame vs niet-coding frame (meer stop codons dan bij toeval) Codon samenstelling in alle frames Codon positie correlaties (dinucleotide distributie) Frequenties van voorkomen van woorden (lengte N) Hexameer frequenties zeer succesvol ● Omvat eigenlijk meeste hiervoor vermelde elementen Brengen correlaties over korte regios in rekening b.v. Codon eindigend op een G wordt meestal niet gevolgd door een codon dat begint met een G

Machine Learning gebaseerde methoden – –

HMM, NN training op gekende sets (experimenteel bepaalde CDS)

Coding potential ●

Programma's –

GRAIL I –

–

GeneMark –

–

Neuraal netwerk met shifting window Inhomogene Markov chain models

Glimmer –

Interpolated Markov chains

Geintegreerde systemen ●

Vinden van volledige genstructuren kan via verschillende methoden – – – –

Integratie van de resultaten van een aantal sensoren m.b.v. HMMs, neurale netwerken and decision trees Integratie binnen 1 systeem b.v. HMM Beste combinatie exonen met dynamic programming Evt. incorporatie homologie informatie

Genscan ●

Model Genscan HMM –

Cirkels en ruiten → functionele eenheden (toestanden) van een gen ● ● ● ●

●

– –

Bij test sequentie wordt elke base toegewezen aan een toestand Volledig model ●

Forward Strand

N → neutraal (niet in een gen) Prom → promotor 5' → start transcriptie Exon Sngl → voor genen die uit 1 enkel exon bestaan Exonen (Exon 0,1,2) en intronen (I0,I1,I2) worden geassocieerd met de fase (t.o.v. het reading frame)

● ●

Getoonde model enkel forward strand ditzelfde ook nog eens voor reverse strand Genen in beide richtingen tegelijk voorspeld

Reverse Strand → gelijkaardig aan hierboven

Geintegreerde systemen ●

GENSCAN – – –

●

AUGUSTUS – – – –

●

Generalized HMM annoteert ook UTR, alternatieve transcripten. incorporatie van extrinsieke data is mogelijk (AUGUSTUS+) lijkt nog acurater dan Genscan (EGASP)

TWINSCAN – –

●

Meerdere signaal en content modellen, HMM sensoren Verschillende modellen afh. Van GC Zeer goede resultaten

Gebaseerd op GENSCAN Incorporeert homologie informatie uit genome comparison

GeneID, GeneID+ – – – –

Signalen met Position Weight Matrices, coding potential met MM Combinatie exonen met dynamic programming GeneID+ incorporeert homologie data Goede resultaten, snelheid en geheugenverbruik

Geintegreerde systemen ●

Eugène – –

●

MORGAN –

●

–

–

Verbeterde sensoren Incorporatie EST/cDNA data

GeneParser –

●

Verschilende sensoren+NN (neural networks) Combinatie rule-based

GRAILExp –

●

Decision trees, dynamic programming

GRAIL –

●

Combinatie van vele systemen, plugins Vnl. Getraind op plant genomen

NN, dynamic programming

Andere –

FGENEH, Genemark, Genemark.hmm, NetGene2, SORFIND, GenLang,VEIL, GENIE, HMMgene, ...

Genome comparison ●

Methode – –

●

Vergelijking homologe genomische regios binnen verwante soorten bv. mens – muis Studie van conservatie → Regios met belangrijke functies (CDS, regulatoire gebieden) worden sterker geconserveerd

Problemen –

Interessante homologe region moet beschikbaar zijn ● ●

–

voldoende geconserveerd, maar niet helemaal Soms ook conservatie buiten CDS, ...

Conservatie duidt op belang regio, zegt niet direct welke functie (CDS, regulatie)

Genome comparison ●

PipMaker – –

Alignatie gebieden met BLASTZ pip: percent identity plot ● ●

Percent identiteit van gap-vrije gealigneerde segmenten Uitzetten in grafiek – –

●

positie in sequentie similariteit van de gealigneerde segmenten

Veel/Langere alignmenten met hoge similariteit → exonen, regulatoire elementen

PipMaker

●

Pipmaker output – – –

Exonen in groen aangeduid Regulatoire gebieden in rood Intronen in het geel

Genome comparison ●

AGenDA –

Kandidaat exonen ● ●

–

Fragmenten gevonden met dialign alignatie algoritme Splice sites met PWM en start/stop codons in buurt van geconserveerde regios

Beste combinatie met dynamic programming

AGenDa

Agenda example

Genome comparison ●

SLAM ● ● ●

●

SGP2 ● ●

●

Simultane alignatie en predictie GPHMM (Generilized Pair HMM) onderscheid tussen conserved non-coding sequence (CNS; UTR, regulatoire elementen, ...) en conserved coding sequence tblastx tussen 2 “anonieme” homologe genomische sequenties Geneid combineert “hit” data met ab-initio genpredictie

Twinscan ●

Genscan gebaseerd algoritme combineert “hit” data met ab-initio genpredictie

Annotatie pipelines ●

Pipeline –

– – ●

Scripts/programma's die automatisch opeenvolging/combinatie van verschillende analyse programma's regelen Vaak parallelle computer systemen Alle annotatie wordt centraal verzameld, beschikbaar gesteld

Voorbeelden – –

Ensembl NCBI mapviewer