Algoritmi za optimizacijo rabe kodonovMramor, Anže (Avtor) Žitnik, Arjana (Mentor) kodoniproteinitranslacijski časdinamično programiranjenormečasovna zahtevnostDelo diplomskega seminarja se ukvarja z matematično rešitvijo biokemijskega problema – želimo sestaviti algoritem, ki bo v realnem času poiskal optimalno zaporedje kodonov proteina za izražanje v celicah E. coli. Natančneje, za eksperimentalno dobljene podatke sinteze proteina želimo določiti takšno zaporedje kodonov, da bi vrednosti časov translacije posamezne aminokisline, ki jih izračunamo po formuli lokalnega povprečja treh zaporednih kodonov, od njih odstopale čim manj. Problem rešujemo z dinamičnim programiranjem. Najprej izpeljemo rekurzivno formulo, ki nam bo rešila optimizacijski problem. Nato rekurzivno formulo razširimo v splošen računalniški algoritem, ki ga tudi implementiramo v programskem jeziku Python. Najprej preverimo delovanje algoritma na podatkih treh obstoječih proteinov. Zaporedje želenih časov translacije dobimo iz dejanskih proteinov – na tak način zagotovimo, da se začetni aproksimirani podatki ujemajo z rezultati algoritma, ter tako preverjamo uspešnost algoritma. Algoritem se na takšni vrsti podatkov izkaže za delujoč v vseh treh primerih, zato bazo testiranih podatkov razširimo na 900 naključno generiranih proteinov. Tudi tu algoritem za vsak protein s 100 % uspešnostjo najde ustrezno zaporedje kodonov. Poleg tega preverjamo še časovno zahtevnost algoritma, ki se izkaže za linearno. V zadnjem delu naloge spremenimo podatke s šumom (s šumi velikosti 1 %, 5 % in 10 %), tako da so želeni časi drugačni od podanih translacijskih časov za translacijo kodonov. Ponovno preverimo uspešnost algoritma, ki je z večanjem šuma vedno manjša. Izkaže se, da ima ključno vlogo pri uspešnosti algoritma izbira norme znotraj rekurzivne formule. Preizkušamo prvo, drugo in neskončno normo, pri čemer se druga izkaže za najbolj uspešno, prva in neskončna pa sta v deležu uspešno določenih kodonov identični.20212021-09-12 08:15:38Delo diplomskega seminarja/zaključno seminarsko delo/naloga130278UDK: 519.8VisID: 119867COBISS_ID: 76299011sl