BIO-INFORMATICA
INTRODUCTIE
RNA & PROTEÏNEN
• Interacties: moleculen interageren met en beïnvloeden elkaar
• Variatie: groot aantal genen, nog meer variatie in RNA en proteïnen
• Spatiotemporale dynamiek: de hoeveelheid van elke molecule verschilt in tijd en ruimte
BIO INFORMATICA
= onderzoek, ontwikkeling of toepassing van computationele “tools” en toepassingen om het gebruik
van biologische, medische, gedraaglijke of gezondheids data uit te breiden met degenen die deze
informatie verzamelen, opslaan, organiseren, analyseren, …
→ Verwerken en analyseren van moleculaire biologische data (gedreven door een vraag)
• Computationele biologie: ontwikkeling en toepassing van data-analytische en theoretische
methoden, mathematische modellering en computationele simulatietechnieken om biologie,
gedrag en sociale systemen te bestuderen.
• Data mining (gedreven door data): patroon extractie en ontdekking van kennis in grote datasets.
HOOFDSTUK 1: ACHTERGROND VAN COMPUTER WETENSCHAP
DATABASES
DATA ORGANISATIE
1. Papier
2. Flat files:
- Collectie van datarapporten
- Geen structuur
- Geen metadata (= informatie over hoe alles bewaard is en wat het is)
3. Databasen:
- Relationele databasen: tabellen, rijen, kolommen, …
Bv. MySQL, SQLite, Oracle
- NoSQL databasen: gemaakt om data te behandelen en op te slaan die niet in het
traditionele database model passen.
ALGORTIMES
1
,= proces of set van regels die gevolgd moet worden bij berekeningen of andere probleem-oplossende
operaties. Vaak maar niet altijd uitgevoerd door een computerprogramma.
= stappenplan om een gegeven probleem op te lossen.
Traditionele algoritmes: procedure geprogrammeerd door een software ingenieur.
! Belangrijk: algoritmes komen vaak met bepaalde assumpties, een correcte uitkomst is enkel
beloofd als deze assumpties kloppen.
VOORBEELD
Een DNA sequentie wordt gegeven en alle 6 mogelijke proteïnesequenties die door translatie
bekomen kunnen worden → translate_sequence voor elke positie
Pairwise sequence aligment algorithm: opstellen zodat de meeste zaken overeenkomen
PRINCIPES VAN CLASSIFICATIE
= op basis van bepaalde eigenschappen van een object een correct label toekennen.
CONFUSION MATRIX
= we gebruiken al voorwerpen waarvan we weten wat het is zodat het programma dit als leidraad
kan gebruiken
• Vals negatief (type II fout): het wordt niet aangerekend tot een categorie waar het eigenlijk wel
bij hoort → ergste fout.
• Vals positief (type I fout): het wordt aangerekend tot een categorie waar het niet bij hoort.
• Accuraatheid: welke fractie is correct van alle voorspellingen
• Gevoeligheid:
• Specificiteit: hoe specifiek het is
GRAAF THEORIE
2
,= studie van grafen
• Graaf: een netwerk representatie of relaties tussen elementen (nodes) van een bepaalde groep.
SIMPELE UNDIRECTED GRAPH
ADJACENCY MATRIX
= matrix die weergeeft welken noden tegen elkaar liggen
DEFINITIES
• Pad: verbindt verschillende noden met elkaar
• Cyclus: pad dat ergens vertrekt en weer uitkomt bij het begin punt
• Clique: stukje van de graaf waarin alles zeer sterk is verbonden met elkaar
• Node degree: aantal randen geconnecteerd aan één node
• Kortste pad: pad dat via zo weinig mogelijk stappen 2 noden met elkaar verbindt
- Computationally nontrivial: alle mogelijke paden tussen een paar noden zoeken.
- Extrapolatie naar alle noden paren: challenge
3
, - Dijkstra’s algoritme: zoekt het kortste pad voor een gegeven node pair
- Floyd-Warshall algoritme: zoekt de grootste afstands matrix
COMPUTATIONELE COMPLEXITEIT
TRAVELLING SALES MAN
• Brute force algoritme: alle mogelijke opties testen → wordt onmogelijk na een bepaald aantal
• Efficiëntie: wordt gemeten door de “worst-case” running time, de langste tijd dat een algoritme
nodig heeft voor de meest moeilijke input
• Big O-notation: notatie die de algoritmische complexiteit beschrijft
- Probleem grootte (n) dan O(n) als de tijd lineair toeneemt met n.
- Tijd proportioneel met kwadraat van n: O(n^2)
COMPLEXITEIT
• P problemen: kan opgelost worden in polynomale tijd
• NP problemen: geen efficiënte weg om een probleem op te lossen maar een kandidaat oplossing
kan gevonden worden in polynomische tijd.
• NP complete problemen: moeilijkste type problemen
• NP hard problemen: erger dan NP complete problemen, als je dit kan oplossen kan je alle NP
problemen oplossen.
SEARCH ALGORITMES
= nemen een probleem als input en zorgen voor een oplossing, vaak na het evalueren van een
bepaald aantal kandidaatoplossingen.
• Search space: set van alle mogelijke oplossing voor een probleem
• Objectieve functie: functie die de waarde terugbrengt en de kwaliteit van een
kandidaatoplossing weergeeft
HILL CLIMBING
• Beweegt steeds naar boven toe waardoor de waarde van de objectieve functie toeneemt
4
INTRODUCTIE
RNA & PROTEÏNEN
• Interacties: moleculen interageren met en beïnvloeden elkaar
• Variatie: groot aantal genen, nog meer variatie in RNA en proteïnen
• Spatiotemporale dynamiek: de hoeveelheid van elke molecule verschilt in tijd en ruimte
BIO INFORMATICA
= onderzoek, ontwikkeling of toepassing van computationele “tools” en toepassingen om het gebruik
van biologische, medische, gedraaglijke of gezondheids data uit te breiden met degenen die deze
informatie verzamelen, opslaan, organiseren, analyseren, …
→ Verwerken en analyseren van moleculaire biologische data (gedreven door een vraag)
• Computationele biologie: ontwikkeling en toepassing van data-analytische en theoretische
methoden, mathematische modellering en computationele simulatietechnieken om biologie,
gedrag en sociale systemen te bestuderen.
• Data mining (gedreven door data): patroon extractie en ontdekking van kennis in grote datasets.
HOOFDSTUK 1: ACHTERGROND VAN COMPUTER WETENSCHAP
DATABASES
DATA ORGANISATIE
1. Papier
2. Flat files:
- Collectie van datarapporten
- Geen structuur
- Geen metadata (= informatie over hoe alles bewaard is en wat het is)
3. Databasen:
- Relationele databasen: tabellen, rijen, kolommen, …
Bv. MySQL, SQLite, Oracle
- NoSQL databasen: gemaakt om data te behandelen en op te slaan die niet in het
traditionele database model passen.
ALGORTIMES
1
,= proces of set van regels die gevolgd moet worden bij berekeningen of andere probleem-oplossende
operaties. Vaak maar niet altijd uitgevoerd door een computerprogramma.
= stappenplan om een gegeven probleem op te lossen.
Traditionele algoritmes: procedure geprogrammeerd door een software ingenieur.
! Belangrijk: algoritmes komen vaak met bepaalde assumpties, een correcte uitkomst is enkel
beloofd als deze assumpties kloppen.
VOORBEELD
Een DNA sequentie wordt gegeven en alle 6 mogelijke proteïnesequenties die door translatie
bekomen kunnen worden → translate_sequence voor elke positie
Pairwise sequence aligment algorithm: opstellen zodat de meeste zaken overeenkomen
PRINCIPES VAN CLASSIFICATIE
= op basis van bepaalde eigenschappen van een object een correct label toekennen.
CONFUSION MATRIX
= we gebruiken al voorwerpen waarvan we weten wat het is zodat het programma dit als leidraad
kan gebruiken
• Vals negatief (type II fout): het wordt niet aangerekend tot een categorie waar het eigenlijk wel
bij hoort → ergste fout.
• Vals positief (type I fout): het wordt aangerekend tot een categorie waar het niet bij hoort.
• Accuraatheid: welke fractie is correct van alle voorspellingen
• Gevoeligheid:
• Specificiteit: hoe specifiek het is
GRAAF THEORIE
2
,= studie van grafen
• Graaf: een netwerk representatie of relaties tussen elementen (nodes) van een bepaalde groep.
SIMPELE UNDIRECTED GRAPH
ADJACENCY MATRIX
= matrix die weergeeft welken noden tegen elkaar liggen
DEFINITIES
• Pad: verbindt verschillende noden met elkaar
• Cyclus: pad dat ergens vertrekt en weer uitkomt bij het begin punt
• Clique: stukje van de graaf waarin alles zeer sterk is verbonden met elkaar
• Node degree: aantal randen geconnecteerd aan één node
• Kortste pad: pad dat via zo weinig mogelijk stappen 2 noden met elkaar verbindt
- Computationally nontrivial: alle mogelijke paden tussen een paar noden zoeken.
- Extrapolatie naar alle noden paren: challenge
3
, - Dijkstra’s algoritme: zoekt het kortste pad voor een gegeven node pair
- Floyd-Warshall algoritme: zoekt de grootste afstands matrix
COMPUTATIONELE COMPLEXITEIT
TRAVELLING SALES MAN
• Brute force algoritme: alle mogelijke opties testen → wordt onmogelijk na een bepaald aantal
• Efficiëntie: wordt gemeten door de “worst-case” running time, de langste tijd dat een algoritme
nodig heeft voor de meest moeilijke input
• Big O-notation: notatie die de algoritmische complexiteit beschrijft
- Probleem grootte (n) dan O(n) als de tijd lineair toeneemt met n.
- Tijd proportioneel met kwadraat van n: O(n^2)
COMPLEXITEIT
• P problemen: kan opgelost worden in polynomale tijd
• NP problemen: geen efficiënte weg om een probleem op te lossen maar een kandidaat oplossing
kan gevonden worden in polynomische tijd.
• NP complete problemen: moeilijkste type problemen
• NP hard problemen: erger dan NP complete problemen, als je dit kan oplossen kan je alle NP
problemen oplossen.
SEARCH ALGORITMES
= nemen een probleem als input en zorgen voor een oplossing, vaak na het evalueren van een
bepaald aantal kandidaatoplossingen.
• Search space: set van alle mogelijke oplossing voor een probleem
• Objectieve functie: functie die de waarde terugbrengt en de kwaliteit van een
kandidaatoplossing weergeeft
HILL CLIMBING
• Beweegt steeds naar boven toe waardoor de waarde van de objectieve functie toeneemt
4
