Faglig innhold

Emnet tar for seg algoritmiske metoder med anvendelser innen bioinformatikk, med et spesielt fokus på algoritmer og datastrukturer for søk, sammenligning og mønsteroppdaging i strenger. Emnet bruker eksempler på biologiske problemstillinger for å motivere algoritmer og løsninger, men emnets fokus er på de algoritmiske problemstillingene.

Læringsutbytte

Kunnskap: - Vet hvordan strengsammenligningsproblem som "longest common subsequence", "edit distance", "local alignment" og "global alignment" kan løses ved dynamisk programmering (DP). - Vet hvordan DP-løsningen for sammenligning av to strenger kan utvides til sammenligning av flere strenger ("multiple alignment"). - Vet hvordan k-mer indekser kan brukes for eksakt og approksimativt strengsøk. - Vet hva et nøkkelordtre er, og hvordan denne indeksstrukturen bygges og brukes for strengsøk. - Vet hva et suffikstre er, hvordan denne indeksstrukturen kan bygges på lineær tid ved hjelp av Ukkonens algoritme, og hvordan suffikstre kan brukes for å løse ulike strengsøk og -sammenligningsproblem. - Vet hvordan mønster i strenger kan finnes med eksakte metoder (ved branch-and-bound) og heuristiske metoder (ved simulated annealing). - Vet sammenhengen mellom sekvenssammenstilling (assembly) og korteste superstreng-problemet og hvorfor Euler-sykel-problemet er et spesialtilfelle av sekvenssammenstilling. - Vet hva hidden Markov-modeller (HMM) er, hvordan disse kan brukes til å modellere og identifisere egenskaper med strenger, og hvordan de sentrale HMM-algoritmene "Viterbi", "forward", og "backward" fungerer. - Vet hva en RNA sekundærstruktur er, hvordan denne relateres til palindrom, og hvordan DP kan brukes til å finne optimale og suboptimale RNA sekundærstrukturer. Ferdigheter: - Implementere kjente algoritmer og datastrukturer og bruke disse på reelle data. - Gjenkjenne varianter av kjente problemstillinger og tilpasse kjente algoritmer til å løse disse. Generell kompetanse: - Vurdere alternativer og velge løsninger som er hensiktsmessige til å løse problemstillinger med reelle data. - Presentere egne løsninger og resultat muntlig og skriftlig.

Læringsformer og aktiviteter

Forelesninger, frivillige øvinger og obligatorisk prosjekt.

Hvis få studenter tar emnet kan forelesningene erstattes med kollokvier.

Obligatoriske aktiviteter

• Øvinger

Anbefalte forkunnskaper

Emne TDT4120 Algoritmer og datastrukturer. Emne TMA4240 Statistikk eller tilsvarende.

Kursmateriell

Jones & Pevzner: An introduction to bioinformatics algorithms (MIT Press, 2004). Artikler og utdelt materiale. (Det tas forbehold om endringer.)