20.500.12556/RUL-121379 Algoritmi za matematično podporo sintezne biologije magistrsko delo Algorithms for mathematical support of synthetic biology Vpraš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. One of the tasks of synthetic biology is determining possible results of selfassembed polypeptide chains. Every link of a polypeptide chain has a partner with which they bond. Such bonded pairs bend the chain into a prescribed shape. For selfassembly of one chain into a structure, represented by a graph G, we define a special kind of double circuit of graph G that we call a strong circuit. We show that there is an equivalence between strong circuits of graph G, 1-face embeddings of a graph G on a surface, and possiblities for the polypeptide chain to form the given structure. We also show that every graph has a 1-face embedding, therefore there exists a polypeptide chain from which it can be contstructed. We model the selfassembly of multiple chains with covering graphs. We determine the smallest structure created by a given set of chains, which we call a base pregraph. Than we prove that given certain restrictions, there is an equivalence between possible constructions and wrapped quasi-covering graphs over the base pregraph. We present an algorithm that finds all non-equivalent ways for a graph to be selfassembed from one chain. We also present an algorithm that finds every non-isomorphic wrapped quasi-covering graphs for a given pregraph. We show results for certain examples. Eulerjev cikel dvojni obhod vložitev grafa v ploskev predgraf krovni graf z razvejišči algoritem na grafih sintezna biologija samosestava polipeptidnih verig Eulerian cycle double circuit graph embedding pregraph covering graph graph algorithm synthetic biology polypeptide chain selfassembly true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2020-10-07 08:15:01 2020-10-07 08:15:05 2024-05-29 14:29:57 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 113317 32755203 1343.pdf 1343.pdf 1 BB754865D8ED59EF99C1D4BF7356CAD8 909306ebca622fd922579cafe04b8d1d2f4ba6222ea5920096752a4d67c4964d dfc2fce4-a1ba-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=136297 Fakulteta za matematiko in fiziko 0 0 0