Matematično modeliranje problemov iz biologije : doktorska disertacija

slovenski

doktorska dela

2017

$d$-stable trace   $E$-restricted trace   automorphism group of double trace   Biologija   branch-and-bound   dinamično programiranje   Disertacije   double trace   d-stabilni obhod   dvojni obhod   dynamic programming   E-predpisani obhod   grupa avtomorfizmov dvojnega obhoda   Matematično modeliranje   nanostructure design   oblikovanje nanostruktur   polipeptidni origami   polypeptide origami   razveji in omeji   samosestavljanje   self-assembling   single face embedding   spanning tree   strogi obhod   strong trace   vložitev z enim licem   vpeto drevo

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

Leta 2013 so Gradišar in sod. predstavili novo strategijo za oblikovanje samosestavljivih nanostruktur. Poglavitni uspeh njihove raziskave predstavlja izdelava polipeptidnega samosestavljivega tetraedra z združevanjem dvanajstih odsekov, ki paroma tvorijo ovite vijačnice v natančno določenem vrstnem redu. Natančneje, ena polipeptidna veriga je razporejena med 6 stranic tetraedra tako, da vsako stranico prečka natanko dvakrat. Na tak način se šest dimerov ovitih vijačnic zaklene v stabilno tetraedrsko strukturo. Polieder $P$, ki je sestavljen iz ene polipeptidne verige, lahko naravno predstavimo z grafom poliedra $G(P)$. Ker v tehnološkem procesu vsaka povezava $G(P)$ ustreza dimeru ovitih vijačnic, ustrezata vsaki povezavi natanko dva odseka. V ta namen predstavimo strogi (in $d$-stabilni) obhod grafa kot sklenjen sprehod, ki vsako povezavo grafa prečka dvakrat (takšen sprehod imenujemo tudi dvojni obhod), pri tem pa za vsako vozlišče $v$ velja, da ne obstaja taka podmnožica njegovih sosedov $N \subseteq N(v)$, $1 \leq |N| < d(v)$ ($1 \leq |N| \leq d$), da vsakič, ko sprehod pride v $v$ iz vozlišča v $N$, tudi zapusti $v$ v smeri proti vozlišču v $N$. S pomočjo povezave med vložitvami grafov z enim licem v ploskve višjega roda in strogimi obhodi ter klasičnima rezultatoma Edmondsa in Ringla lahko dokažemo, da vsak povezan graf vsebuje strogi obhod in da graf $G$ vsebuje $d$-stabilni obhod natanko tedaj, ko je povezan in je njegova minimalna stopnja $\delta(G) > d$. Dvojni obhod vsako povezavo grafa prečka dvakrat. Posledično lahko v dvojnem obhodu definiramo dva tipa povezav.Če dvojni obhod $W$ prečka povezavo $e$ dvakrat v isti smeri, pravimo, da je $e$ paralelna povezava (glede na $W$), sicer pa rečemo, da je $e$ antiparalelna povezava (glede na $W$). Nadalje je dvojni obhod grafa $G$ paralelni dvojni obhod, če je vsaka povezava v $G$ paralelna (glede na $W$), in antiparalelni dvojni obhod, če je vsaka povezava v $G$ antiparalelna (glede na $W$). Tudi motivacija za takšen pristop naravno izhaja iz lastnosti samosestavljivih nanostruktur. V delu karakteriziramo grafe, ki vsebujejo: (i) paralelne stroge obhode kot Eulerjeve grafe, (ii) paralelne $d$-stabilne obhode kot Eulerjeve grafe z minimalno stopnjo $\delta > d$, (iii) antiparalelne stroge obhode kot vse povezane grafe, v katerih obstaja vpeto drevo $T$ z lastnostjo, da ima vsaka povezana komponenta ko-drevesa $G - E(T)$ sodo število povezav, in (iv) antiparalelne $d$-stabilne obhode kot vse povezane grafe $G$ z minimalno stopnjo $\delta(G) > d$, v katerih obstaja vpeto drevo $T$ z lastnostjo, da je vsaka povezana komponenta ko-drevesa $G - E(T)$ soda ali pa vsebuje vozlišče stopnje najmanj $2d + 2$. Zadnji rezultat predstavlja tudi posplošitev problema, ki ga je leta 1951 postavil Ore in šele slabih 40 let kasneje rešil Thomassen (omenjeni problem v našem jeziku predstavlja karakterizacijo grafov, ki vsebujejo antiparalelne 1-stabilne obhode). Pri tem si med drugim pomagamo tudi z novimi ugotovitvami o vpetih drevesih s podobnimi lastnostmi, kot jih imajo Xuongova drevesa. Koncept $E$-predpisanih obhodov, tj. dvojnih obhodov, v katerih je vsaka povezava iz $E \subseteq E(G)$ antiparalelna in vsaka povezava iz $E(G) \setminus E$ paralelna, po eni strani združi rezultate o paralelnih in antiparalelnih dvojnih obhodih v preproste izreke ter po drugi strani v praksi pomaga kontrolirati lastnosti samosestavljivih nanostruktur. $E$-predpisane dvojne obhode sta neodvisno raziskovala že Vastergaard in Fleischner, medtem ko so rezultati o $E$-predpisanih strogih obhodih in $E$-predpisanih $d$-stabilnih obhodih povsem novi. Ker grafi vsebujejo več dvojnih obhodov, definiramo, da sta dva dvojna obhoda $W$ in $W'$ grafa $G$ ekvivalentna, kadar je moč $W'$ dobiti z obratom $W$, z zamikom $W$, z delovanjem permutacije, inducirane z avtomorfizmom grafa $G$ na $W$, ali s kombinacijo prej naštetih treh možnosti. V želji, da bi v praksi za dani polieder znali izbrati strogi obhod, ki bo imel največjo verjetnost, da se uspešno sestavi v samosestavljivo nanostrukturo želene oblike, smo razvili dva algoritma, ki generirata vse stroge obhode za dani graf $G$. Prvi algoritem temelji na algebraičnem pristopu in uporablja nekatera nova dognanja o grupi avtomorfizmov dvojnih obhodov, drugi pa se zanaša na topološke lastnosti grafa. Pri tem je časovna zahtevnost drugega za kubične grafe le $O(mf)$, kjer je $m$ število povezav, $f$ pa število lic v neki znani vložitvi grafa $G$.

12.05.2023