course-details-portlet

TDT4287 - Algoritmer for bioinformatikk

Om emnet

Vurderingsordning

Vurderingsordning: Skriftlig skoleeksamen
Karakter: Bokstavkarakterer

Vurdering Vekting Varighet Delkarakter Hjelpemidler
Skriftlig skoleeksamen 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.

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 2022

Undervisningsspråk: Engelsk

Sted: Trondheim

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

Ansvarlig enhet
Institutt for datateknologi og informatikk

Timeplan

Listevisning
Kalendervisning

Eksamensinfo

Vurderingsordning: Skriftlig skoleeksamen

Termin Statuskode Vurdering Vekting Hjelpemidler Dato Tid Eksamens- system Rom *
Høst ORD Skriftlig skoleeksamen 100/100 D 21.12.2022 09:00 INSPERA
Rom Bygning Antall kandidater
SL120 blå sone Sluppenvegen 14 1
SL415 Sluppenvegen 14 25
Sommer UTS Skriftlig skoleeksamen 100/100 D 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.
Eksamensinfo

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

Mer om eksamen ved NTNU