TY - THES A1 - Breuer, David T1 - The plant cytoskeleton as a transportation network T1 - Modellierung des pflanzliche Zytoskeletts als Transportnetzwerk N2 - The cytoskeleton is an essential component of living cells. It is composed of different types of protein filaments that form complex, dynamically rearranging, and interconnected networks. The cytoskeleton serves a multitude of cellular functions which further depend on the cell context. In animal cells, the cytoskeleton prominently shapes the cell's mechanical properties and movement. In plant cells, in contrast, the presence of a rigid cell wall as well as their larger sizes highlight the role of the cytoskeleton in long-distance intracellular transport. As it provides the basis for cell growth and biomass production, cytoskeletal transport in plant cells is of direct environmental and economical relevance. However, while knowledge about the molecular details of the cytoskeletal transport is growing rapidly, the organizational principles that shape these processes on a whole-cell level remain elusive. This thesis is devoted to the following question: How does the complex architecture of the plant cytoskeleton relate to its transport functionality? The answer requires a systems level perspective of plant cytoskeletal structure and transport. To this end, I combined state-of-the-art confocal microscopy, quantitative digital image analysis, and mathematically powerful, intuitively accessible graph-theoretical approaches. This thesis summarizes five of my publications that shed light on the plant cytoskeleton as a transportation network: (1) I developed network-based frameworks for accurate, automated quantification of cytoskeletal structures, applicable in, e.g., genetic or chemical screens; (2) I showed that the actin cytoskeleton displays properties of efficient transport networks, hinting at its biological design principles; (3) Using multi-objective optimization, I demonstrated that different plant cell types sustain cytoskeletal networks with cell-type specific and near-optimal organization; (4) By investigating actual transport of organelles through the cell, I showed that properties of the actin cytoskeleton are predictive of organelle flow and provided quantitative evidence for a coordination of transport at a cellular level; (5) I devised a robust, optimization-based method to identify individual cytoskeletal filaments from a given network representation, allowing the investigation of single filament properties in the network context. The developed methods were made publicly available as open-source software tools. Altogether, my findings and proposed frameworks provide quantitative, system-level insights into intracellular transport in living cells. Despite my focus on the plant cytoskeleton, the established combination of experimental and theoretical approaches is readily applicable to different organisms. Despite the necessity of detailed molecular studies, only a complementary, systemic perspective, as presented here, enables both understanding of cytoskeletal function in its evolutionary context as well as its future technological control and utilization. N2 - Das Zytoskelett ist ein notwendiger Bestandteil lebender Zellen. Es besteht aus verschiedenen Arten von Proteinfilamenten, die ihrerseits komplexe, sich dynamisch reorganisierende und miteinander verknüpfte Netzwerke bilden. Das Zytoskelett erfüllt eine Vielzahl von Funktionen in der Zelle. In Tierzellen bestimmt das Aktin-Zytoskelett maßgeblich die mechanischen Zelleigenschaften und die Zellbewegung. In Pflanzenzellen hingegen kommt dem Aktin-Zytoskelett eine besondere Bedeutung in intrazellulären Transportprozessen zu, bedingt insbesondere durch die starre pflanzliche Zellwand sowie die Zellgröße. Als wesentlicher Faktor für Zellwachstum und somit auch die Produktion von Biomasse, ist Zytoskelett-basierter Transport daher von unmittelbarer ökologischer und ökonomischer Bedeutung. Während das Wissen über die molekularen Grundlagen Zytoskelett-basierter Transportprozesse beständig wächst, sind die zugrunde liegenden Prinzipien zellweiter Organisation bisher weitgehend unbekannt. Diese Dissertation widmet sich daher folgender Frage: Wie hängt die komplexe Architektur des pflanzlichen Zytoskeletts mit seiner intrazellulären Transportfunktion zusammen? Eine Antwort auf diese Frage erfordert eine systemische Perspektive auf Zytoskelettstruktur und -transport. Zu diesem Zweck habe ich Mikroskopiedaten mit hoher raumzeitlicher Auflösung sowie Computer-gestützte Bildanalysen und mathematische Ansätzen der Graphen- und Netzwerktheorie kombiniert. Die vorliegende Dissertation umfasst fünf meiner Publikationen, die sich einem systemischen Verständnis des pflanzlichen Zytoskeletts als Transportnetzwerk widmen: (1) Dafür habe ich Bilddaten-basierte Netzwerkmodelle entwickelt, die eine exakte und automatisierte Quantifizierung der Architektur des Zytoskeletts ermöglichen. Diese Quantifizierung kann beispielsweise in genetischen oder chemischen Versuchen genutzt werden und für eine weitere Erforschung der genetischen Grundlagen und möglicher molekularer Interaktionspartner des Zytoskeletts hilfreich sein; (2) Ich habe nachgewiesen, dass das pflanzliche Aktin-Zytoskelett Eigenschaften effizienter Transportnetzwerk aufweist und Hinweise auf seine evolutionären Organisationsprinzipien liefert; (3) Durch die mathematische Optimierung von Transportnetzwerken konnte ich zeigen, dass unterschiedliche Pflanzenzelltypen spezifische und optimierte Organisationsstrukturen des Aktin-Zytoskeletts aufweisen; (4) Durch quantitative Analyse des Transports von Organellen in Pflanzenzellen habe ich nachgewiesen, dass sich Transportmuster ausgehend von der Struktur des Aktin-Zytoskeletts vorhersagen lassen. Dabei spielen sowohl die Organisation des Zytoskeletts auf Zellebene als auch seine Geometrie eine zentrale Rolle. (5) Schließlich habe ich eine robuste, optimierungs-basierte Methode entwickelt, die es erlaubt, individuelle Filamente eines Aktin-Netzwerks zu identifizieren. Dadurch ist es möglich, die Eigenschaften einzelner Zytoskelettfilamente im zellulären Kontext zu untersuchen. Die im Zuge dieser Dissertation entwickelten Methoden wurden frei und quelloffen als Werkzeuge zur Beantwortung verwandter Fragestellung zugänglich gemacht. Insgesamt liefern die hier präsentierten Ergebnisse und entwickelten Methoden quantitative, systemische Einsichten in die Transportfunktion des Zytoskeletts. Die hier etablierte Kombination von experimentellen und theoretischen Ansätzen kann, trotz des Fokusses auf das pflanzliche Zytoskelett, direkt auf andere Organismen angewendet werden. Als Ergänzung molekularer Studien bildet ein systemischer Blickwinkel, wie er hier entwickelt wurde, die Grundlage für ein Verständnis sowohl des evolutionären Kontextes als auch zukünftiger Kontroll- und Nutzungsmöglichkeiten des pflanzlichen Zytoskeletts. KW - systems biology KW - mathematical modeling KW - cytoskeleton KW - plant science KW - graph theory KW - image analysis KW - Systembiologie KW - mathematische Modellierung KW - Zytoskelett KW - Zellbiologie KW - Graphtheorie KW - Bildanalyse Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-93583 ER - TY - THES A1 - Fischer, Jens Walter T1 - Random dynamics in collective behavior - consensus, clustering & extinction of populations T1 - Stochastische Dynamiken in kollektivem Verhalten: Konsens, Gruppenbildung, Aussterben von Populationen N2 - The echo chamber model describes the development of groups in heterogeneous social networks. By heterogeneous social network we mean a set of individuals, each of whom represents exactly one opinion. The existing relationships between individuals can then be represented by a graph. The echo chamber model is a time-discrete model which, like a board game, is played in rounds. In each round, an existing relationship is randomly and uniformly selected from the network and the two connected individuals interact. If the opinions of the individuals involved are sufficiently similar, they continue to move closer together in their opinions, whereas in the case of opinions that are too far apart, they break off their relationship and one of the individuals seeks a new relationship. In this paper we examine the building blocks of this model. We start from the observation that changes in the structure of relationships in the network can be described by a system of interacting particles in a more abstract space. These reflections lead to the definition of a new abstract graph that encompasses all possible relational configurations of the social network. This provides us with the geometric understanding necessary to analyse the dynamic components of the echo chamber model in Part III. As a first step, in Part 7, we leave aside the opinions of the inidividuals and assume that the position of the edges changes with each move as described above, in order to obtain a basic understanding of the underlying dynamics. Using Markov chain theory, we find upper bounds on the speed of convergence of an associated Markov chain to its unique stationary distribution and show that there are mutually identifiable networks that are not apparent in the dynamics under analysis, in the sense that the stationary distribution of the associated Markov chain gives equal weight to these networks. In the reversible cases, we focus in particular on the explicit form of the stationary distribution as well as on the lower bounds of the Cheeger constant to describe the convergence speed. The final result of Section 8, based on absorbing Markov chains, shows that in a reduced version of the echo chamber model, a hierarchical structure of the number of conflicting relations can be identified. We can use this structure to determine an upper bound on the expected absorption time, using a quasi-stationary distribution. This hierarchy of structure also provides a bridge to classical theories of pure death processes. We conclude by showing how future research can exploit this link and by discussing the importance of the results as building blocks for a full theoretical understanding of the echo chamber model. Finally, Part IV presents a published paper on the birth-death process with partial catastrophe. The paper is based on the explicit calculation of the first moment of a catastrophe. This first part is entirely based on an analytical approach to second degree recurrences with linear coefficients. The convergence to 0 of the resulting sequence as well as the speed of convergence are proved. On the other hand, the determination of the upper bounds of the expected value of the population size as well as its variance and the difference between the determined upper bound and the actual value of the expected value. For these results we use almost exclusively the theory of ordinary nonlinear differential equations. N2 - Beziehungen und damit Interaktion sowie Diskussion, aber auch Konflikt und Opposition bilden die Grundbausteine einer jeden Gesellschaft. Häufig wird Kommunikation als der übergreigende Begriff zur Beschreibung interner Strukturen einer Gesellschaft identifiziert. Dabei muss es sich aber nicht um eine Gesellschaft im Sinne von Nationen handeln, sondern kann auch schlicht eine Gruppe von Menschen umfassen, die miteinander strukturiert interagieren, beispielsweise, eine Gruppe von Angestellten, die an einem gemeinsamen Projekt arbeiten, oder die Mitglieder eines sozialen Netzwerks. In dieser Arbeit befassen wir uns mit der mathematischen Beschreibung solcher Prozesse innerhalb von Gruppen und Gesellschaften und legen dabei unseren Fokus auf die Bildung eines Konsens durch Interaktion aber auch die Konsequenzen von Konflikt und das potentielle Aussterben einer Population. Dabei werden zwei Modelle im Fokus des Interesses stehen: Das Echokammer Model sowie eine Erweiterung des Geburts-Todes Prozesses, die die Möglichkeit eines radikalen Abfalls der Populationsgr öße miteinschließt. Wir beginnen mit einer Einführung in Part I und teilen die verbleibende Arbeit in drei Teile auf, wobei sich die ersten beiden technischen Abschnitte, Part II und III, mit einer ausführlichen Analyse der Bausteine des Echokammer Models befassen und im dritten Abschnitt, in Part IV, der erweiterte Geburts- Todes Prozess untersucht wird. Dieser wird im Folgenden als Geburts-Todes Prozess mit teilweiser Katastrophe bezeichnet werden. Das Echokammer Model beschreibt die Entwicklung von Gruppen in zunächst heterogenen sozialen Netzwerken. Unter einem heterogenen sozialen Netzwerk verstehen wir dabei eine Menge von Individuen, von denen jedes exakt eine Meinungen vertritt. Meinungen werden vereinfacht durch Werte in [0, 1] modelliert. Bestehende Beziehungen unter den Individuen können dann durch einen Graphen dargestellt werden. Es handelt sich bei dem Echokammer Modell um ein zeit-diskretes Modell, das entsprechend, ähnlich einem Brettspiel, in Zügen abläuft. In jedem Zug wird zufällig gleichverteilt eine bestehende Beziehung aus dem Netzwerk ausgewählt und die beiden verbundenen Individuen interagieren. Dabei kann es zu zwei verschiedenen Interaktionen kommen. Sind die Meinungen der betroffenen Individuen hinreichend ähnlich, so nähern sie sich weiter in ihren Meinungen an, während sie im Fall von Meinungen, die zu weit von einander liegen, ihre Beziehung auflösen und sich eines der Individuen eine neue Beziehung sucht. 8 In dieser Arbeit untersuchen wir theoretisch die Bausteine dieses Modells. Dabei legen wir die Beobachtung zu Grunde, dass die Veränderungen der Beziehungsstruktur im Netzwerk durch einen System von interagierenden Partikeln auf einem abstrakteren Raum beschrieben werden kann. Dies erlaubt es insbesondere graphentheoretische überlegungen in die Analyse einfließen zu lassen. Diese überlegungen werden ausührlich in Part II diskutiert und führen zur Definition eines neuen, abstrahierten Graphens, der alle möglichen Beziehungskonfigurationen des sozialen Netzwerks umfasst. Dies erlaubt es uns einen ähnlichkeitsbegriff für Beziehungskonfigurationen auf Basis der benachbarten Knoten in besagtem Graphen zu definieren. Dies liefert uns das notwendige geometrische Verständnis um in Part III die dynamischen Komponenten des Echokammer models zu analysieren. Insbesondere fokusieren wir uns dabei auf die Dynamik der Kanten, für die bisher in der Literatur noch keine Ergebnisse existieren. Wir lassen zunächst in Abschnitt 7 die Meinungen der Individuen beiseite und nehmen an, dass die Position der Kanten sich in jedem Zug wie zuvor beschrieben ändert, um eine grundlegendes Verständnis der unterliegenden Dynamik zu erhalten. Unter der Verwendung der Theorie von Markovketten finden wir obere Schranken an die Konvergenzgeschwindigkeit einer assoziierten Markovkette gegen ihre eindeutige stationäre Verteilung und zeigen, dass es Netzwerke gibt, die miteinander identifizierbar und unter der analysierten Dynamik daheingehend ununterscheinbar sind, dass die stationäre Verteilung der assozierten Markovkette diesen Netzwerken dasselbe Gewicht zuordnet. Anschließend beweisen wir eine Reihe von quantitativen Resultaten, die sich insbesondere in Fällen, in denen die assozierte Markovkette reversibel ist, als berechenbar herausstellen. Insbesondere die explizite Form der stationären Verteilung sowie untere Schranken an die Cheeger Konstante zur Beschreibung der Konvergenzgeschwindigkeit stehen dabei im Fokus und werden ausführlich diskutiert. Nach dieser vertieften Analyse des reduzierten Modells, fügen wir die Meinungen unserer Betrachtung wieder hinzu. Das abschließende Result in Abschnitt 8, basierend auf absorbierenden Markovketten, liefert dann, dass in einer reduzierte Version des Echokammer Modells, in dem sich Individuen ähnlicher Meinung nicht annähern, eine hierarchische Struktur der Anzahl der konfliktreichen Beziehung identifiziert werden kann. Dies können wir ausnutzen, um eine obere Schranke an die erwartete Absorptionszeit, unter Zuhilfenahme einer quasi-stationären Verteilung, zu bestimmen. Diese hierarchische Struktur bildet außerdem eine Brücke zu klassischen Theorien von Geburts-Todes und, insbesondere, reinen Todes-Prozessen, für die eine reiche Literatur existiert. Wir zeigen abschließend auf, wie künftige Forschung diese Verbindung ausnutzen kann und diskutieren die Wichtigkeit der Ergbenisse als Bausteine eines vollständigen theoretischen Verständnisses des Echokammer Modells. Part IV stellt abschließend einen veröffentlichten Artikel vor, der sich dem Geburts- Todes Prozess mit teilweiser Katastrophe widmet. Besagter Artikel steht dabei auf zwei Säulen. Zum Einen der expliziten Berechnung des ersten Zeitpunkts einer Katastrophe, wenn die Population zu Beginn der Beobachtung von instabiler Größe ist. KW - Markov chains KW - graph theory KW - complex systems KW - interacting particle systems KW - Markovketten KW - komplexe Systeme KW - Graphentheorie KW - Systeme interagierender Partikel Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-553725 ER - TY - THES A1 - Katzmann, Maximilian T1 - About the analysis of algorithms on networks with underlying hyperbolic geometry T1 - Über die Analyse von Algorithmen auf Netzwerken mit zugrundeliegender hyperbolischer Geometrie N2 - Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this thesis, we demonstrate that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, we first introduce strongly hyperbolic unit disk graphs and identify the famous hyperbolic random graph model as a special case of them. We then consider four problems where recent empirical results highlight a gap between theory and practice and use hyperbolic graph models to explain these phenomena theoretically. First, we develop a routing scheme, used to forward information in a network, and analyze its efficiency on strongly hyperbolic unit disk graphs. For the special case of hyperbolic random graphs, our algorithm beats existing performance lower bounds. Afterwards, we use the hyperbolic random graph model to theoretically explain empirical observations about the performance of the bidirectional breadth-first search. Finally, we develop algorithms for computing optimal and nearly optimal vertex covers (problems known to be NP-hard) and show that, on hyperbolic random graphs, they run in polynomial and quasi-linear time, respectively. Our theoretical analyses reveal interesting properties of hyperbolic random graphs and our empirical studies present evidence that these properties, as well as our algorithmic improvements translate back into practice. N2 - Viele komplexe Systeme mit denen wir tagtäglich zu tun haben, können mit Hilfe von Netzwerken beschrieben werden, welche daher schon jahrzehntelang im Fokus der Informatik stehen. Dort werden Algorithmen entwickelt, um diese Systeme besser verstehen und nutzen zu können. Überraschenderweise unterscheidet sich unsere theoretische Vorstellung dieser Algorithmen jedoch oft immens von derem praktischen Verhalten. Tatsächlich neigen sie dazu auf echten Netzwerken viel effizienter zu sein, als man im schlimmsten Fall erwarten würde. Eine Möglichkeit diese Diskrepanz zu erfassen ist die Average-Case Analyse bei der man die Unterschiede zwischen echten Instanzen und dem schlimmsten Fall ausnutzt, indem ausschließlich Netzwerke betrachtet werden, deren Eigenschaften die von echten Graphen gut abbilden. Jüngste Beobachtungen zeigen, dass gute Abbildungen entstehen, wenn man annimmt, dass einem Netzwerk eine hyperbolische Geometrie zugrunde liegt. In dieser Arbeit wird demonstriert, dass hyperbolische Netzwerke als mächtiges Werkzeug der Average-Case Analyse dienen können. Dazu werden stark-hyperbolische Unit-Disk-Graphen eingeführt und die bekannten hyperbolischen Zufallsgraphen als ein Sonderfall dieser identifiziert. Anschließend werden auf diesen Modellen vier Probleme analysiert, um Resultate vorangegangener Experimente theoretisch zu erklären, die eine Diskrepanz zwischen Theorie und Praxis aufzeigten. Zuerst wird ein Routing Schema zum Transport von Nachrichten entwickelt und dessen Effizienz auf stark-hyperbolischen Unit-Disk-Graphen untersucht. Allgemeingültige Effizienzschranken können so auf hyperbolischen Zufallsgraphen unterboten werden. Anschließend wird das hyperbolische Zufallsgraphenmodell verwendet, um praktische Beobachtungen der bidirektionalen Breitensuche theoretisch zu erklären und es werden Algorithmen entwickelt, um optimale und nahezu optimale Knotenüberdeckungen zu berechnen (NP-schwer), deren Laufzeit auf diesen Graphen jeweils polynomiell und quasi-linear ist. In den Analysen werden neue Eigenschaften von hyperbolischen Zufallsgraphen aufgedeckt und empirisch gezeigt, dass sich diese sowie die algorithmischen Verbesserungen auch auf echten Netzwerken nachweisen lassen. KW - graph theory KW - hyperbolic geometry KW - average-case analysis KW - Average-Case Analyse KW - Graphentheorie KW - hyperbolische Geometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-582965 ER -