Samenvatting HCO algoritmes voor sequentie alignments

Algoritmes voor sequentie alignments
Algoritme, is als het ware een set van regels die je steeds opnieuw afloopt. Er zijn algoritmes die je
kan gebruiken om sequentie alignments te maken.
Alignment, als je twee sequenties hebt: seqX (X1X2…XM) en seqY (Y1Y2…YN) kan je daar een alignment
van maken. Dat doe je door gaps toe te voegen vanaf positie 0, …, M in X en vanaf positie 0, …, N in Y,
waardoor elke letter van de ene sequentie tegenover een andere letter of gap staat in de andere
sequentie. Bij een alignment maak je beide sequenties dus even lang en leg je ze naast elkaar.
Optimale alignment, is de alignment die het meest consistent is met het model van evolutie. Bij
aminozuren gebruik je dan bijvoorbeeld BLOSUM62 en bij DNA de identity matrix. De optimale
alignment vertoont hierbij de meeste similarity of de hoogste identity in het geval van DNA.
Eisen alignment, een alignment moet betrouwbaar zijn en de gaps moeten dus niet random
toegevoegd zijn. De methode om een alignment te verkrijgen, moet reproduceerbaar zijn en dus kan
je een algoritme maken om sequenties te alignen. Vandaar dat we hiervoor computers gebruiken. Zij
voeren altijd de dezelfde stappen uit, terwijl het bij een mens nog weleens fout kan gaan.
Local alignment, hierbij wordt een deel van een aantal sequenties met elkaar vergeleken en je
bent dan op zoek naar de optimale sub-alignment binnen twee sequenties. Hier ga je er dus vanuit
dat de sequenties gedeeltelijk homoloog zijn en de rest is dan niet evolutionair verwant (homoloog).
Dat kan komen door exon shuffling of door domein insertie.
Global alignment, alignt twee sequenties van begin tot eind. Dit kan je toepassen als je weet
dat twee sequenties geheel homologen zijn, doordat er bijvoorbeeld gen
duplicatie heeft opgetreden.
Identity waarnemen, een manier om te achterhalen of sequenties identieke
(sub-)sequenties hebben, is door ze uit te zetten in een tabel. Hierbij zet je de ene sequentie uit
tegen de andere sequentie en ga je scores toedienen of aangeven op welke plekken
overeenkomsten zijn. In de tabel ga je dan op zoek naar een reeks residuen die hetzelfde zijn. Zo
zie je rechts een diagonaal aangegeven en dat figuur noem je een alignment matrix. Deze diagonaal
moet altijd van linksboven naar rechtsonder lopen, omdat sequenties een richting hebben (DNA: 5’
→ 3’ eiwit: C → N).
Alignment matrix, soms kom je diagonalen tegen in een aligment matrix die op
een positie onderbroken worden, doordat een G bijvoorbeeld gemuteerd is in
een C. Om dit soort onderbrekingen uit te sluiten, gebruiken we scores. Denk
hierbij aan similarity scores. In een alignment matrix kom je soms ook twee
diagonalen tegen waar als het ware een gat tussen zit (zoals rechts is
weergegeven). In dat geval heeft er een insertie (bij de horizontale sequentie) of
een deletie (bij de verticale sequentie) plaatsgevonden. Aangezien we hier niet
weten welke van de twee gebeurtenissen heeft plaatsgevonden, noemen we het
een indel.
Algoritme opstellen, om een alignment te maken, moet je een algoritme opstellen.
Daarvoor heb je een scoringssysteem nodig. Denk hierbij aan een substitutie matrix
waarin aangegeven is hoeveel (min)punten een match of mismatch oplevert en wat
de gap penalty is. Deze scores zijn gebaseerd op een model van evolutie. Hierin geven
we met getallen weer hoe waarschijnlijk het is dat elk mutatietype plaatsvindt. Zaken
die hoogst waarschijnlijk plaatsvinden krijgen hoge scores en zaken die minder
waarschijnlijk zijn, krijgen lagere scores (hogere penalties/straffen). Dit is terug te zien
in de substitutie matrix die hiernaast is weergegeven, aangezien we er bij evolutie vanuit gaan
dat zaken geconserveerd blijven. A-A krijgt dan ook een positieve score, terwijl A-C een
negatieve score krijgt. Bij het opstellen van een algoritme vormen de matrix en gap penalty
dus je model van evolutie. Met deze wijze van scoring, gaan we terug naar de alignment
matrix en gaan we cel voor cel een score toedienen. Als de residuen op een bepaalde positie
gelijk aan elkaar zijn, krijgt de cel een +1 score. Als de residuen niet aan elkaar gelijk zijn, krijg de cel
een -1 score. Deze scores zijn relatief aan het naastgelegen vakje en je telt deze score dus op bij de

, score uit dat vakje (zie ‘scores optellen’). Zo zou de eerste diagonaal in naaststaande alignment matrix
een score van +5 hebben en de tweede een score van +3.
Gap penalty, de waarde die we aan gap toekennen is altijd negatief. Dit tel je op bij de substitutie
score.
Scores optellen, van een bepaalde cel (X) kan de alignment vanuit 3 richtingen komen:
- Diagonaal, hierbij komt de alignment vanuit linksboven (U) en dit indiceert een
alignment van residuen. b en d liggen dus boven elkaar in de alignment. De score van X
is in dat geval: score van U + substitutie score(b , d) .
- Vanaf boven, hierbij komt de alignment vanuit boven (V) en dat geeft aan dat er een gap
in de horizontale sequentie zit (vanwege een indel). De score van X is in dat geval:
score van V −gap penalty .
- Vanaf links, hierbij komt de alignment vanuit links (W) en dat geeft aan dat er een gap in de
verticale sequentie zit. De score van X is in dat geval: score van W −gap penalty . Let
hierbij op dat je niet uit gaat rekenen dat de score score van W −−2 is, want dan tel je
gap penalty er juist bij op. Als de gap penalty dus al negatief is, moet je hem er juist bij
optellen.
Elke keer moet je de optie kiezen die tot de hoogste alignment score leidt. Dit garandeert uiteindelijk
de optimale alignment score voor elke combinatie van posities in de twee sequenties. Bij het
opstellen van een matrix waarin je deze scores verwerkt, begin je altijd links bovenin.
Voorbeeld alignment matrix, in naastgegeven matrix
begin je links bovenin en dat levert je een score van 1,
omdat A en A een match zijn. Als je nu vanuit de V positie
de alignment score verder zou maken, zou dat
1−2=−1 opleveren, maar in deze matrix worden
getallen onder de 0 niet gebruikt en vandaar dat er 0 staat.
De W positie zou hier hetzelfde opleveren, maar de X
positie is een match en dus gaan we verder naar die
positie wat ons een alignment score van 2 ( 1+1=2 )
oplevert. Zo loop je de hele matrix rij, voor rij, voor rij af
en dat levert diagonalen op met de hoogste score op de
positie waar ze ophouden. Zo zie je dat de diagonaal die
linksboven begint tot aan een score van 12 identiek is.
Daarna begint de score af te nemen, omdat er een C
tegenover een T staat. De optimale local alignment score binnen een alignment vindt je dan ook door
het hoogste getal in de matrix op te zoeken en deze te volgen tot die 0 wordt. In dit geval volgen de
beste en een-na-beste alignment score elkaar best netjes op en kan je zeggen dat er een indel heeft
plaatsgevonden.
Model of evolution? Je kan afvragen of bovenstaand model van evolutie wel het beste model is. Je
rekent nu namelijk voor elke insertie of deletie dezelfde straf. Je zegt dus dat de kans dat een gap
ontstaat even groot is als de kans op het verlengen van een gap. Indels zijn over het algemeen enkele
evolutionaire gebeurtenissen en je wil dus niet elk residu wat tegen een gap gealigned is minpunten
geven. Het model van evolutie kan zich hier op aanpassen door verschillende gap penalties te
gebruiken:
- Gap open penalty: is een hoge straf om de (on)waarschijnlijkheid dat een indel in de evolutie
plaatsvindt aan te geven.
- Gap extension penalty: is een 0 of lage penalty om de waarschijnlijkheid van de evolutionaire
gebeurtenis aan te geven desondanks de lengte van het indel.
Zo kan je een gap open penalty van -2 hanteren een gap extension penalty van 0.
Gaps, zijn het resultaat van inserties of deleties in een sequentie. Een bepaalde insertie of deletie is
waarschijnlijk één evolutionaire gebeurtenissen desondanks zijn grootte. Een bioloog kan kiezen hoe
die indels bestraft: