BioinformaticaBioinformatica

• Prof. Raffaele Calogeroraffaele calogero@unito itraffaele.calogero@unito.itTel. 011 6705417Cell. 333 3827080Orari di ricevimento:Orari di ricevimento: – in qualunque momento

T t• Testo:– Introduzione alla Genomica, Gibson & Muse (Zanichelli)

• Capitoli trattati durante le lezioni• Capitoli trattati durante le lezioni.

Whole Genome Shotgun AssemblyT t t i f iTwo strategies for sequencing: clone-by-clone approach

whole-genome shotgun approach (Celera, Gene Myers).

Shotgun sequencing was introduced by F. Sanger et al. (1977) and has remained the mainstay of genome sequence assembly for nearly 25 years now.y y y

ED Green, Nat Rev Genet 2, 573 (2001)

Il sequenziamento gerarchicoIl sequenziamento gerarchico del genoma umanog

• Passaggi principali del sequenziamento gerarchicogerarchico

Mappa fisicaUn punto importante preliminare al sequenziamento del genomaumano è stata la costruzione di una mappa fisica ad alta risoluzionedi ognuno dei cromosomi umani.di ognuno dei cromosomi umani.Per completare una mappa fisica di 3 x 109 basi è necessariodisporre di libraries genomiche comprensive di tutto il genoma

ddi i i f ti ti l ti i iti tt isuddiviso in frammenti sovrapposti e clonati in appositi vettori.Una delle caratteristiche di queste libraries genomiche è che devonoessere costituite da grossi frammenti di DNA nell’ordine di 100-300gKb in modo che con 2-5 x 105 cloni indipendenti è possibile avere lacompleta rappresentazione del genoma.

∼300 kb

Eterocromatina

gapscostitutiva

BAC: Bacterial artificial chroosomeNel 1992 è stato sviluppato unvettore di clonaggio basato sulfattore episomale F difattore episomale F diEscherichia coli.Il fattore F di E. coli è un DNAextracromosomale circolare checontiene sul suo DNA alcunigeni regolativi:g g

oriS e repEparA e parB

I tt i BAC tt i tiI vettori BAC sono caratterizzatida:

un marcatore fenotipicositi cosN del batteriofagolambda e loxP del batteriofagoP1una serie di siti di restrizionerari.

• Costruzione di librerie di cloni contenenti 50-200Kb200Kb

Sequenziamento gerarchicoSequenziamento gerarchico

Filt i i i d ll lib i di• Filtrazione: rimozione dalle librerie di genomiche di materiale spurio (frammenti di genoma batterico)

• Assemblaggio: ordinamento delle contig di gg gciascun BAC/PAC e successivo allineamento delle contig sui cromosomi a ea e to de e co t g su c o osovia STS

• Merging: assemblaggio dei vari contig• Merging: assemblaggio dei vari contig negli “scaffolds” cromosomici

Ordinamento dei cloni BAC

BAC Fingerprint:

• Il chromosome walking gpermette di costruire delle contig in modo sequenziale.

• Usando la sequenza terminale di un primo clone si identificano altri che laidentificano altri che la condividono.

• Usando l’analisi dei profili di• Usando l analisi dei profili di restrizione è possibile ricostruire consequenzialità dei qvari cloni.

• Si isola una nuova sequenza terminale e si ripete la procedura.

• Dal punto di vista storico il metodo principale per allineare le mappe fisiche con le genetiche è l’uso delle mappe i l i hcitologiche.

• Le mappe citologiche sono profili di bandeggio cromosomico bili l i i tti i t t f i hosservabili al microscopio ottico su piastre metafasiche

colorate.• L’ibridazione in situ di frammenti di DNA (STS sequence• L ibridazione in situ di frammenti di DNA (STS, sequence

tagged site) permette l’allineamento con la mappa fisica.

Ricombinazioneigenomica

• La ricombinazione tende ad• La ricombinazione tende ad essere soppressa vicino al centromero ed incrementare notevolmente nelle parti distalinotevolmente nelle parti distali del cromosoma con particolare riguardo per le ultime 20-35 Mb.

• La ricombinazione è più alta in cromosomi corti per permettere almeno un crossing over peralmeno un crossing-over per braccio, anche perche’ i crossing-over sembrano essere necessari per la correttanecessari per la corretta disgiunzione meiotica delle coppie di cromosomi omologhi.

Ricombinazione genomicagenomica

• La ricombinazione media per cromosomamedia per cromosoma aumenta in funzione della riduzione della l h d l b ilunghezza del braccio del cromosoma.

• Lunghe braccia gcromosomiche hanno una media di ricombinazione di un cMricombinazione di un cM per Mb mentre braccia corte possono arrivare a 2 cM per Mb2 cM per Mb.

Mappatura citogeneticapp g

Bandeggiamento:C banding N bandingC-bandingD-bandingG-banding

N-bandingT-banding

Integrazione tra citogenetica e sequenze genomichegenomiche

Il collegamento tra mappa citogenetica e sequenza nucleotidica è stato realizzato attraverso l’uso delle STS (sequenze tagged site) ( q gg )che sono delle sequenze uniche del genoma.

La definizione di una mappa fisica genomica di STS è stato uno dei passi preliminari al sequenziamento del genoma umano.

Utilizzando una tecnica nota come FISH è stato possibile mappare la posizione di lunghi frammenti genomici (100-200 kb), contenenti una o piu’ STS, sul cromosoma metafasico e di conseguenza p , gassociare la posizione delle STS all’interno delle bande citogenetiche

FISHFISH: Trisomia del 21 FISH

Integrazione tra citogenetica e sequenze genomichegenomiche

Integrazione tra citogenetica e sequenze genomichegenomiche

• Una fase importantissima nel sequenziamento delsequenziamento del genoma umano è stato lo sviluppo distato lo sviluppo di nuove tecnologie di

i tsequenziamento automatico:– Incremento della

lunghezza dei gframmenti sequenziati

– Maggiore high-Maggiore highthroughput

Automated Sequencingl ll t ti i i d i th ti did h inearly all automatic sequencing is done using the enzymatic dideoxy chain-

termination method of Sanger (1977).Separation of fragments by gel electrophoresis.Readout of fragments labeled with fluorescent dyes.

Computer analysis of gel images:Computer analysis of gel images:- lane tracking – identify gel boundaries- lane profiling – sum each of 4 signals across lane width to create a profile- trace processing – deconvolute and smooth signal estimates + reduce noise- base-calling in which the processed trace is translated into a sequence of bases.

Program Phred is quasi-standard for last step (base calling).

Base Calling - PhredB. Ewing, L. Hillier, M.C. Wendl, P. Green Base-calling of automated sequencer traces using Phred. I. Accuracy assessment. Genome Res 8, 175-185 (1998).B. Ewing, P. Green. Base-calling of automated sequencer traces using Phred. II. Errror probabilities. Genome Res 8 186-194 (1998)Genome Res 8, 186-194 (1998).

The processed traces are displayed as chromatograms of 4 curves of different color, each curve representing the signal of 1 of the 4 bases.

Base Calling - PhredIdealized traces would consist of evenly spaced, nonoverlapping peaks Q litnonoverlapping peaks.

Real traces deviate from

Quality:high – noambiguities

this ideal due to imper-fections of the sequencingreactions, of gel electro-reactions, of gel electrophoresis, and of traceprocessing.

medium – someambiguities

The first 50 or so peaksand peaks over 500 or soare particularly noisy. Poor – low

confidence

PhredPhred

• La probabilità di errore di lettura di una base generata da Phred è data da:– La variazione di distanza del picco in un intervallo di

sette picchi, con al centro la base in corso di id tifi iidentificazione.

– Il rapporto tra il più alto ed il più basso picco non identificato nello stesso intervalloidentificato nello stesso intervallo.

– Lo stesso rapporto in un intervallo costituito da tre picchipicchi.

– Il numero di basi tra quelle in esame e quella vicina non identificata.non identificata.

PhredPhred

• La probabilità di errore (P) è trasformata in un punteggio che corrisponde a 10 volte il logaritmo negativo di P.

• Un punteggio di phred inferiore a 13 indica che ggc’è una probabilità di errore >0.05.

• Un punteggio di phred maggiore a 30 indica cheUn punteggio di phred maggiore a 30 indica che c’è una probabilità di errore <0.001.

• Punteggi maggiori di 20 indicano una elevata• Punteggi maggiori di 20 indicano una elevata attendibilità.

• Ciascun tracciato è accompagnato da due righe (automatica e manuale).

– A) Notevole rumore di fondo dato dalla letturafondo dato dalla lettura delle prime basi

– B) Presenza di tratti polimorfici in due sequenze

– C) Dopo 800 basi si osserva in genere una degradazione della gqualità della sequenza

• Distribuzione dei punteggi phred su 26000 letture di

Gli i t isequenza. Gli istogrammi più scuri rappresentano la qualità di lettura per basi comprese tra 100 e 400.comprese tra 100 e 400.

• Gli istogrammi più chiari rappresentano i punteggi assegati a tutta la gsequenza leggibile

Phrap & ConsedPhrap & Consed• Phrap:

– Programma che permette l’assemblaggio delle sequenze derivate dallo stesso clone in una contigderivate dallo stesso clone in una contig

• Consed:– Programma grafico per la valutazione e manipolazione dei og a a g a co pe a a uta o e e a po a o e de

risultati dell’assemblaggio phrap

Quanti frammenti devo sequenziare?• Considerando N frammenti di lunghezza h

distribuiti su un genoma di lunghezza G, il grado di copertura è dato da:grado di copertura è dato da:

Nha =Shotgun sequencing Ga =

Se N è grande e h è piccolo la di t ib i d i f ti ’distribuzione dei frammenti puo’ essere approssimata ad una distribuzione di Poisson con media pari al grado di copertura a.Data la distribuzione di Poisson la probabilità che l’estremo sinistro di unprobabilità che l estremo sinistro di un frammento sia presente in un punto scelto casualmente è pari a:

aep −−=1

Quanti frammenti devo sequenziare?

aep −−=1b b l à d l

ep 1Per avere una probabilità del 0.99 a=4.6.Per avere una probabilità del 0.999 a=6.9

Essendo il genoma umano 3 x 109 basi anche con un copertura di 6.9 rimangono 3 x 106 basi non p gsequenziate.

Sequenziamento shotgun

Passaggi del sequenziamento shotgun

• Screener: mascherare le sequenze ripetute.p

• Overlapper: assemblare tra loro i frammentiframmenti– Le sovrapposizioni specifiche hanno una

17probabilità di apparire una volta ogni 1017

comparazioni quindi è poco probabile che compaiano 2 volte nello stesso genoma se non ci sono state duplicazioni recenti.

Passaggi del sequenziamento shotgun

• Unitigger: ragguppamento delle contig basate su sequenze non ripetute e ripetute q p pin unitig, che sono una serie di sequenze uniche che non si sovrappongono in modouniche che non si sovrappongono in modo ambiguo.S ff• Scaffolder: assemblaggio delle unitig in scaffolds.

• Assemblaggio nel sequenziamento shotgun:– A: asseblaggio per sequenze singole (sinistra) e sequenze ripetute (destra)– B: Overlapper allinea le Unicontig (U-unitig sequenze non ripetute, Unitig

supercollassate sequenze ripetute)supercollassate sequenze ripetute)– Orientamento delle U-unitig sulla base delle sequenze terminali di cloni da 10-50 Kb

Rifiniture del sequenziamento shotgun

• Le lacune restanti vengono risolte in più passaggi successivi:– Inserzione delle unitig precedentemente scartate ma

confermate da più di due o tre coppie appaiate– Inserizione delle sequenze la cui posizione è

confermata da una sola letturaBAC lki l t l l i ti– BAC walking per completare le lacune rimanenti

– Associazione degli scaffolds alla struttura genomica via STSvia STS

• Rifiniture di assemblaggio shotgun

Verifica delle sequenzeVerifica delle sequenzeL l t i d ll idi ità di• La valutazione della veridicità di un sequenziamento genomico viene fatta a tre livelli:livelli:– Completezza: limitata dalla possibilità di clonare e

sequenziare regioni ad altissima ripetitivitàsequenziare regioni ad altissima ripetitività (eterocromatina costitutiva)

– Accuratezza: L’accuratezza di sequenza puo’ essere aumentata semplicemente aumentando la ridondanza di sequenziamentoValidità degli allineamenti: E’ determinabile– Validità degli allineamenti: E determinabile integrando dati preesistenti quali mappe fisiche o genetiche con i dati di sequenziamento.

• Valori stimanti di identificazione corretta dei tratti riuniti di un genomaPer il progetto genoma umano l’94% è inserito in• Per il progetto genoma umano l’94% è inserito in contig di almeno 100Kb

• Discrepanze tra i progetti di sequenziamento alla stesura preliminare della sequenza.

– Il cromosoma 22 considerato “finito” aveva molte meno discrepanze del 5 ancora in fase “draft”

– Verde allineamenti appaiati, arancione zone >50kb non ordinate, azzurro regioni orientate in modo opposto. Trattini neri: interruzioni, trattini blu N di 10 kb

Annotazione dei geniAnnotazione dei genisu sequenze genomicheq g

Structure and transcription of a Eukaryotic gene

What is gene prediction?What is gene prediction?

Detecting meaningful signals in uncharacterised DNA sequencesDetecting meaningful signals in uncharacterised DNA sequences.

Knowledge of the interesting information in DNA.

S ti th ‘ h ff f th h t’Sorting the ‘chaff from the wheat’

GATCGGTCGAGCGTAAGCTAGCTAG

ATCGATGATCGATCGGCCATATATC

ACTAGAGCTAGAATCGATAATCGATACTAGAGCTAGAATCGATAATCGAT

CGATATAGCTATAGCTATAGCCTAT

Gene prediction is ‘recognising protein-coding regions in genomic sequence’

Knowing what to look forKnowing what to look for

What is a gene?What is a gene?

Not a full transcript with control regions

The coding sequence (ATG -> STOP)

Start MiddleN

EndStart Middle End

Annotation of eukaryotic genomesAnnotation of eukaryotic genomes

Genomic DNA ab initio gene

transcriptionUnprocessed RNA

ab initio gene prediction

RNA processing

translation

AAAAAAAMature mRNAComparative gene

di ti

Gm3

translationNascent polypeptide folding

prediction

Active enzyme

Functional

Reactant A Product BFunction

identification

Gene finding: Issuesg

Issues regarding gene finding in generalIssues regarding gene finding in general

Genome size

Genome composition

Genome complexity

cis-splicing

t li itrans-splicing

alternate splicing

Gene finding: genomeg g

Genome compositionGenome composition

Long ORFs tend to be coding

Presence of more putative ORFs in GC rich genomes (Stop codons = UAA, UAG & UGA)

Genome complexity

Simple repetitive sequences and dispersed repeats p p q p ptend to be anti-coding

May need to mask sequence prior to geneMay need to mask sequence prior to gene prediction

Gene finding: coding densityg g y

As the coding/non-coding length ratio decreases, exonAs the coding/non coding length ratio decreases, exon prediction becomes more complex

Human

Fugu

worm

E.coli

In procarioti e eucarioti inferiori l’identificazione di geni è relativamente facile.I metodi ab-initio identificano in modo preciso fino al 90% dei geni.p g

Gene finding: splicingg p g

cis-splicing of genes

Finding multiple (short) exons is harder than finding a single (long) exon.

In uomo la dimensione media di un esone è 50 basi

trans-splicing of genes

A trans-splice acceptor is no different to a normal splice acceptor

worm

E liE.coli

Gene finding: alternate splicingGene finding: alternate splicing

Alternate splicing (isoforms) are very difficult to predict.

Human A

Human B

Human C

ab initio predictionab initio prediction

What is ab initio gene prediction?

Prediction from first principles using the raw DNA sequence only.

GATCGGTCGAGCGTAAGCTAGCTAG

ATCGATGATCGATCGGCCATATATC

ACTAGAGCTAGAATCGATAATCGAT

CGATATAGCTATAGCTATAGCCTAT

Requires ‘training sets’ of known gene structures to generate statistical tests for the likelihood (probability) of a prediction beinglikelihood (probability) of a prediction being real.

Gene finding: ab initioGene finding: ab initio

What features of a ORF can we use?What features of a ORF can we use?Size - large open reading frames

DNA composition - codon usage / 3rd position codon bias

Kozak sequence CCGCCAUGG

Ribosome binding sites

Termination signal (stops)

Splice junction boundaries (acceptor/donor)

Gene finding: featuresGene finding: features

Think of a CDS gene prediction as a linear seriesThink of a CDS gene prediction as a linear series of sequence features:

Initiation codon

Coding sequence (exon)Coding sequence (exon)

Non coding sequence (intron)

Splice donor (5’)N times

Non-coding sequence (intron)

Splice acceptor (3’)

Coding sequence (exon)

Termination codon

Coding sequence (exon)

Splicing SignalsSplicing Signals

Exons are interspersed with introns and typically flanked by GT and AG

Consensus splice sitesConsensus splice sites

Donor: 7.9 bitsAcceptor: 9.4 bitsAcceptor: 9.4 bits(Stephens & Schneider, 1996)

(http://www-lmmb.ncifcrf.gov/~toms/sequencelogo.html)

Splice site detectionSplice site detection5’ 3’

Donor site5’ 3’

Position

% -8 … -2 -1 0 1 2 … 17A 26 … 60 9 0 1 54 … 21A 26 … 60 9 0 1 54 … 21C 26 … 15 5 0 1 2 … 27G 25 … 12 78 99 0 41 … 27T 23 … 13 8 1 98 3 … 25

From lectures by Serafim Batzoglou (Stanford)

An end to ab initio predictionAn end to ab initio prediction

b i i i di i i iab initio gene prediction is inaccurate

High false positive rates for most predictors

Exon prediction sensitivity can be good

Rarely used as a final product

Human annotation runs multiple algorithms and scores exon predicted by multiple predictors.

Used as a starting point for refinement/verification

Prediction need correction and validation

Why not just build gene models by comparative means?

Annotation of eukaryotic genomesAnnotation of eukaryotic genomes

Genomic DNA ab initio gene

transcriptionUnprocessed RNA

ab initio gene prediction

RNA processing

translation

AAAAAAAMature mRNAComparative gene

di ti

Gm3

translationNascent polypeptide folding

prediction

Active enzyme

Functional

Reactant A Product BFunction

identification

comparative gene prediction

Use knowledge of known coding sequences to identify region of genomic DNA by similarityidentify region of genomic DNA by similarity

transcriptome - transcribed DNA sequence

proteome - peptide sequence

genome - related genomic sequencegenome related genomic sequence

Transcript-based prediction: datasetsTranscript based prediction: datasets

Generation of large numbers of Expressed Sequence Tags (ESTs)g p q g ( )

Quick, cheap but random

Subtractive hybridisation to find rare transcriptsSubtractive hybridisation to find rare transcripts

Use multiple libraries for different life-stages/conditions

Single-pass sequence prone to errorsSingle-pass sequence prone to errors

Generation of small number of full length cDNA sequences

Slow and laborious but focusedSlow and laborious but focused

Large-scale sequencing of (presumed) full length cDNAs

S i l i l d l i / i f CDSSystematic, multiplexed cloning/sequencing of CDS

Expensive and only viable if part of bigger project

Transcript-based prediction: How it worksp p

Align transcript data to genomic sequence using a pair-wise isequence comparison

EST(Expression sequence tag)

cDNA

OST(ORF sequence tag)

Summary

Genes are complex structure which are difficult to predict with the required level of accuracy/confidence

W di t t b tt th t tWe can predict stops better than starts

We can only give gross confidence levels to predictions (i.e. confirmed partially confirmed or predicted)confirmed, partially confirmed or predicted)

Gene prediction is only part of the annotation procedure

Movement from ab initio to comparative methodology asMovement from ab initio to comparative methodology as sequence data becomes available/affordable

Curation of gene models is an active process – the set of gene models for a genome is fluid and WILL change over time.