Dit is een uitgebreide samenvatting van het hoorcollege over hoofdstuk 8 uit de reader. In het geel staan dingen gemarkeerd die nog niet helemaal duidelijk zijn. Daar verwacht na het hoorcollege van maandag meer duidelijkheid over te geven. Onderwerpen die hier naar voren komen, zijn: heuristieken,...
Heuristic searches
Heuristieken, als je in een grote dataset van sequenties op zoek bent naar een homologe sequentie,
zou dat veel te lang duren om het met dynamic programming te vinden. Vandaar dat we hiervoor
heuristieken gebruiken. Dat zijn als het ware trucjes waarmee je hoogstwaarschijnlijk het juist
antwoord krijgt. Hier staat geen garantie op, omdat er een paar zaken aangenomen worden bij
gebruik van heuristieken.
Zoeken in een database, stel je wil de sequentie TGCTGCAGGACAACAGTT opzoeken in een database,
dan kan je dit bij google intikken, aangezien google een database heeft van alle woorden die op het
internet aanwezig zijn, maar dan moet dit specifieke woord wel aanwezig zijn. Google geeft vaak de
opties of je naar … op zoek was als je een verkeerd woord intypt, maar google kan niet elke mogelijke
mutatie van een sequentie opslaan. Google heeft als het ware een hele grote index aan woorden in
zijn geheugen en hij weet precies van elk woord waar het staat. Dan gaat google verschillende
internetadressen met elkaar vergelijken en geeft die sites waarop al jouw zoekwoorden aanwezig zijn.
Dit zou je ook met DNA kunnen doen door alle ‘woordjes’ in het RAM van een computer op te slaan.
Zo kan de computer heel snel bepaalde sequenties vinden. Die ‘woordjes’ die je opzoekt zijn soms
echter genen van duizenden nucleotiden en het opslaan van mogelijke combinaties van lange
woorden kost heel veel geheugen (en dat heb je niet). Je kan dit probleem verhelpen door lange
sequenties (woorden) op te knippen in kleinere sequenties: k-mers. Deze passen misschien wel in
je RAM. In de afbeelding zie je hoe je een eiwit sequentie in 5-mers knipt. Je kan een index van alle
k-mers die voorkomen in een database sequentie opslaan in het RAM. Alle k-mers kunnen opgeslagen
worden tot k≈20 voor nucleotiden en k≈9 voor aminozuren (, omdat er meer AZ zijn dan
nucleotiden). Zo kan je voor de Genbank database alle k-mers in het RAM opslaan. k≈20 en k≈9 is
best wel kort, maar je moet ook niet hele lange woorden opslaan, want als er dan 1 mutatie
plaatsvindt kan je een gehele k-mer van 20 nucleotiden al niet meer vinden. Je zou je ook af kunnen
vragen of het mogelijk is om alle mogelijke k-mers in de database op te slaan dus dat je alle k-mers
inclusief de mogelijke mutaties opslaat, maar dat zou heel veel RAM nodig hebben en zou de
zoektocht naar exacte matches limiteren.
RAM, random acces memory, een computer programma kan snel element vinden die in de RAM
opgeslagen staan. Hierdoor kan de computer bepaalde zaken/woorden heel snel terugvinden.
k-mer, bestaat uit k nucleotiden of aminozuren.
Transcriptomics, in het geval van transcriptomics kan het soms wel handig zijn om alle mogelijke k-
mers in de database op te slaan (inclusief mogelijke mutaties). Als je namelijk weinig mutaties
verwacht tussen de query (zoekopdracht) en gegevens uit de database kan je een k-mer goed
terugvinden. Dat is bijvoorbeeld het geval bij transcriptomics van een genoom waarvan je een hele
goede referentie hebt. Zo heb je voor de mens het human reference genome wat uit 3 miljard basen
bestaat en dus makkelijk in het RAM opgeslagen kan worden. Als je dan bijvoorbeeld DNA uit een
tumor illumina sequenced en dan vergelijkt met exacte matches met het human reference genome
weten we dat 1-5 miljoen basen kunnen verschillen van persoon tot persoon. Dat is echter maar een
klein gedeelte en je kunt dus door exacte matches een groot deel van de sequentie direct herkennen.
Zo kan je dus achterhalen welke genen er in de tumor tot expressie komen.
Hier wordt gesproken over het moment dat een k-mer search wel goed van pas zou kunnen komen,
maar over wat voor soort k-mer search gaat het nu? Eentje waarin je alle mogelijk mutaties ook
opneemt? Zo ja, waarom?
Metagenomics, hierbij is de referentiedatabase niet altijd dicht verwant aan je monster. Zo zijn alle
virussen en bacteriën in oceaanwater erg verschillend (deze muteren constant). Dan kan je dus niet
verwachten dat ze veel overeenkomen met je database die bovendien groter is dan 100 miljard
nucleotiden. Alleen als je met hele korte k-mers in je RAM gaat werken, kan je verwachten dat je
matches krijgt met nucleotiden uit je monster, maar korte k-mers als ATGA kunnen overal terecht
komen daar heb je dus vrij weinig aan. Als je de sequenties uit je monster met langere k-mers gaat
vergelijken, zal je lang niet alle sequenties vinden. Je moet dus zorgen dat je database dicht verwant
, is aan het monster waar je het DNA uithaalt, want je hebt er niks aan om metagenomen met een
database te vergelijken die weinig overeenkomsten heeft.
Index search, is gelimiteerd tot exacte matches en exacte matches in RAM zijn snel, maar limiteren je
resultaten. Index search kan geschikt zijn voor het menselijke transcriptoom, maar de genetische
variatie die optreedt door bepaalde mutaties van kanker zullen niet exact matchen met het human
reference genome. Heel veel mutaties kan je dus niet identificeren met deze methode. Bij
metagenomen is het het geval dat elk micro-organisme wat je tegenkomt anders is. Je zal hierbij
nooit exact dezelfde sequentie terugvinden. Daarbij zitten er ook verschillen tussen virussen,
schimmels, protisten etc.
Natural sequence diverge, in de afbeelding zie je de seqeunce
van een metagenoom uit zeewater. We weten dat de bacterie
SAR86 voorkomt in zeewater en daarvan is het genoom ook
aanwezig in de database. Als je dan het zeewater gaat alignen
tegen het referentiegenoom zie je dat een groot deel van de hits bovenaan zit met bijna 100%
identiteit. Het blijft echter bij 97% en deze reads zijn dus niet geheel identiek, maar het komt wel
zoveel overeen dat je het tot SAR86 mag rekenen. Deze sequenties behoren dus tot een strain die
nauw verwant is aan het referentiegenoom. Daaronder zie je nog een gebied wat wel tot 50%
verschillend is en deze organisme zijn SAR86-like en behoren waarschijnlijk tot hetzelfde genus of
dezelfde familie, maar niet tot dezelfde soort zoals de 97% groep wel tot dezelfde soort behoort. Je
hebt dus een ander algoritme nodig voor metagenomen waar een natuurlijke variabiliteit in
voorkomt.
Best of both worlds, we willen dat we snel kunnen zoeken, maar we willen ook dat we heel gevoelig
kunnen zoeken voor de mogelijke mutaties die we in de natuur aantreffen. Als je meer evolutionaire
divergentie (verschillen) toestaat in je hits:
Zal je zoekopdracht gevoeliger zijn (en kan die distant homology waarnemen)
…maar je kan nooit alle mogelijke variaties opslaan in de RAM
…dus is het nodig om sequentie alignment te gebruiken (al kost dat veel CPU operaties).
Als oplossing kan je het beste van beide werelden combineren:
- Snel potentiële hits vinden door exacte k-mers te gebruiken die in een index zijn opgeslagen
(RAM).
- Je wil alleen de sequenties gaan alignen waarin je al een aantal goede k-mers hebt gevonden
(CPU).
Je gaat dus eerst op zoek naar k-mers die kort genoeg moeten zijn om distant homologs te vinden
waar veel mutaties in zitten en vervolgens ga je alleen een alignment maken voor de sequenties
waarin een exacte k-mer is gevonden.
BLAST, basic local alignment search tool, dit algoritme vindt potentiële homologen met een redelijke
snelheid. Hierbij past die hetgeen toe wat onder ‘best of both worlds’ beschreven staat. Zoals in de
naam al vermeld staat, gaat BLAST op zoek naar local alignments en het is maar liefst 10 tot 50 keer
sneller dan Smith-Waterman. Bij een blast search voer je je query in en dat levert dan een hit/subject
op. Dat is een similar sequentie die in de database aanwezig is. BLAST is het meest gebruikte
programma voor bio-informatici. Er zijn ondertussen snellere algoritmes dan BLAST beschikbaar:
DIAMOND & USEARCH.
BLAST algoritme, dit algoritme bestaat uit de volgende stappen:
1. Eerst ga je op zoek naar alle woordjes van een lengte W in je query. Volgens de default
settings van BLAST is W voor eiwitten 3 aminozuren en voor DNA 11 nucleotiden. Deze
woordjes in de query kan BLAST een beetje muteren op basis van de BLOSUM matrix om ook
te kijken naar woorden die in de buurt van de query liggen.
2. BLAST vindt snel similar woorden in de database en deze similar woorden worden bepaald
door de substitutie matrix (BLOSUM62 voor eiwitten en identity matrix voor DNA). Alle
woorden in de database sequenties zijn in het RAM opgeslagen en de index stelt dan ook snel
alle potentiële hits vast. BLAST vermenigvuldigt hierbij al best snel het aantal woordjes
waarmee die zoekt om waarschijnlijke mutaties mee te kunnen nemen. De grens van de score
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller brittheijmans. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.23. You're not tied to anything after your purchase.
