Forelæsere: Niels
Richard Hansen og Ernst Hansen
Deltagere:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stikord:
Markovkæder, skjulte markovkæder, EM-algoritmen, optimerings-algoritmer,
ML-estimation, dynamisk programmering, scoringsfunktioner, asymptotik.
Anvendelser af ovenstående indenfor biologisk sekvensanalyse.
Forelæsninger og øvelser:
4 timer om ugen med øvelsesgennemgang 1 time hver anden uge.
Mandag kl. 14-16 og onsdag kl. 13-15 i Aud. 9.
Indhold:
Introduktion til biologiske sekvensdata.
| Der sekventeres idag store mængde DNA, RNA og proteiner indenfor biologien, biokemien, medicinalforskningen o.lign., og sammenligning af nye sekvenser med kendte spiller en vigtig rolle i forskningen. I stor udstrækning benyttes databasesøgning efter f.eks. gener, der ligner et netop sekventeret gen, og problemet er i høj grad at kvantificere begreber som "ligner". I dette kursus gennemgås de mest almindelige metoder til sammenligning af sekvenser (ved såkaldt linieopstilling), hvor man benytter additive scorefunktioner og dynamisk programmering til at finde den optimale linieopstilling af to sekvenser. Multipel linieopstilling, hvor flere end to sekvenser sammenlignes, og lokal linieopstilling berøres også. |
| En del af kurset vil gå med at behandle fordelingsresultater for scorefunktionen under en simpel stokastisk model, hvor "bogstaverne" i sekvensen antages uafhængige og identisk fordelte (iid). Dette giver en referencemodel, som vi kan holde resultater op imod, for at finde ud af hvornår en given sammenligning af to sekvenser er signifikant "bedre", end hvad man kan forvente ved en tilfældighed. |
| Dernæst behandles forekomsten af mønstre i tilfældige (iid og markov) sekvenser, og den centrale grænseværdisætning for markovkæder på tællelige tilstandsrum vil blive vist i den forbindelse. |
Kategoriske tidsrækker.
| Efter en del analyse af iid-modeller, som i forbindelse med biologiske sekvensdata primært tjener som referencemodeller, vil en klasse af modeller kaldet skjulte markovkæder eller skjulte markovmodeller blive indtroduceret. I den forbindelse gennemgås også begreberne betinget uafhængighed og grafisk repræsentation af afhængighed mellem stokastiske variable. |
| Skjulte markovmodeller er en omfattende klasse af modeller, der kan benyttes til modellering af mange andre typer kategoriske tidsrækker end de biologiske, dvs. datasekvenser fra en endelig strukturløs mængde, hvor der evt. er afhængighed mellem de enkelte observationer. |
| Statistisk inferens for skjulte markovmodeller behandles grundigt i kurset, hvor der bl.a. vil der blive brugt tid på den algoritmiske side omkring beregning af likelihood- funktionen, EM-algoritmen (ofte kaldet Baum-Welch algoritmen for skjulte markovmodeller) til beregning af maksimum-likelihood estimater og Viterbi algoritmen. Anvendelser af denne type modeller og metoder indenfor den biologiske sekvensanalyse vil blive behandlet. |
| EM-algoritmen er blot en metode til numerisk at finde maksimum-likelihood estimater, og såfremt tiden tillader det, vil kurset blive afsluttet med en gennemgang af andre metoder til numerisk optimering med særligt fokus på maksimum-likelihood estimation for skjulte markovmodeller. |
| Litteratur
M. S. Waterman; Introduction to Computational Biology. Maps, sequences and genomes. (Primær lærebog). R. Durbin, S. Eddy, A. Krogh, G. Mitchinson;
Primer on Molecular Genetics (PDF) (lidt gammel, men ok) Dynamisk programmering: Notat1 (27. september, side 1-8, væsentlige indeksfejl rettet) Abstrakt konstruktion af metrikker og similaritetsmål: Notat2 (27.september, side 1-5) Asymptotik for similaritetsscore og den subadditive ergodesætning: Notat3 (27.september, side 1-7) Notat5 (2. november, side 1-6) Notat6 (19. november, side 1-10, enkelte trykfejl rettet) Large deviation teori: Notat4 (10. oktober, side 1-9. Ny sætning med bevis for påstande i 2.4 inkluderet! Endvidere er den korrekte betingelse for Sanovs sætning indføjet) Markovkæder og den centrale grænseværdisætning: Notat7 (29. november, side 1-16.) Fornyelsesteori baseret på markovkæder: Notat8 (12. december, side 1-4.) Skjulte markovmodeller: Notat9 (12.december, side 1-10. Supplerende håndskrevne notater udleveret.) |
| Forudsætninger:
Statistik 1 og en interesse for beregningsproblematik, algoritmer og biologiske problemstillinger. Er man overbygningsstuderende på matematik, datalogi eller lign., har interesse for emnet, og har man haft 2SS, er man også velkommen, da store dele af kurset ikke kræver mere. |
| Eksamen/punktprøve:
En obligatorisk rapportopgave med teoretiske og praktiske spørgsmål + en mindre teoretisk punktprøve. |
| Belastning:
4 punkter/10 ECTS |