Uporaba matematičnih modelov in algoritmov pri raziskovanju bioloških zaporedij : magistrsko delo
Rihtaršič, Urška, 1981-
V svojem magistrskem delu bom predstavila uporabo matematičnih modelov in nekaterih algoritmov dinamičnega programiranja pri reševanju problema vzporejanja bioloških, to je proteinskih in DNK ...zaporedij. Naš cilj bo poiskati optimalno poravnavo dveh zaporedij - to pomeni, da zaporedji poravnamo tako, da so homologne baze na istoležnih mestih. Pri tem si bomo pomagali z algebraičnimi statističnimi modeli. Seveda nikoli ne moremo biti popolnoma prepričani, da je poravnava, ki jo dobimo s takim modelom, dejansko pravilna, lahko pa poiščemo poravnavo, ki je optimalna glede na neko objektivno funkcijo. Ta funkcija je določena s točkovalno shemo, s katero pripišemo točke dogodkom delecije, insercije in substitucije v zaporedjih. Izkaže se, da je problem iskanja optimalne poravnave dveh zaporedij pri dani točkovalni shemi ekvivalenten problemu iskanja najkrajše poti v uteženem usmerjenem grafu, ki ga lahko učinkovito rešimo s pomočjo Needleman-Wunschevega algoritma. To je algoritem dinamičnega programiranja, kitemelji na tropski aritmetiki. Lahko pa se vprašamo tudi drugače: Kakšni morajo biti parametri točkovalne sheme, do bo izbrana poravnava glede na to točkovalno shemo optimalna? Tudi tu bomo uporabili algebraične statistične modele. Vsak tak model je podan s polinomsko preslikavo, ki slika iz parametričnega prostora v prostor stanj. Osredotočili se bomo predvsem na parni skriti markovski model za vzporejanje zaporedij. Vsakemu koordinatnemu polinomu te preslikave lahko priredimo Newtonov politop. Izkaže se, da oglišča tega politopa ustrezjo optimalnim poravnavam, vektorji parametrov, za katere je posamezna poravnava optimalna, pa ležijo v normalnem stožcu oglišča,ki določa to poravnavo. Newtonov politop dveh zaporedij izračunamo z algoritmom razširjanja politopov, ki je različica Needleman-Wunschovega algoritma, le da ga izvajamo v algebri politopov.
Type of material - master's thesis
Publication and manufacture - Ljubljana : [U. Rihtaršič], 2010
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
