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

Mer om vurdering

Eksamensoppgave gis kun på engelsk. Studentens besvarelse kan være på norsk eller engelsk.
Ved utsatt eksamen (kontinuasjonseksamen) kan skriftlig eksamen bli endret til muntlig eksamen.

Spesielle vilkår

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.)