Bio-informatica
H1 Computer science background
1.1 Databases
Er zijn verschillende manieren om data te bewaren:
Papier
Flat files
o Geen structuur
o Geen metadata geen uitleg wat wat is, geen uniform systeem
Vb.: excel document, word document etc.
Databases 2 soorten:
1. Relationele
2. NoSQL
Relational databases
Gegevens opgeslagen in een reeks tabellen die met elkaar verbonden zijn door een
gedefinieerde logica kunnen hier gerichte vragen aan stellen
NoSQL databases
Alles wat niet efficiënt in een gewone databank past, kan hierin
1.2 Algorithms
Algoritme = set aan regels om mee te rekenen, meestal uitgevoerd door een computer
programma MAAR is niet noodzakelijk
Voorbeelden zonder computer: staartdeling, routeplanner
VROEGER: traditionele algoritmes werden geproduceerd door een software engineer
NU: algoritmes die geoptimaliseerd worden a.d.h.v. voorbeelden self-learning of
machine learning (AI)
! LET OP: algoritmes komen met bepaalde assumpties, vb.: bij routeplanner dat je met de fiets
gaat DUS een correcte uitkomst kan enkel bekomen worden wanneer deze assumpties
correct zijn
Toegepast voorbeeld
We willen een DNA-sequentie laten transleren door een algoritme PROBLEEM: levert 6
theoretisch mogelijke AZ sequenties op WANT weten niet waar de translatie start en of we de
sequentie v/d leading of de lagging strand hebben
Pairwise sequence alignment algorithm
Voorloper op wat we in het volgend hoofdstuk gaan zien
Resultaten vergelijken resultaten zo plaatsen dat ze zoveel mogelijk
gelijkenissen in dezelfde kolom hebben
1
,1.3 Principles of classification
Veel problemen die we willen oplossen in de bio-informatica zijn klassificatie problemen
willen een correct label geven gebruiken de ‘confusion matrix’ als
representatie
Confusion matrix
Kunnen hiermee ook verschillende dingen berekenen:
Accuraatheid: beschrijft welke fractie van alle classificaties resulteerde in een correct
toegewezen label
Gevoeligheid: beschrijft welke fractie van de positieve gevallen als zodanig werd
geïdentificeerd
Specificiteit: beschrijft welke fractie van alle negatieve gevallen
als zodanig is geïdentificeerd
Computers maken soms fouten we onderscheiden 2 grote fouten:
Vals positief = type I fout
Vals negatief = type II fout
Voor elke toepassing kan je uitmaken welke fout het ergste is, vb.: liever minder vals
negatieve bij diagnostiek dan vals positieve
! EXAMEN: wordt vaak gevraagd om manueel uit te rekenen
ROC analysis
Gaan algoritmes zo optimaliseren dat de fout dat we willen vermijden afneemt MAAR dan zal
de andere fout stijgen spelen met een drempelwaarde tussen de 2 fouten door met
gevoeligheid en specificiteit te spelen plotten in ‘receiver operating characteristic’
! EXAMEN: geen vraag over
1.4 Graph theory
Gaat over het omgaan met graphen
Graph = mathematische structuur, netwerk dat bestaat uit
knooppunten (nodes) en de relaties in het netwerk (edges)
Graph representatie kan ook omgezet worden in een adjacency matrix of in een adjacency list
Enkele begrippen
2
,Path = combinatie aan edges
Cycle = pad dat terug uitkomt bij zijn beginpunt
Clique = stukje v/d graph waarin alles zeer sterk met elkaar verbonden is
Node degree = hoeveel edges een node met zich geconnecteerd heeft
Verschillende soorten graphen
Undirected = edges hebben geen richting
Directed = gerichte graph, beide richtingen v/e edge kunnen een
andere betekenis hebben
Mixed = combinatie v/d twee
Paden
Vaak meer dan 1 pad om 2 nodes met elkaar te verbinden zoeken naar het korste pad
Algoritmes ontwikkeld om het korste pad te berekenen
o Dijkstra’s algoritme: berekent het korste pad voor een nodenpaar
o Floyd-Warshall algorithm: berekent de kortste paden tussen alle nodenparen
! Als we de afstand tussen 2 noden willen definiëren nemen we ALTIJD het kortste pad
1.5 Computational complexity
Sommige problemen zijn ook voor computers moeilijk op te lossen met enkel ‘brute kracht’ (=
alle mogelijke oplossingen berekenen), vb.: ‘the travelling salesman problem’
De efficiëntie v/e algoritme wordt bepaald a.d.h.v. de duur van de berekeningen
(tijdscomplexiteit) of het geheugen dat het algoritme aankan
voor de input (ruimtecomplexiteit)
Big-O notation = beschrijven hoe het algoritme verandert
wanneer de omvang groter wordt
Kunnen de Big-O notation van verschillende algoritmes
makkelijk met elkaar vergelijken
Voorbeeld: the travelling salesman problem
Complexity classes
Problemen worden ingedeeld o.b.v. hun complexiteit:
P problems: kunnen worden opgelost in een polynomiale tijd
NP problems: er is geen efficiënte manier om het probleem op te lossen MAAR een
kandidaat oplossing kan wel worden nagekenen in polynomiale tijd
NP complete problems: het moeilijkste type NP problems
NP hard problems: niet enkel NP en moeilijker dan de NP complete problems
3
, Veel problemen zijn te lastig om op te lossen OPLOSSING: i.p.v. ‘de perfecte’ oplossing te
zoeken, zoeken we gewoon naar een ‘goede’ oplossing we onderscheiden dus 2 methodes:
1. Exhaustive: systematisch alle kandidaten
‘checken’, brute kracht
2. Heuristic: gericht specifieke kandidaten ‘checken’
MAAR kan zijn dat de bekomen oplossing niet
de beste oplossing is die er bestaat
Zoekprobleem
Veel problemen bestaan eruit om de beste oplossing te zoeken in een groot aanbod van
mogelijke oplossingen = zoekprobleem
Zoekalgoritme
Hebben een probleem als input en geven een oplossing terug die de
beste waarde van objectieve functie (= functie die de kwaliteit v/d
kandidaatoplossing aangeeft) heeft
Voorbeeld: woord zoeken in tekst
Brute kracht: alle woorden scannen
Heuristics: index gebruiken
Voorbeeld: zoeken de x-waarde waarvoor de y-waarde maximaal is kunnen alle waarden
van x afscannen (brute kracht) kunnen ook naar de pieken gaan kijken MAAR hebben dan
mss niet de hoogste piek: noemen dit een lokaal optimum globaal optimum is voor de hele
zoekruimte de hoogste
Kan zich ook voordoen in meerdere dimensies veel complexer
Optimalisatiemethoden
We gebruiken optimalisatie methoden i.p.v. brute kracht
Bij optimalisatiemethoden maken we gebruik van iterative improvement beginnen v/e
oplossing die niet optimaal is en gaan deze stapje per stapje beter maken tot we een betere
oplossing krijgen
Voorbeelden van optimatlisatie methodes:
- Hill climbing
- Simulated annealing
- Evolutionary / genetic algorrithms
Hill climbing
Het begint met een willekeurige oplossing voor een probleem, om vervolgens een betere
oplossing te vinden door een stapsgewijze verandering aan te brengen in de oplossing als
de verandering een betere oplossing oplevert, wordt er een nieuwe verandering in de nieuwe
oplossing aangebracht en zo verder tot er geen verbetering meer mogelijk is
Voorbeeld: berg beklimmen willen de hoogste coördinaat vinden paracommando uit
vliegtuig: vertrekt vanuit 1 punt en zet elke keer een stap in een random richting, als deze
hoger is dan blijft die staan en gaat die vandaar verder maar als het lager of hetzelfde gaat
die terug naar zijn beginpunt
4
H1 Computer science background
1.1 Databases
Er zijn verschillende manieren om data te bewaren:
Papier
Flat files
o Geen structuur
o Geen metadata geen uitleg wat wat is, geen uniform systeem
Vb.: excel document, word document etc.
Databases 2 soorten:
1. Relationele
2. NoSQL
Relational databases
Gegevens opgeslagen in een reeks tabellen die met elkaar verbonden zijn door een
gedefinieerde logica kunnen hier gerichte vragen aan stellen
NoSQL databases
Alles wat niet efficiënt in een gewone databank past, kan hierin
1.2 Algorithms
Algoritme = set aan regels om mee te rekenen, meestal uitgevoerd door een computer
programma MAAR is niet noodzakelijk
Voorbeelden zonder computer: staartdeling, routeplanner
VROEGER: traditionele algoritmes werden geproduceerd door een software engineer
NU: algoritmes die geoptimaliseerd worden a.d.h.v. voorbeelden self-learning of
machine learning (AI)
! LET OP: algoritmes komen met bepaalde assumpties, vb.: bij routeplanner dat je met de fiets
gaat DUS een correcte uitkomst kan enkel bekomen worden wanneer deze assumpties
correct zijn
Toegepast voorbeeld
We willen een DNA-sequentie laten transleren door een algoritme PROBLEEM: levert 6
theoretisch mogelijke AZ sequenties op WANT weten niet waar de translatie start en of we de
sequentie v/d leading of de lagging strand hebben
Pairwise sequence alignment algorithm
Voorloper op wat we in het volgend hoofdstuk gaan zien
Resultaten vergelijken resultaten zo plaatsen dat ze zoveel mogelijk
gelijkenissen in dezelfde kolom hebben
1
,1.3 Principles of classification
Veel problemen die we willen oplossen in de bio-informatica zijn klassificatie problemen
willen een correct label geven gebruiken de ‘confusion matrix’ als
representatie
Confusion matrix
Kunnen hiermee ook verschillende dingen berekenen:
Accuraatheid: beschrijft welke fractie van alle classificaties resulteerde in een correct
toegewezen label
Gevoeligheid: beschrijft welke fractie van de positieve gevallen als zodanig werd
geïdentificeerd
Specificiteit: beschrijft welke fractie van alle negatieve gevallen
als zodanig is geïdentificeerd
Computers maken soms fouten we onderscheiden 2 grote fouten:
Vals positief = type I fout
Vals negatief = type II fout
Voor elke toepassing kan je uitmaken welke fout het ergste is, vb.: liever minder vals
negatieve bij diagnostiek dan vals positieve
! EXAMEN: wordt vaak gevraagd om manueel uit te rekenen
ROC analysis
Gaan algoritmes zo optimaliseren dat de fout dat we willen vermijden afneemt MAAR dan zal
de andere fout stijgen spelen met een drempelwaarde tussen de 2 fouten door met
gevoeligheid en specificiteit te spelen plotten in ‘receiver operating characteristic’
! EXAMEN: geen vraag over
1.4 Graph theory
Gaat over het omgaan met graphen
Graph = mathematische structuur, netwerk dat bestaat uit
knooppunten (nodes) en de relaties in het netwerk (edges)
Graph representatie kan ook omgezet worden in een adjacency matrix of in een adjacency list
Enkele begrippen
2
,Path = combinatie aan edges
Cycle = pad dat terug uitkomt bij zijn beginpunt
Clique = stukje v/d graph waarin alles zeer sterk met elkaar verbonden is
Node degree = hoeveel edges een node met zich geconnecteerd heeft
Verschillende soorten graphen
Undirected = edges hebben geen richting
Directed = gerichte graph, beide richtingen v/e edge kunnen een
andere betekenis hebben
Mixed = combinatie v/d twee
Paden
Vaak meer dan 1 pad om 2 nodes met elkaar te verbinden zoeken naar het korste pad
Algoritmes ontwikkeld om het korste pad te berekenen
o Dijkstra’s algoritme: berekent het korste pad voor een nodenpaar
o Floyd-Warshall algorithm: berekent de kortste paden tussen alle nodenparen
! Als we de afstand tussen 2 noden willen definiëren nemen we ALTIJD het kortste pad
1.5 Computational complexity
Sommige problemen zijn ook voor computers moeilijk op te lossen met enkel ‘brute kracht’ (=
alle mogelijke oplossingen berekenen), vb.: ‘the travelling salesman problem’
De efficiëntie v/e algoritme wordt bepaald a.d.h.v. de duur van de berekeningen
(tijdscomplexiteit) of het geheugen dat het algoritme aankan
voor de input (ruimtecomplexiteit)
Big-O notation = beschrijven hoe het algoritme verandert
wanneer de omvang groter wordt
Kunnen de Big-O notation van verschillende algoritmes
makkelijk met elkaar vergelijken
Voorbeeld: the travelling salesman problem
Complexity classes
Problemen worden ingedeeld o.b.v. hun complexiteit:
P problems: kunnen worden opgelost in een polynomiale tijd
NP problems: er is geen efficiënte manier om het probleem op te lossen MAAR een
kandidaat oplossing kan wel worden nagekenen in polynomiale tijd
NP complete problems: het moeilijkste type NP problems
NP hard problems: niet enkel NP en moeilijker dan de NP complete problems
3
, Veel problemen zijn te lastig om op te lossen OPLOSSING: i.p.v. ‘de perfecte’ oplossing te
zoeken, zoeken we gewoon naar een ‘goede’ oplossing we onderscheiden dus 2 methodes:
1. Exhaustive: systematisch alle kandidaten
‘checken’, brute kracht
2. Heuristic: gericht specifieke kandidaten ‘checken’
MAAR kan zijn dat de bekomen oplossing niet
de beste oplossing is die er bestaat
Zoekprobleem
Veel problemen bestaan eruit om de beste oplossing te zoeken in een groot aanbod van
mogelijke oplossingen = zoekprobleem
Zoekalgoritme
Hebben een probleem als input en geven een oplossing terug die de
beste waarde van objectieve functie (= functie die de kwaliteit v/d
kandidaatoplossing aangeeft) heeft
Voorbeeld: woord zoeken in tekst
Brute kracht: alle woorden scannen
Heuristics: index gebruiken
Voorbeeld: zoeken de x-waarde waarvoor de y-waarde maximaal is kunnen alle waarden
van x afscannen (brute kracht) kunnen ook naar de pieken gaan kijken MAAR hebben dan
mss niet de hoogste piek: noemen dit een lokaal optimum globaal optimum is voor de hele
zoekruimte de hoogste
Kan zich ook voordoen in meerdere dimensies veel complexer
Optimalisatiemethoden
We gebruiken optimalisatie methoden i.p.v. brute kracht
Bij optimalisatiemethoden maken we gebruik van iterative improvement beginnen v/e
oplossing die niet optimaal is en gaan deze stapje per stapje beter maken tot we een betere
oplossing krijgen
Voorbeelden van optimatlisatie methodes:
- Hill climbing
- Simulated annealing
- Evolutionary / genetic algorrithms
Hill climbing
Het begint met een willekeurige oplossing voor een probleem, om vervolgens een betere
oplossing te vinden door een stapsgewijze verandering aan te brengen in de oplossing als
de verandering een betere oplossing oplevert, wordt er een nieuwe verandering in de nieuwe
oplossing aangebracht en zo verder tot er geen verbetering meer mogelijk is
Voorbeeld: berg beklimmen willen de hoogste coördinaat vinden paracommando uit
vliegtuig: vertrekt vanuit 1 punt en zet elke keer een stap in een random richting, als deze
hoger is dan blijft die staan en gaat die vandaar verder maar als het lager of hetzelfde gaat
die terug naar zijn beginpunt
4
