Algoritmi za matematično podporo sintezne biologijeHajšen, Matic Oskar (Avtor) Pisanski, Tomaž (Mentor) Eulerjev cikeldvojni obhodvložitev grafa v ploskevpredgrafkrovni graf z razvejiščialgoritem na grafihsintezna biologijasamosestava polipeptidnih verigVprašanje v sintezni biologiji je, na koliko načninov se lahko v pare, ki jim pravimo dimeri, lepijo členi polipeptidnih verig tako, da ima zlepljena veriga predpisano obliko. Za primer samosestave ene verige v strukturo, opisano z grafom G, defniramo posebno vrsto dvojnega obhoda po grafu G, ki ji pravimo krepek obhod. Izkaže se, da velja ekvivalenca med krepkimi obhodi, vložitvami grafa G v ploskev, ki imajo eno lice, in možnimi verigami, ki se samosetavijo v željeno strukturo. Pokažemo, da ima vsak graf G 1-lično vložitev, torej obstaja veriga iz katere ga lahko sestavimo. Če ustvarjamo nanostrukturo iz več verig, kot model zanjo uporabljamo krovni graf z razvejišči. Pokažemo, kakšna je najmanjša struktura, ki jo lahko naredimo z izbranimi polipeptidnimi verigami, čemur pravimo bazni predgraf. Potem dokažemo, da z nekaterimi omejitvami velja ekvivalenca med izvedljivimi strukturami in krovnimi grafi z razvejišči nad baznim predgrafom. Predstavljen je algoritem, ki poišče vse neekvivalentne načine samosestave grafa iz ene verige. Pokažemo tudi algoritem, ki izračuna vse neizomorfne krovne grafe z razvejišči. Prikazani so še rezultati za nekaj določenih primerov.20202020-10-07 08:15:01Magistrsko delo/naloga121379sl