Preizkusite novo različico: COBISS+
 Lokalna baza podatkov: FMF in IMFM, Matematična knjižnica, Ljubljana (Štev. zapisov: 63.575) | Domača stran knjižnice

Izbrani zapis trajna povezava

AvtorRus, Jernej, 1987-
Naslov Matematično modeliranje problemov iz biologije : doktorska disertacija / Jernej Rus
Vrsta/vsebinatype of material disertacija
Jezikslovenski
Leto2017
Založništvo in izdelavaLjubljana : [J. Rus], 2017
Ostali avtorjiKlavžar, Sandi
Bokal, Drago, 1978-
Fizični opisXIV, 115 str. : ilustr. ; 30 cm
OpombeMentor Sandi Klavžar, somentor Drago Bokal
Bibliografija: str. 99-105
Povzetek ; Abstract
Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Predmetne oznake (nekontrolirane)oblikovanje nanostruktur / samosestavljanje / polipeptidni origami / dvojni obhod / strogi obhod / d-stabilni obhod / E-predpisani obhod / vložitev z enim licem / vpeto drevo / grupa avtomorfizmov dvojnega obhoda / razveji in omeji / dinamično programiranje / nanostructure design / self-assembling / polypeptide origami / double trace / strong trace / $d$-stable trace / $E$-restricted trace / single face embedding / spanning tree / automorphism group of double trace / branch-and-bound / dynamic programming
UDK519.17(043.3)
Druge klasifikacije
05C05
05C10
05C30
05C45
05C85
49L20
68R10
68Q25
90C39
92B05
92E10
94C15 (MSC 2010)
URLhttp://www.matknjiz.si/doktorati/2017/Rus-14521-28.pdf
PovzetekLeta 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$.
In 2013, Gradišar et al. presented a novel self-assembly strategy for polypeptide nanostructure design. The main success of their research is a construction of a polypeptide self-assembling tetrahedron by concatenating 12 coiled-coil-forming segments in a prescribed order. More precisely, a single polypeptide chain consisting of 12 segments was routed through 6 edges of the tetrahedron in such a way that every edge was traversed exactly twice. In this way, 6 coiled-coil dimers were created and interlocked into a stable tetrahedral structure. A polyhedron $P$, which is composed from a single polymer chain, can be naturally represented by a graph $G(P)$ of the polyhedron. As in the self-assembly process, every edge of $G(P)$ corresponds to a coiled-coil dimer, exactly two segments are associated with every edge of $G(P)$. We therefore introduce a strong (and a $d$-stable) trace of a graph as a closed walk that traverses every edge of graph twice, also called a double trace, and for every vertex $v$, there is no subset $N$ of its neighbors, with $1 \leq |N| < d(v)$ ($1 \leq |N| \leq d$), such that every time the walk enters $v$ from $N$, it also exits to a vertex in $N$, respectively. We then establish the duality between single face embeddings of graphs into surfaces of higher genera and strong traces, and use classical results of Edmonds and Ringel to charecterize graphs that admit strong traces (every connected graph) and $d$-stable traces (every connected graph $G$ with minimal degree $\delta(G) > d$). Every edge is traversed twice in a double trace. Consequently, if a double trace $W$ traverses an edge $e$ in the same direction twice, then we call $e$ a parallel edge (with respect to $W$), otherwise e is an antiparallel edge. A double trace $W$ of a graph $G$ is then a parallel double trace if every edge of $G$ is parallel (with respect to $W$) and an antiparallel double trace if every edge of $G$ is antiparallel (with respect to $W$). The motivation for this approach naturally arises from the properties of selfassembling nanostructures. We characterize graphs which admit: (i) parallel strong traces as Eulerian graphs, (ii) parallel $d$-stable traces as Eulerian graphs with minimal degree $> d$, (iii) antiparallel strong traces as connected graphs $G$ in which there exists a spanning tree $T$ with the property that every connected component of the co-tree $G - E(T)$ has an even number of edges, and (iv) antiparallel $d$-stable traces as connected graphs $G$ with minimal degree $> d$ in which there exists a spanning tree $T$ with the property that every connected component of the co-tree $G - E(T)$ is even or contains a vertex of degree at least $2d + 2$. The last result also generalizes a problem posed by Ore back in the 1950s and solved by Thomassen almost 40 years later. In our notation, problem raised by Ore could be read as characterizing the graphs, which admit antiparallel 1-stable traces. For solving this problem, we among other use some new discoveries about spanning trees similair to Xuong trees. The concept of $E$-restricted traces, that is, a double trace where every edge from a set $E(G) \subseteq E$ is antiparallel and every edge from $E(G) \setminus E$ is parallel, on the one hand unify the results about parallel and antiparallel double traces while on the other hand also bid us more control over the properties of self-assembling nanostructures during their construction when being used as a mathematical model. Results regarding $E$-restricted double traces were already well known and independently proven by Vastergaard and by Fleischner, while theorems about $E$-restricted strong traces and $E$-restricted $d$-stable traces are new results. Since graphs admit multiple double traces, we define double traces $W$ and $W'$ of a graph $G$ to be equivalent, if $W'$ can be obtained from $W$ by reversion $W$, by shifting $W$, by applying a permutation on $W$ induced by an automorphisms of $G$, or using any combination of the previous three operations. In order to be able to maximize the probability which strong trace to choose for a given nanostructure so that an appropriate polypeptide chain will self assemble into the desired structure, we develop two algorithms for generating all non equivalent strong traces for a given graph $G$. The first algorithm is based on an algebraic approach and uses some new discoveries about the automorphism group of double traces, while the second relies on topological properties of a graph and has complexity $O(mf)$ for cubic graphs, where $m$ is the number of edges and $f$ is the number of faces in some fixed embedding of $G$.
COBISS.SI-ID17985881

info Dostopna je elektronska verzija dokumenta ali pa gre za elektronski vir

Statusi v izposoji

Podatki o izvodu (signatura - lokacija, inventarna št. ...) Status izvoda Rezervacija
Knjižnica 14521/28 001availability  prosto - za čitalnico