Page 1 of 1

autoPACK und cellPACK [DEUTSCH]

Posted: 18.10.2013, 14:23
by kjarosch
autoPACK/cellPACK
autoPACK und cellPACK sind Open Source Packing Algorithmen, die es ermöglichen, Oberflächen, Sphären und Volumina mit Objekten zu füllen. In der folgenden Hausarbeit werden diese beiden Programme vorgestellt und anhand der folgenden Punkte die großen Verbesserungen im Bereich der Zellvisualisierung herausgestellt:

• Packungsprobleme
• der ideale Algorihtmus
• autoPACK (autoFILL)
• Workflow
• cellPACK
• Anwendungen und Wettbewerbe
• Zusammenfassung


Packungsprobleme
Um sich den Nutzen der beiden Algorithmen autoPACK und cellPACK zu verdeutlichen, ist es zunächst notwendig, sich eine Klasse der Optimierungsprobleme anzuschauen und zu definieren. Zu dieser Klasse gehören die sogenannten Packungsprobleme. Diese Probleme beschäftigen sich damit, verschiedene Objekte optimal und mit wenig bzw. keiner Überlappung sowie mit minimalstem Abstand zueinander in Oberflächen, Sphären oder in Volumina anzuordnen. Ziel der Mathematiker und Informatiker ist es dabei Algorithmen zu finden, die es ermöglichen, die optimale Anordnung von Objekten innerhalb eines vorher definierten Raumes mittels Computer errechnen und bestimmen zu lassen.

Zusätzlich ist zu erwähnen, dass jedes Packungsproblem sogenannte covering problems beinhaltet. Diese Probleme in der Kombinatorik und der Computerwissenschaft beschreiben die Auseinandersetzung mit informationstechnischen Problemen, die sich u.a. mit den Fragen beschäftigen, ob eine berechnete Struktur (Objekt) eine andere überdeckt oder wie groß diese sein darf, sein muss, um zum Optimum zu gelangen. Diese Arten von Problemen gehören zu den Minimierungsansätzen.
In der Zellvisualisierung sind zusätzliche Schwierigkeiten zur Lösung des Packungsproblems zu beachten, da keine abstrakten Objekte oder Formen in einem Raum angeordnet werden sondern komplexe Moleküle. Biologische Moleküle (Objekte) weisen verschiedene komplexe Formen auf, wechselwirken mit unterschiedlich stark untereinander, sodass verschiedenste Konformationen auftreten können. Dennoch können die Moleküle nicht vergrößert, gestaucht oder verkleinert werden, was als loose packing problem bezeichnet wird. Da jedoch das Wissen über makromolekulare Interaktionen noch recht dürftig ist und alle Zusammenhänge innerhalb der Zelle nicht bekannt sind, ist es bisher unmöglich eine Zelle Baustein für Baustein zu modellieren. Auch Experten halten dies für die nächsten Jahrzehnte für unmöglich, da der Aufbau und die Interaktionsvielfalt innerhalb der Zelle unbeschreiblich komplex sind.[1].
Darüber hinaus sind einige Oberflächenbestandteile hoch organisiert, wie z.B. die bekannten lipid rafts oder in der gleichen Oberfläche willkürlich angeordnet, wie z.B. die verschiedenen Phospholipide.
Des Weiteren sorgt die Kombination von Oberflächenmodellierung und die Modellierung von Zellvolumina für zusätzliche Aspekte, die in der Entwicklung des Packungsalgorithmus beachtet werden müssen.

Der ideale Algorithmus
Wie wir nun sehen konnten, sind einige Dinge bei der Entwicklung eines für die zellvisualisierungsrelevanten Packungsalgorithmus zu beachten. Laut Graham T. Johnson, dem Entwickler des autoPACK und cellPACK Plug-In´s, müsste ein idealer Algorithmus die folgenden Eigenschaften aufweisen.
1. Anordnung von Objekten im Raum (zufällig bzw. basierend auf deren Mengenverteilung) [1]
Hiermit ist die Anordnung von Objekten in allen möglichen Formen gemeint, d.h. ein idealer Algorithmus muss in der Lage sein, in spezifischen Volumina oder gewölbten Oberflächen Objekte realitätsgetreu anzuordnen.
2. Verfahrensorientiert arbeiten[1]
Hiermit ist die Anordnung der Objekte unter Berücksichtigung ihrer Eigenschaften gemeint. Verfahrensorientiert arbeiten beschreibt somit die Verwendung des gesamten Wissens über ein Objekt, was im Rahmen von kristallographischen Untersuchungen oder auch in der Mikroskopie gesammelt werden konnte.
3. Muss iterativ und homogen arbeiten[1]
Der ideale Algorithmus vermeidet somit die Ausbildung von Gradienten oder Neigungen.
4. skalierbar und parallelisierbar [1]

autoPACK
Ein Algorithmus der versucht, diese Dinge zu berücksichtigen, ist das Plug-In autoPACK. Dieses Plug-In ermöglicht es, innerhalb eines 3D-Grafiksoftware eine Oberflächenmodellierung durchzuführen. Mittels autoPACK ist der Anwender in der Lage, Objekte und Formen in Oberflächen, Sphären und Volumina anordnen zu lassen. [2] Dabei bietet das Programm folgende Eigenschaften:
• Keine bis minimale Überlappung (Methodenabhängig) [2]
• Genauigkeit vs. Geschwindigkeit (Usereinstellung) [2]
„Zero edge effects“ [2]
• Zufällige oder geordnete Verteilung der Objekte möglich[2]
• Agentenbasierte Interaktion, Gewichtung und Kollisionskontrolle[2]

Der vom autoPACK genutzte Algorithmus vereinigt die bisher bekannten regulären und rechnerischen Packungslösungen und stellt eine heuristische Lösung für das sogenannte loose packing problem dar.

Workflow
Die Arbeitsweise des Plug-In´s ist dabei sehr gut im Workflow von Grahem T. Johnson beschrieben. Vor dem Start des Programmes wird vom Programm eine Definition der Fläche bzw. des Raumes erfragt. Durch diese Information, lädt autoPACK eine sogenannte Masterlist, die innerhalb einer Datenbank lokalisiert ist und die entsprechenden Moleküle der zugehörigen Oberfläche bzw. des Raum auflistet. Diese Liste enthält alle bisher bekannten Moleküle und kann vom Anwender ergänzt oder bestimmte Moleküle entfernt werden, je nach Anwendungswunsch. Falls eine solche Masterlist nicht zur Verfügung steht, wird der Anwender gebeten, eine Liste anzufertigen. Innerhalb der Liste sind nicht nur die Mengenverteilung der Moleküle, sondern auch weitere biologische Informationen beschrieben, wie z.B. Interaktionspartner oder dessen Orientierung in der Oberfläche.
Der nächste Schritt ist die Anordnung der Moleküle auf einer Oberfläche oder in einem Raum. Hierfür ist es notwendig, Gitterpunkte zu definieren, um die Lokalisierung des Objektes/Moleküls zu berechnen. Für die Erzeugung der Gitterpunkte werden die kleinsten Moleküle genutzt, um den möglichst minimalsten Abstand zwischen diesen Molekülen zu bestimmen. Dieser Abstand wird so bestimmt, dass in es zu keiner Kollision zwischen den verwendeten Molekülen kommt. Dieser Abstand dient als Basis für die Entfernung jedes einzelnen Gitterpunkt, an dem die Zuordnung der Molekül/Objekt Lokalisierung stattfindet.
Nach der Erzeugung des Gitters werden die Moleküle/Objekte vom Programm priorisiert und entsprechend angeordnet. Die Priorisierung beschreibt dabei, wie schwierig ein Molekül in eine Oberfläche oder Raum zu packen ist. Moleküle/Objekte, die schwer zu packen sind, da sie groß sind oder komplexe Strukturen aufweisen, werden am Anfang gepackt und erhalten somit eine höhere Priorisierung, da kleinere Moleküle/Objekte in die „Lücken“ der großen gepackt werden können. Dies ermöglicht, eine möglichst enge und realitätsgetreue Packung.
Werden zunächst die kleineren Moleküle angeordnet, kann dies dazu führen, dass die Packung zu locker ist oder dass einige Moleküle nicht mehr gepackt werden können, womit sich die Zusammensetzung ändert. Dies wird mit der Priorisierung vermieden.
Die Verfahren mit denen autoPACK die Moleküle/Objekte anordnet, kann auf 2 Arten geschehen. Entweder findet die Anordnung durch Wahl des Gitterpunktes statt, d.h. der Gitterpunkt wird gewählt und autoPACK ermittelt ein geeignetes Molekül/Objekt hierfür, oder autoPACK wählt ein Molekül/Objekt aus und versucht dieses, an einem Gitterpunkt anzuordnen. Bei der Anordnung werden diverse Kriterien versucht zu berücksichtigen. Findet eine Überlappung statt, wird das Molekül rotiert und überprüft, ob die Überlappung weiterhin vorliegt. Zusätzlich ist autoPACK in der Lage die Kräfte, die zwischen Molekülen/Objekten auftreten können, bei der Anordnung mit zu berücksichtigen.

cellPACK
cellPACK ist eine Spezialisierung von autoPACK, die die verschiedenen Darstellungsmöglichkeiten von biologischen Molekülen, die mittels ePMV möglich sind, mit dem Packungsalgorithmus von autoPACK verbindet. Hiermit können 3D-Modelle mit einer beliebigen Anzahl von biologischen Molekülen erstellt werden. Wie oben schon erwähnt, werden dabei zusätzliche Informationen über die Moleküle genutzt, um eine möglichst realitätsgetreue Darstellung zu ermöglichen und molekulare Interaktionen zu visualisieren.

Anwendungen und Wettbewerbe
Die Möglichkeiten mit diesen Programmen, eine Zellvisualisierung zu entwickeln oder aufzubauen, sind beeindruckend. Früher war es nur möglich, mit künstlerischem Geschick z.B. unter Verwendung von Wasserfarben wie bei David S. Goodsell der durch zeitlich sehr aufwendiges designen in 3D-Grafikprogrammen eine Visualisierung aufzubauen. Mit Hilfe dieser Programme ist es sehr schnell möglich, Oberflächen zu füllen und eine Visualisierung schneller und womöglich auch genauer zu generieren. Dies kann nicht nur für Bilder sondern zudem in Videoanimationen genutzt werden. Das war auch einer der Gründe, warum die Society of Digitalartist einen Wettbewerb mit dem Namen autoPACK Visualisation Challenge 2012 ausgerichtet hat.

Zusammenfassung
autoPACK und cellPACK sind nützliche und innovative Open-Source Software Plug-In´s, die es ermöglichen, biologische Moleküle und Objekte in verschiedenen Ordnungen zu packen. Mit Hilfe dieser Software-Erweiterungen ist es möglich, die Kommunikation und die Wissensverbreitung effizienter zu gestalten. Durch die Vereinigung von biologisch relevanten Packungsalgorithmen mit mathematischen Packungsalgorithmen ist es nun möglich, computerbasierte Modelle zu konstruieren und neue Sachverhalte zu visualisieren, was eine Verbesserung der Präsentationsmöglichkeiten von Theorien und Daten hervorbringt. Dennoch ist zu erwähnen, dass dieses Tool noch nicht ausgereift ist und einige Fehler vorweist. Durch den modularen Aufbau der Plug-In´s ist eine Erweiterung und Verbesserung möglich und notwendig, besonders, da die ausgesprochene Kompatibilität mit allen bekannten 3D-Grafikprogrammen nicht 100% gegeben ist. Nichts destotrotz sind die Möglichkeiten, die mit Hilfe dieses Programms möglich sind, beeindruckend und für die Visualisierungscommunity eine Bereicherung.

Literatur
[1] Graham T. Johnson, Automated Modeling and Visualization of Cellular Mesoscale, PHD Thesis, La Jolla, California, 2011
[2] Internet Website: http://www.autopack.org

Bilder
Alle Bilder mit freundlicher Genehmigung von Graham Johnson (http://fivth.com).

Anhang
Die Präsentation befindet sich im geschlossenen Bereich.

Re: autoPACK und cellPACK [DEUTSCH]

Posted: 15.06.2017, 09:16
by CarissaKing
Thanks for sharing this link concerns regarding packing problem and also the solutions. Since this is always important to get the solution for the problems. Because not everybody can be the problem solver. As many of us are problem creator and just a few people have that ability to solve it.