course-details-portlet

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.

Kursmateriell

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

Flere sider om emnet

Fakta om emnet

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

Undervisning

Termin nr.: 1
Undervises:  HØST 2020

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:

Timeplan

Listevisning
Kalendervisning

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

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

Mer om eksamen ved NTNU