Bio-informatica Similariteit Searches. Peter De Rijk

Bio-informatica Similariteit Searches Peter De Rijk

6

Similariteit searches –

Zoeken naar gelijkende sequenties in sequentie databanken ●

Korte sequentie (b.v. EST) waar we meer van willen weten –

–

●

Andere korte sequenties ● annotatie gegevens (mogelijk) ● uitbreiding sequentie (mogelijk) ● Homologe sequenties? (vergelijkende analyse) Genomische regio, gen ● Plaatsing in context

Annotatie van grote sequenties – –

b.v. Genomische regio's, kandidaat gebieden Waar liggen b.v. mRNA's, EST's, genen, gekende eiwit sequenties, etc.

Low complexity sequenties –

Low complexity sequenties ● ●

–

bv. Tandem repeats, GC rijke regio... Geven zeer gemakkelijk hits bij toeval (met niet gerelateerde sequenties)

Om deze te maskeren gebruikt men Filters ●

SEG voor proteïne HILCDEVNEGDEENEDFLPS HILCXXXXXXXXXXXXFLPS

●

DUST voor DNA GCTCAAAAAATAAAAACACG GCTCNNNNNNNNNNNNCACG

Low complexity sequenties –

Repeats ● ●

●

Simple repeats: korte herhaalde sequenties Stukken sequentie die vaak voorkomen in een genoom b.v. t.g.v transposons Moeten gemaskeerd worden voor een zoektocht – –

–

Geven enorm veel, niet informatieve hits Kunnen informatieve hits maskeren

RepeatMasker ● ●

Identificeert en maskeert repeats Methode – –

Database van gekende repeats (in verschillende genomen) Vergelijking query met database met behulp van dynamic programming

Dynamic programming search –

Methode ●

●

Optimale locale alignatie met dynamic programming -> zeer traag (voor alle sequenties in database) Om te versnellen gebruikt men – –

–

zeer grootte parallelle systemen (bv Maspar: verschillende PC's berekenen elk een deel ...) Hardware acceleratie ● CPU specifiek voor bepaalde algorithmen maken (bv. Bioccelerator, Genematcher, …) ● Speciale functies (oorspronkelijk voor versnelling van multimedia) van gewone cpus/gpus (bv. CLC Bio)

Servers ● ●

BLITZ Swsrch

Heuristiek –

Vorige (dynamic programming) ●

–

Alle mogelijke alignmenten van de query sequentie met alle databank sequenties worden gecontroleerd → steeds optimale oplossing (gegeven parameters) → traag

Heuristiek of approximatie ●

Niet alle mogelijkheden worden onderzocht, wel de meest waarschijnlijke –

●

●

bv. We kijken eerst op een andere snellere manier of een databank sequentie enigszins lijkt op de query, we gaan enkel verder met degene waarvoor dit het geval is

vind veel sneller gelijkende sequenties in grote databanken Geen garantie dat alle gelijkende sequenties worden gevonden

Fasta –

FastA ● ●

● ●

–

Fast Alignement, Methode van Pearson & Lipman Eerste veel gebruikte programma om similariteits searches te doen in databanken FASTA zoekt locale alignementen Gebruikt een heuristiek

Varianten ● ● ●

fastn (nucleïnezuren) fastp (proteïnen) fastx (vergelijkt DNA met proteïne sequenties)

FastA algoritme –

database sequence

–

query sequence

–

Zoekt naar korte identieke segmenten van lengte k (k-tuples, woorden) ● Maakt tabel met posities van elk woord in query ● Offset tabel met per positie: verschillen positie van woord t.o.v. posities in query ● ~ diagonalen in matrix Lengte k: belangrijk! ● bv. k = 10 → er is minstens 1 match van 10 identieke opeenvolgende basen/AZ nodig. ● Default – AZ: k = 2 – NZ: k = 6 Lagere k waardes ● Grotere sensitiviteit ● Langere zoektijd

Offset table Simpele voorbeeld offset tabel voor k=1 protein 1 n c s p t a . . . . . protein 2 . . . . . a c s p r k position in offset amino acid protein 1 protein 2 pos 1 – pos 2 ---------------------------------------------------a 6 6 0 c 2 7 -5 k 11 n 1 p 4 9 -5 r 10 s 3 8 -5 t 5 ---------------------------------------------------common offset for the 3 amino acids c,s and p protein 1 n c s p t a | | | protein 2 a c s p r k

FastA algoritme –

database sequence

– –

query sequence

–

Zoekt 10 beste regios of diagonalen ● In offset tabel: woord matches met dezelfde offset liggen op dezelfde diagonaal ● Beste regio → met meeste identiteiten (woord matches) → Woord matches dicht bij elkaar Scoort “initial regions” met behulp van de PAM matrix init1 score (= score beste regio) Gaat enkel verder wanneer init1 > cutoff

FastA algoritme –

database sequence

–

query sequence

Verwijdert intial regions < een opgegeven cutoff Verbindt segmenten ● eventueel nu ook op verschillende diagonalen) → initn score ● = som van scores samengestelde initiele regios ● aftrekken van “joining penalties” voor elke gap

FastA algoritme –

database sequence

–

query sequence

Beste lokaal alignement ● Terug te vinden binnen gebied gedefinieerd door segmenten ● Via Dynamic programming Geeft een optimized score s (opt score)

Scores van database searches Met welke score weet je zeker of 2 sequenties verwant zijn? Ideaal: perfecte discriminatie

Realiteit: overlap

cutoff

verwante sequenties Alignements score

Aantal sequenties

Aantal sequenties

niet verwante sequenties

cutoff? niet verwante sequenties verwante sequenties Alignements score FN

FP

FastA scores Statistiek om na te gaan hoe goed de scores zijn

●

z-score – –

S-μ

Frequentie

σs –

μs Alignements score

S –

Significantie van een alignment score S Correctie voor de verschillen in lengte n van de databank sequentie

●

σS = standaard deviatie S

●

μS = gemiddelde van S

Parameters worden geschat door fitting aan laag scorende alignementen in de databank 'laag' : arbitrair gekozen

Figuur: Distributie scores van niet verwante sequenties → S is significanter naarmate het verschil met het gemiddelde groter is → minder significant wanneer spreiding groter

FastA scores ●

Probability P –

●

Expect – – – –

●

Kans dat een databank sequentie (lengte n) en de query sequentie (lengte m) bij toeval een alignement met dezelfde of betere z-score zou opleveren Hoeveel hits met gelijkaardige of beter score kunnen op basis van toeval verwacht worden Liefst zo klein mogelijk (cut off standaard = 10) E = NP (N = aantal sequenties in databank; P= probabilteit) Hoe meer sequenties in een databank, hoe groter de kans dat er per toeval hits worden gevonden.

Bitscore – –

Score gecorrigeerd voor de schaal van het score systeem Onafhankelijk van het scoring systeem (vergelijking mogelijk tussen verschillende programmas, settings, databanken)

FastA beschikbaarheid ●

WWW – –

EBI http://fasta.bioch.virginia.edu/fasta

– ●

Lokaal –

kan gedownload worden

BLAST ●

Basic Local Alignment Search Tool – –

●

Meest gebruikte programma voor zoeken van locale alignementen via bv.NCBI Gebruikt ook heuristiek

Database –

Blastall vergelijkt ● ●

query in fasta formaat database in binair formaat – –

–

binair: 4 basen in 1 byte; zoektocht gaat sneller (itt FastA: waar de database ook in FastA formaat is) gemaakt met commando formatdb

Met bl2seq kunnen ook 2 sequenties in fasta formaat vergeleken worden

BLAST programs Query

Database

blastp

Proteïne

Proteïne

tblastn

BLAST search gevoeliger op protein niveau dan op DNA niveau

blastx DNA

blastn

DNA

tblastx 6 frame translation Beide sequenties omgezet naar alle mogelijke translaties, en dan vergeleken

6 frame translation

–

We willen alle mogelijke vertalingen van de DNA sequentie ●

●

–

Start op positie 1, 2 en 3 geeft verschillende vertalingen (blauw, rood, groen) Start op positie 4 geeft dezelfde vertaling als positie1 (zonder het eerste AZ), 5 als 2, ... → zelfde reading frame

6 frame translatie ● ●

3 reading frames in een sequentie Proteine kan afgeschreven worden van zowel forward als reverse strand → 6 reading frames

BLAST algoritme ●

●

BLAST zoekt eerst snel naar identieke sequenties van lengte W in de query en db → “word hits” Word size W –

Default ● ●

–

W = 3 voor AZ W = 11 voor NZ

Lagere W ● ●

Grotere sensitiviteit Langere zoektijd

BLAST algoritme

●

query sequentie: RLEGDCVFDGMIGSDQGSLRFDGFDVECDSPG RLE hashtable LEG EGD hash Table position position in seq ... 1 2 2 RLE:1 EGD:3 999 3 2 4 … Snelle search naar word hits 999 LEG:2 – alle woorden van lengte W in de 1000

–

query worden opgeslagen in een hash table De databank sequentie word sequentieel gescand

database sequentie: DLEGDCFFDGMIGSDWGSLRFDGFDVECDSPG DLE LEG EGD hash in hashtable in query ... 3 Leeg niet in query LEG:2 positie 2 999 RLE:1 EGD:3 positie 3 2

BLAST algoritme

●

query sequentie: RLEGDCVFDGMIGSDQGSLRFDGFDVECDSPG GSD 16 gelijkenis score voor elke GAD 13 mogelijkheid GTD 13 GDD 12 Neighborhood word list GED 12 – Ook gelijkende woorden GGD 12 in hash table GSE 12 – afhankelijk van score GCD 11 matrix GHD 11 GMD 11 GSN 11 GID 10 GLD 10 Opgenomen tot een GVD 10 bepaalde score T

T = 11

BLAST algoritme ● ●

BLAST1: Word hits worden uitgebreid tot HSPs HSP: High-scoring Segment Pair –

Optimaal lokaal alignement zonder gaps ●

●

●

Paar van segmenten uit query en database sequentie van gelijke lengte Alignement score kan niet meer worden verbeterd door het gebied uit te breiden of in te krimpen Score bepaald op basis van score matrix –

–

default BLOSUM62

Score beter dan een vooraf opgegeven 'treshold' of 'cutoff' waarde

BLAST algoritme ...DGMIGSDQGSL... ...+G G+D GS+... ...NGQRGTDVGSV...

●

Woord hit links en rechts uitbreiden uitbreiden – Voor elk paar gealigneerde AZ score uit score matrix bij totaal tellen – Stop wanneer totaal score onder een gegeven waarde zakt – Segment afkappen op maximale score

totaalscore

G S D Q G S L R F D G F D V E C G T D V G S V M D E I P N D F E Uit Score matrix 6 1 6-2 6 4 2-1-3 2-4-4 1-3-3-4

BLAST 2 (gapped BLAST) ●

2 hit criterium –

●

woord hit wordt slechts uitgebreid als er een tweede woord hit is binnen een afstand A (default = 40 AZ); → dit verhoogt de snelheid van de search

Optimaal lokaal alignement met gaps –

Als de score van HSP hoger is dan een gegeven score Sg

–

Dynamic programming methode om alignement te zoeken

BLAST scores –

Expect value ●

–

Aantal verwachte toevallige hits met dezelfde of betere score dan de score S van deze hit

E = mnKe-λS ● ● ●

m= lengte query n = lengte database (som lengte van alle sequenties db) K en λ – – –

λ en K zijn parameters geassocieerd met het score systeem In BLAST 1 zijn deze parameters theoretisch afgeleid In BLAST2 ● Kan niet theoretisch afgeleid worden door de gaps ● fit aan gesimuleerde resultaten met random seq en random databases (random sequentie model) ● Voor een selectie van score matrices, gap costs → enkel deze combinaties kunnen gebruikt worden als parameters

BLAST scores –

Probability P ●

●

Kans dat alignement met een score ≥ S per toeval zou kunnen gevonden worden Kan afgeleid worden van Expect value E P = 1 – e-E

–

Bit score ●

●

●

Score gecorrigeerd voor de schaal van het score systeem. Maakt het mogelijk om scores van verschillende soorten searches te vergelijken Afhankelijk van berekende parameters en score

BLAST beschikbaarheid ●

Via web: – –

●

Lokaal – –

●

EBI NCBI kan gedownload worden Zelf database maken

Commandline client – –

Blastcl2 Locale databases of databases op web

Specifieke vormen BLAST ●

Varianten/op BLAST gebaseerde tools –

Megablast ●

–

Blat ●

●

●

sneller zoeken naar sterk gelijkende sequenties, langere seq mogelijk (grotere word size, greedy alignment) Sneller zoeken naar (sterk gelijkende) sequenties in genoom db (genoom) wordt in hashtable bijgehouden ipv. query

Specifieke vormen (patroon gerelateerde) – – –

PSI-BLAST: Position Specific Iterative BLAST PHI-BLAST: Pattern Hit Initiated BLAST RPS-BLAST: Reverse Position Specific BLAST → Zie Hoofdstuk 7: Profielen

Conclusies ●

Proteïne searches zijn gevoeliger dan DNA – – –

groter alfabet (DNA bij toeval 25% identiteit) score matrices Query mogelijk coderend DNA: ●

●

beter searches op proteïne niveau: blastx, tblastn, tblastx

Welk programma –

BLAST beter dan FastA op proteïne niveau ● ●

–

Neighboring words: grotere sensitiviteit HSP's komen vaak op geconserveerde kern

FastA beter voor niet coderend DNA ●

Meer inserties/deleties -> geconserveerde kernen zijn kleiner

BLAST of FastA Snelheid

SW

BLAST1 BLAST2

fastA

Sensitiviteit bij zoeken naar proteïne of vertaalde DNA sequenties

fastA

BLAST1 SW BLAST2

Sensitiviteit bij zoeken naar DNA sequenties

BLAST SW: Smith & Waterman: Dynamic Programming

fastA SW

Conclusies ●

Databank groter – –

grotere E values Meer vals positieven → Gebruik kleinere databanken kan noise beperken ●

Beperken databank tot een sub set –

●

bv. Enkel humane sequenties, enkel mRNA, ...

kleinere databank (indien mogelijk/nuttig) – –

bv. humane genoom databank ipv. Volledige nucleotide db bv. swissprot ipv. Volledige proteine db

●

Gevaren –

Als een gebied van query heel veel hits geeft – – –

– – –

b.v. frequent voorkomend domein Andere hits worden gemaskeerd Nieuwe search met query waar dit gebied uitgefilterd werd

Similariteit betekent niet steeds homologie, homologie betekent niet steeds zelfde functie De beschrijving van een hit sequentie slaat niet per se op de regio waar de hit zich bevindt Database annotaties zijn niet altijd betrouwbaar ●

Incompleet, putative (= mogelijk/niet zeker), fouten