course-details-portlet

TDT4287 - Algoritmer for bioinformatikk

Om emnet

Vurderingsordning

Vurderingsordning: Skriftlig eksamen
Karakter: Bokstavkarakterer

Vurderingsform Vekting Varighet Hjelpemidler Delkarakter
Skriftlig eksamen 100/100 4 timer D

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.

Kursmateriell

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

Fakta om emnet

Versjon: 1
Studiepoeng:  7.5 SP
Studienivå: Høyere grads nivå

Undervisning

Termin nr.: 1
Undervises:  HØST 2019

Forelesningstimer: 2
Øvingstimer: 3
Fordypningstimer: 7

Undervisningsspråk: Engelsk

Sted: Trondheim

Fagområde(r)
  • Algoritmekonstruksjon
  • Bioinformatikk
Kontaktinformasjon
Emneansvarlig/koordinator: Faglærer(e):

Ansvarlig enhet
Institutt for datateknologi og informatikk

Telefon:

Eksamensinfo

Vurderingsordning: Skriftlig eksamen

Termin Statuskode Vurderings-form Vekting Hjelpemidler Dato Tid Digital eksamen Rom *
Høst ORD Skriftlig eksamen 100/100 D 02.12.2019 15:00
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.
Eksamensinfo

For mer info om oppmelding til og gjennomføring av eksamen, se "Innsida - Eksamen"

Mer om eksamen ved NTNU