Algoritmi za matematično podporo sintezne biologije : magistrsko delo

Hajšen, Matic Oskar (author), Pisanski, Tomaž (mentor)

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.

• Language: Slovenian
• Keywords: Eulerjev cikel, dvojni obhod, vložitev grafa v ploskev, predgraf, krovni graf z razvejišči, algoritem na grafih, sintezna biologija, samosestava polipeptidnih verig
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2020
• PID: 20.500.12556/RUL-121379
• COBISS.SI-ID: 32755203
• Publication date in RUL: 07.10.2020

Secondary language

• Language: English
• Title: Algorithms for mathematical support of synthetic biology

Abstract

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.

• Keywords: Eulerian cycle, double circuit, graph embedding, pregraph, covering graph, graph algorithm, synthetic biology, polypeptide chain selfassembly