Emne - Algoritmer for bioinformatikk - TDT4287
TDT4287 - Algoritmer for bioinformatikk
Om emnet
Vurderingsordning
Vurderingsordning: Hjemmeeksamen
Karakter: Bestått/Ikke bestått
Vurderingsform | Vekting | Varighet | Hjelpemidler | Delkarakter |
---|---|---|---|---|
Hjemmeeksamen | 100/100 | 4 timer |
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
Vurderingsmelding krever godkjent undervisningsmelding samme semester. Obligatorisk aktivitet fra tidligere semester kan godkjennes av instituttet.
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.)
Versjon: 1
Studiepoeng:
7.5 SP
Studienivå: Høyere grads nivå
Termin nr.: 1
Undervises: HØST 2020
Forelesningstimer: 2
Øvingstimer: 3
Fordypningstimer: 7
Undervisningsspråk: Engelsk
Sted: Trondheim
- Algoritmekonstruksjon
- Bioinformatikk
Ansvarlig enhet
Institutt for datateknologi og informatikk
Telefon:
Eksamensinfo
Vurderingsordning: Hjemmeeksamen
- Termin Statuskode Vurderings-form Vekting Hjelpemidler Dato Tid Digital eksamen Rom *
-
Høst
ORD
Hjemme-eksamen (1)
100/100
Utlevering 07.12.2020
Innlevering 07.12.2020
Utlevering 09:00
Innlevering 13:00
INSPERA -
Rom Bygning Antall kandidater
- * Skriftlig eksamen plasseres på rom 3 dager før eksamensdato. Hvis mer enn ett rom er oppgitt, finner du ditt rom på Studentweb.
- 1) Merk at eksamensform er endret som et smittevernstiltak i den pågående koronasituasjonen. Please note that the exam form has changed as a preventive measure in the ongoing corona situation.
For mer info om oppmelding til og gjennomføring av eksamen, se "Innsida - Eksamen"