Promotor Prediction Programms (PPP)

1

Promotor Prediction Programms (PPP)

Christian Ehrlich&

Falko Krause

Evolution eukaryontischer Promotorsequenzen

2

Übersicht

• Einführung– Bilogischer Hintergrund– Maschinenlernen

• Eponine– Relevance Vector Machine

• FirstEF– Quadratische Diskriminanzanalyse

• Vergleich von PPPs

3

Der Promotor

Ort:– vor und nach der

Transkriptionsstart- stelle (TSS)

Merkmale:– Transkriptionsfaktor-

bindungsstellen (TFBS) z.B. TATA-Box

– CpG-Inseln– TSS– Initiator Sequenz

Einführung Eponine FirstEF Vergleich von PPPs

4

Maschienenlernen

Hidden Markov Modelle (HMM)

Neuronale Netze (NN)


5

Maschienenlernen

Sampling Relevance

Vector Machine (RVM)

Quadratische

Diskriminanz-

analyse (QDA)


6

Eponine

What can we learn from noncoding regions of similarity between regions

T.Down, T.J.P. Hubbard2004 , BMC Bioinformatics


7

Maschinenlernen

Überwachtes Maschinenlernen– annotierte Daten (Promoter Regionen, TSS,

proteincodierende Bereiche)– Modellerstellung aus diesen Daten– automatische Daten Annotierung

überwacht unüberwacht


8

Trainingset

H Chromosome 6

Human Maus

BLAST-Z F i l t e r

ab initioGen-Suche

codierend (annotiert)

RepeatMasker

M Genome

+ Trainingssetkonserviert funktionell

nicht proteincodierend

- Trainingssetnicht proteincodierend


9

Relevance Vector Machine

Bayes’sche automatische Relevanz Determination (ARD)für Modelle mit linearen Parametern (RVM 2000 M.E.Tipping M$)

• wenige Basis-Funktionen können von einem Generalisierten Linearem Modell (GLM) gelernt werden

• Basis-Funktionen können selbst gewählt werden (SVM nur Kernel Funktionen)

• Anzahl der Basis-Funktionen wird reduziert


10

Relevance Vector Maschine

+ Trainingsset - Trainingsset

RVM

)(

)()|()|(

DP

MPMDPDMP

Trainings Modell

PWM


11

Sampling

„Sequenzen in der Nähe der TATA-Box sind auch für Promotoren spezifisch“

• generiere eine neue PWM aus einer vorhanden durch Veränderung der Gewichte (Dirichlet verteilt)

• generiere eine neue PWM durch weglassen der ersten oder letzten Spalte


12

EAS, EWS, cEWS

• Eponine Anchored Sequence (EAS) – Anker

• Eponine Windowed Sequence (EWS)– zufallige PWMs

• Convolved Eponine Windowed Sequence(C-EWS)– PWM Gerüste


13

EWS – Ergebnisse

TSS Datenbank

H Chromosome 22

[-2k, TSS, +2k]

• Testset• Seedwort Länge

• Hits dist. TSS• ohne CpG

• Receiver Operating Characteristic curve


14

First Exon Finder (FirstEF)

Computational identification of promoters and first exon in the human genome

Ramana V. Davuluri. Ivo Gross & Michael Q. Zhang

Nature genetics, Volume 29, December 2001


15

Motivation

Gen Vorhersage erreicht ~90% Sensitivität– Genscan– FGENES– MZEF

Promoter Vorhersage erreicht ~50% Sensitivität– PromoterInspector– Eponine– DragonPF

\\|// (o o)-. .-. .-oOOo~(_)~oOOo-. .-. .-. .-. ||X|||\ /|||X|||\ /|||X|||\ /|||X|||\ /|||X|/ \|||X|||/ \|||X|||/ \|||X|||/ \|||X|||/ ' `-' `-' `-' `-' `-' `-' `-' `-' Genscan


DragonPF

16

Methoden

Diskriminanzanalyse

Idee: Klassifizierung eines Objektes anhand mind. einer Zufallsvariablen

Voraussetzung:

Günstig:

Benötigt:

0 1 ... n

X

~ ( , )X N

0 1 ... n

( | )iP Gruppe x


17

Methoden

Quadratische Diskriminanzanalyse (QDA)

Idee: Klassifizierung eines Objektes anhand mind. einer Zufallsvariablen

Voraussetzung:

Günstig:

Benötigt:

0 1 ... n

X

~ ( , )X N

0 1 ... n

( | )iP Gruppe x


18

Algorithmen Design

Suche nach Splice Donor Site (GT)

Suche 1500bp/500bp up-/downstream nach GT

Fenster = Promotor Region

first-Exon gefunden

P(donor site | GT) > 0.4

nicht CpG CpG

P(promotor | Fenster) > 0.4 P(promotor | Fenster) > 0.4

P(exon | alle) > 0.5


Fenster = Promotor Region

19

Training

QDF Training Probleme: Nicht viele GenBank Einträge beinhalten first-Exon

AnnotationenIdee: Sammele first-Exons und Promotoren durch Mapping von vollständige 5’ UTR’s auf Gensequenzen

2.139 first-Exons welche durch eine 500bp5’ Region (Promotor) und 500bp 3’ Region (Intron) flankiert sind

61% teilweise codierend und 39% nicht cod.


20

Training

QDF Training Evaluation

(sensitivity) (specificity)


Vorhersage von CpG first-Exons ist sehr gut

Vorhersage von nicht CpG first-Exons ist ok

21FirstEF: 106/121~87% vorhergesagt (33/42~78% nicht-codierent)

UCSC

Evaluation

Evaluation procedureGenBank

Genes + Promoters

(Chrom. 21/22)Chromosom 21/22

mit repeats & ohne repeats

BLAT

aliniere G. + P. mit Chromosom Sequenz

121annotierte first-Exons (42 nicht-codierent)


22

PPPs

Promoter prediction analysis on

the whole human genome

V.B.Bajic, S.L.Tan, Y.Suzuki, S.Sugano

Nature biotechnology, Volume 22, Number 11, November 2004


23

Testset

• basiert auf experimental Daten (full-length oligo-capped’ cDNA)

• nicht bei allen PPPs möglich

• einige false negatives werden in kauf genommen

Humanes Genom

[-2000bp , TSS , +2000bp]


24

Funktion

X

X

only

CpG Insel

X

HMM

X

X

X

TATA-Box

QDAFirst EF

XPromoter 2.0

INR + AbstandXNNPP

pysikalische Eigenschaften

XMC Promoter

RVMEponine

XXDragon GSF/PF

stat. regelbasiertes System

CpgProD

Weitere KonzepteC+G Gehalt

ANNName


25

26

PPPs im Vergleich – Gewinner?

• PPPs haben oft schlechtere Ergebnisse geliefert als angegeben – Eponine p.p.v.72,73% angegenen 66,97% erreicht– FirstEF p.p.v 86 % angegeben 67,1% erreicht

• nicht CpG-Insel Promotoren werden schlecht erkannt

• höchste p.p.v. < 65% ( 2 Richtige 1 Falsche )

• RepeatMasker verbessert oft das Ergebniss

• „Traue keiner Statistik die du nicht selbst gemacht hast“


27

PPPs in Kombiation

• Kombination von PPPs verbessert Ergebnisse

• Vorgehen:

– Scannen mit Fensterbreite von 2000bp– Wahlverfahren:

• Regel 1: Fester k bekommt +Vorhersagen von s PPPs

• Regel 2: Fester k bekommt +Vorhersagen von s PPPs von einer festgelegten Untergruppe


28

Zusammenfassung

• Lerverfahren ?– Relevance Vector Machine– Quadratische Diskriminierungs Analyse

• Wie bekomme ich Promotor-Regionen ?

• Evaluierung von PPPs ?– Verfahren– Vergleichbarkeit

• Probleme der Promotor Vorhersage ?

29

ENDE

Noch Fragen?

30

Literatur

• What can we learn from noncoding regions of similarity between regions, T.Down, T.J.P. Hubbard, http://www.biomedcentral.com/1471-2105/5/131

• Relevance Vector Machines for classifying points and regions in biological sequences, T.Down, T.J.P. Hubbard

• A Machine Learning Strategy to Identity Exonic Splice Enhancers in Human Protein-coding Sequence, T.Down, B.Leong, T.J.P. Hubbard

• Chapter 4. Learning from comparative genomics, http://library.sanger.ac.uk/uhtbin/cgisirsi/0/0/520/a12334d?user_id=HYP-REST

• The Relevance Vector Machine, M.Tipping• Crouching Introns,Hidden Exons, B.Leong• Promoter prediction analysis on the whole human genome, V.B.Bajic,

S.L.Tan, Y.Suzuki, S.Sugano• Computational identification of promoters and first exon in the human

genome, R.V.Davuluri, I.Gross, M.Q.Zhang

Documents

Promotor Prediction Programms (PPP)