Bio-informatica
Les 2
There are 3 major primary nucleotide sequence databases:
1. ENA or European Nucleotide Archive (European Bioinformatics Institute, Europe)
2. GenBank (National Center for Biotechnology Information, USA)
3. DDBJ or DNA Data Bank of Japan (National Institute of Genetics, Japan)
Together they form the International Nucleotide Sequence Database Collaboration, INSDC
NCBI = US based organisatie die referentie databases bevat
➢ MedGen is een NCBI database die meer info bevat over oorzaak en fenotype van de ziekte,
relevante publicaties, enz.
➢ Gene database, bevat informatie over genen
➢ Genbank, bevat een collectie van DNA sequences
➢ dbSNP, database for nucleotide varieties
UniProt → database om een lijst van eiwitten met hun aminozuursequenties te downloaden
De protein databank → Database voor 3D structuren
Nucleotide database → Een collectie van sequences van meerdere bronnen zoals GenBank, RefSeq
and PDB
- GenBank → een verzameling van alle openbaar beschikbare DNA-sequenties.
WebLogo → visueel zoeken naar motieven in een multiple sequence alignment
InterPro → Voor het vinden van gekende proteïne domeinen in een protein
ProSite → is gespecialiseerd in het verzamelen van informatie over functionele profielen en patronen
MEME → Vindt motief met De novo
Chou Fasman method → Identificatie van secundaire aminozuursequenties
Kyte&Doolittle method → Identificatie van hydrofobe patches in aminozuursequenties
Aantal Multiple sequence alignment tools:
➢ Clustal Omega
➢ Clustal W (progressive)
➢ T-Coffee
➢ MUSCLE (iterative)
➢ MAFFT (iterative)
Het meest gebruikte algoritme om een database search te doen is BLAST.
Algoritme met Heuristic methods
1. FASTA
2. BLAST
3. MSA
a. Lipman MSA algoritme
b. Feng en Doolittle algoritme
c. CLUSTALw
d. MUSCLE
e. SAGA
f. T-COFFEE
1
,Hoofdstuk 2. Background
Flat Files:
- Collectie van data
- Files zonder tekstopmaak
- Er zit geen metadata in.
Relationele database:
- Bestaat uit tabellen (denk aan excel)
Algoritmes
= Set van procedures/regels om een probleem op te lossen of andere probleemoplossende taken.
Data problemen → Algoritmen → Oplossing
Traditionele algoritmes = procedures geprogrammeerd door een software ingenieur
Recente algoritmes = artificial intelligence, computers te leren om zelf te ‘denken’
Algoritme komen vaak met bepaalde assumpties. Een correcte outcome kan alleen worden
gegarandeerd als deze aan de assumpties voldoen.
Voorbeeld algoritmen:
Input: Een DNA sequentie en een genetische code tabel.
Output: Alle (6) mogelijke proteïne sequenties dat kan voortkomen uit de gegeven DNA sequentie
Binaire Classificatie
Type I fout = False positives
Type 2 fout = False negatives
Sensitiviteit en specificiteit kunnen berekenen
Bij een perfecte test, zijn de specificiteit, sensitiviteit en accuraatheid 100%
2
,ROC analyse
Receiver operating characteristic.
➢ Illustreert de performance van een binair classificatiesysteem als de discriminatie drempel wordt
gevarieerd.
➢ Plot van de fractie van TP uit de totale werkelijke positieven (TPR of sensitivity of recall) versus
de fractie van FP uit de totale werkelijke negatieven (FPR, fall-out of 1-specificiteit), bij
verschillende drempel instellingen
We gaan dus met een variërende beslissingsdrempel de relatie tussen specificity en sensitivity plotten
Graph theory (Graaf- / Grafentheorie)
Graaf is een representatie van gegevens als een netwerk.
network representation of relations (edges, connectie) between elements (nodes, knooppunten) of a
certain group.
Clique = een connectie van nodes en edges die sterker met elkaar geconnecteerd zijn dan met de
buitenwereld.
Soorten graven
1. Undirected, ongericht
2. Directed, gericht
3. Mixed, gemixt
Node degree = aantal edges verbonden met een node
Node degree van node 5 is 3
Node degree van node 6 is 1
3
,Voorbeeld Graven
Dataset van 6 elementen, die op een welbepaalde manier met elkaar verbonden zijn.
In deze graaf zijn 7 edges en 6 nodes.
Undirected graph = er is geen richting van de edges (geen pijltjes)
De bijbehorende matrix:
Er staat een 1 op de plek als de nodes met elkaar verbonden zijn, en een 0 op de plek als de nodes
niet met elkaar verbonden zijn.
➢ Merk op dat deze matrix symmetrisch is tov van de diagonaal, dit is altijd zo bij een undirected
(ongerichte) graaf.
Je kan ook een bijbehorende lijst maken, de adjacency list. In deze lijst geeft aan welke nodes buren
van elkaar zijn
Je kan tussen verschillende nodes een pad vinden. Je wilt bijvoorbeeld een pad vinden tussen node 6
en node 2, dit kan op meerdere manieren (soms zijn er geen manieren)
Node degree = aantal edges verbonden met een node
Node degree van node 5 is 3
Node degree van node 6 is 1
4
,Path = een manier om 2 knooppunten met elkaar te verbinden via de edges. Vaak (niet altijd) zijn er
meerdere paden mogelijk.
Kortste pad = pad dat de kortste weg is tussen 2 nodes, dus via zo weinig mogelijk edges.
Dijkstra’s algoritme = berekent de kortste weg van de gegeven nodes
Floyd-Warshall algoritme = berekent de volledige afstandsmatrix
Big-O notatie = Notatie om te beschrijven hoe de tijd of geheugen van een algoritme toeneemt als een
probleem toeneemt.
- Bijvoorbeeld als je meerdere sequenties toevoegt → Input sequentie wordt langer en hoeveel
meer rekentijd en computergeheugen ga je dan nodig hebben
Als je een probleem van de grootte n hebt, dan duurt het O(n) tijd voor het algoritme om dit te
berekenen, als de tijd lineair is.
Voorbeeld
Je hebt een lange tekst en het algoritme moet 1 specifiek woord gaan vinden in die tekst. De tijd om dit
te vinden zal lineair toenemen met de lengte van de tekst.
Als de tekst 2x zo lang is, zal de tijd ook 2x zo groot worden om het woord te vinden.
Complexiteits klassen
P problemen = kan opgelost worden in polynomiale tijd
NP problemen = geen efficiënte manier om op te lossen, maar een kandidaat oplossing kan worden
gecheckt in polynomiale tijd.
NP complete problemen = moeilijkste typen van NP problemen
NP hard problemen = niet alleen NP, en ook nog erger dan de NP complete problemen.
2 methoden om problemen op te lossen:
1. Exhaustive methode → Brute kracht methode (brute force method). Computer alle mogelijke
oplossingen laten maken en deze dan laten testen
a. Dit is vrij eenvoudig, maar gaat zeer langzaam bij grote input van data
b. Geeft gegarandeerd een oplossing/antwoord
2. Heuristic methode → Gaat alleen de oplossingen evalueren die meest waarschijnlijk goede
oplossingen zijn.
a. Meer geavanceerd en probleem-specifieke programmering
b. Meer efficiënt voor grotere problemen
c. Geeft niet gegarandeerd een oplossing/antwoord
Voorbeeld:
Vind de term init I in de bio-informatica cursus.
Dit kan je doen op 2 manieren
1. Met brute force → scan elke pagina totdat je de term hebt gevonden
2. Met Heuristic method → start screening het BLAST en FASTA hoofdstuk
Iterative improvement = stapsgewijs verbeteren, waarin we vertrekken met een initiële oplossing, je
gaat dan evalueren hoe goed is dit. Is dit voldoende goed? Zo niet kan je de kandidaat oplossing
modificeren en opnieuw evalueren, dit process doe je totdat de oplossing goed genoeg is
Search space = set van alle mogelijke oplossingen van een probleem
Objectieve functies = functie die een waarde geeft die de kwaliteit van kandidaat-opties aangeeft
5
,Een aantal typische optimalisatie methoden;
➢ Hill climbing = Een random functie proberen te verbeteren
➢ Simulated annealing = wordt wederom een iteratie optimalisatie uitvoeren. Laat suboptimale
oplossing toe om onderzocht te worden
➢ Evolutionaire algoritmen = algoritmen die aan optimalisatie doen (door bijv hill climbing), door
middel van de parameters van de huidige positie te veranderen.
6
, Les 3
Hoofdstuk 3; pairwise alignment
Paragraaf 3.1 Introduction
Aligneren = onder elkaar zetten (vergelijken) van 2 sequenties, kan DNA, RNA of eiwit seq zijn.
Mismatch = een verschil tussen 2 letters in beide sequenties. Zijn vaak het gevolg van substitutie
doorheen evolutie.
➢ hamming distance = aantal mismatches
➢ Mismatches zijn vaak het gevolg van substituties door evolutie.
Gap penalty = Een methode om alignment van twee of meer sequenties te scoren. Bij het aligneren
van sequenties kan het introduceren van gabs in de sequenties een alignment algoritme in staat stellen
om meer termen te matchen dan een alignment zonder tussenruimte. Het minimaliseren van gabs in
een alignment is echter belangrijk om een bruikbaar alignment te creëren.
Te veel gabs kunnen ertoe leiden dat een alignment zinloos wordt.
Gap-penalties worden gebruikt om alignment scores aan te passen op basis van het aantal en de
lengte van de gaps.
het introduceren van gabs direct na andere gabs wordt beïnvloed door de gap extension penalty.
Database voor 3D structuren → De protein databank
Paragraaf 3.2 Dot matrix method
substitutie matrix = matrix die waarde bevat die corresponderen met de kans dat de gegeven
aminozuur wordt gesubstitueerd door een ander aminozuur
𝐴𝑎𝑛𝑡𝑎𝑙 𝑔𝑒𝑜𝑏𝑠𝑒𝑟𝑣𝑒𝑒𝑟𝑑𝑒 𝑠𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑖𝑒𝑠 𝑡𝑢𝑠𝑠𝑒𝑛 𝑎 𝑒𝑛 𝑏
Substitutie waarschijnlijkheid = s (a,b) = Log ( )
𝐴𝑎𝑛𝑡𝑎𝑙 𝑣𝑒𝑟𝑤𝑎𝑐ℎ𝑡𝑒 𝑠𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑖𝑒𝑠 𝑡𝑢𝑠𝑠𝑒𝑛 𝑎 𝑒𝑛 𝑏
Alignment score = S = Σ(𝑠𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑖𝑒 𝑠𝑐𝑜𝑟𝑒)
→ Zegt hoe gelijkaardig 2 sequenties t.o.v. elkaar zijn.
➢ Als de sequenties op elkaar lijken zal S hoog zijn
➢ Als de sequenties niet erg op elkaar lijken zal S laag zijn
Er kunnen ook gabs voorkomen in een sequentie. Een gab is een gevolg van een insertie of deletie in
een van de alignment sequenties, kan voorkomen doorheen de evolutie.
7
, Verbeterde alignment score s = Σ(𝑠𝑢𝑏𝑠𝑡𝑖𝑡𝑢𝑡𝑖𝑒 𝑠𝑐𝑜𝑟𝑒) - Σ( 𝑠𝑐𝑜𝑟𝑒 𝑣𝑎𝑛 𝐺𝑎𝑝 𝑝𝑒𝑛𝑎𝑙𝑡𝑖𝑒𝑠)
Optimale alignment = Max (s) = de hoogst mogelijke alignment score
Pairwise alignment = vergelijken van 2 sequences.
Multiple alignment = vergelijken van 3 of meer sequenties.
Global alignment = De 2 volledige sequenties met elkaar vergelijken
- vooral goed voor 2 gelijkende sequenties van ongeveer dezelfde lengte
Local alignment = Vergelijkt stukjes van een sequentie waar voldoende gelijkenissen zijn
Similarity = Zegt iets over de mate waarin 2 nucleotide of eiwitsequenties op elkaar lijken
Identity = hoeveel karakters zijn er identiek. Stel je hebt 70% identity, betekent dit dat de 2 sequenties
voor 70% identiek zijn aan elkaar.
Conservation = Behoud van fysicochemische eigenschappen
Homology = eiwitten met een gemeenschappelijke voorouder.
- Orthologie = homologe sequenties in verschillende species die voortkomen uit
gemeenschappelijke voorouderlijke genen tijdens soortvorming.
- Paralogie = homologe sequenties binnen 1 soort species, voortkomend uit genduplicatie.
- Xenologie = sequenties die komen van laterale transfer van genen
- Analogie = gelijkaardige sequenties zonder gemeenschappelijke voorouder
Alignment matrix / dot matrix
1. Zet sequentie A verticaal van de matrix en sequentie B horizontaal van de matrix
2. Zet een marker op de plekken van de aminozuren die identiek zijn (dus m&m, a&a etc.)
3. Zoek naar regio's (een opeenvolgende diagonaal) die gelijkheden vertonen
a. Diagonaal = overeenkomst tussen beide sequenties
b. Mismatch = een ontbrekend kruisje in de diagonaal
c. Gab = verticale / horizontale shift
8
