Heß, Martin (2013)
Visuell-interaktiver Vergleich vieler hierarchischer Strukturen.
Technische Universität Darmstadt
Masterarbeit, Bibliographie

Kurzbeschreibung (Abstract)

Hierarchische Strukturen sind in verschiedenen Anwendungsgebieten weit verbreitet. Ein Beispiel hierfür ist die aktuelle Forschung im Bereich der Phylogenese. Insbesondere der Vergleich einer sehr großen Menge sogenannter Phylogenetischer Bäume ist hier von Bedeutung. Das Hauptziel hierbei ist Ähnlichkeiten und Unterschiede zwischen den einzelnen Bäumen aufzudecken. Durch die Größe, Komplexität und Anzahl dieser Bäume ist ihr Vergleich durch den Menschen jedoch sehr schwierig. Aktelle Forschungsarbeiten beschäftigen sich daher unter anderem mit der Entwicklung neuer Techniken, um auch eine große Anzahl solcher Bäume vergleichen zu können und den Benutzer bei der Arbeit zu unterstützen. Das Forschungsgebiet Visual Analytics bietet dafür Lösungsansätze in Form von interaktiven Visualisierungen gepaart mit Dataminingtechniken an. Der neue Visual Analytics Ansatz dieser Masterarbeit ermöglicht den visuellen interaktiven Vergleich sehr großer Mengen von Hierarchischen Strukturen in Bezug auf deren Elemente, Topologie und Erstellungsparametern. Der Vergleich wird dabei mittels mehrerer Schritte durchgeführt. Im ersten Schritt werden die Hierarchischen Strukturen mittels eines Hierarchischen Clusteringverfahrens in Abhängigkeit ihrer Ähnlichkeit zueinander gruppiert. Hieraus resultiert eine sogenannte Superhierarchie. Im nächsten Schritt werden in dieser Superhierarchie relevante Substrukturen (Gruppen ähnlicher Hierarchien) identifiziert. Dies geschieht mittels eines automatischen Schwellenwert-Auswahl-Verfahrens. Der letzte Schritt besteht in der Auswahl eines einzelnen Repräsentanten für jede der identifizierten Substrukturen. Die Auswahl ist dabei von der Ähnlichkeit des Repräsentanten zu allen anderen Hierarchien aus der gleichen Substruktur abhängig. Ein Repräsentant steht für eine ganze Gruppe ähnlicher Hierarchien und kann stellvertretend für diese im Vergleich genutzt werden. Auf diese Weise wird der Vergleich sehr vieler Hierarchien auf eine kleine Menge von Repräsentanten reduziert. Dieser Vergleich wird in diesem Ansatz mittels einer bestehenden Technik vorgestellt von Bremm et al. BvLH+11 durchgeführt. Durch diesen Ansatz wird der Anwender in die Lage versetzt, mehr als 1000 Hierarchien zeitgleich miteinander zu vergleichen. Der Vergleichs einer Menge von 1345 unterschiedlichen Phylogenetischen Bäumen demonstriert dies exemplarisch. Die Basis dieser Bäume bilden die 16S rRNA Sequenzen verschiedener Bakterien, welche mittels des Multiplen Alignierungsalgorithmus ClustalW2 LBB+07 unter Verwendung unterschiedlicher Parametersets aligniert wurde. Die Bäumen wurden anschließend mit dem PhyML GDL+10 Algorithmus erzeugt. Hierarchical Structures are widely used for multiple purposes. One example is the current research in phylogenetics, especially the comparison of large numbers of so called phylogenetic trees. The main target is the discovery of similarities and dissimilarities between those trees. The size, complexity and large amount of those trees makes the comparison task very difficult for the user. Current research challenges are to provide solutions to help the user in performing the comparison task, even with a large amount of trees. The research field Visual Analytics for example provides solutions for these challenges by using different datamining techniques and interactive visualizations. This master-thesis presents a new approach for the visual and interactive comparison of a large set of trees, considering their elements, topology and the parameters used for their calculation. The comparison is done in several steps. In the first step, the trees are hierarchically clustered depending on their similarities. This results in a so called Superhierarchy. The next step is the identification of relevant substructures (groups of similar hierarchies) in this Superhierarchy by using an automatic threshold selection technique. The last step is the selection of a single representative hierarchy for each of the identified relevant substructures. These representatives are chosen on the basis of their similarity to all other hierarchies in the same substructure. One representative is therefore able to replace a whole group of similar hierarchies in the comparison. In this way, the comparison complexity is reduced to a small set of representatives. The comparison task on these sets of representatives is performed by using an existing technique presented by Bremm et al. in BvLH+11. By using these concepts, the user is able to compare more than 1000 trees at once. This is shown in an example comparison of 1344 different phylogenetic trees of the 16S ribosomal RNA from different bacteria, constructed with the ClustalW2 LBB+07 Multiple Alignment algorithm using different sets of parameters and the PhyML GDL+10 algorithm. 2Hierarchical Structures are widely used for multiple purposes. One example is the current research in phylogenetics, especially the comparison of large numbers of so called phylogenetic trees. The main target is the discovery of similarities and dissimilarities between those trees. The size, complexity and large amount of those trees makes the comparison task very difficult for the user. Current research challenges are to provide solutions to help the user in performing the comparison task, even with a large amount of trees. The research field Visual Analytics for example provides solutions for these challenges by using different datamining techniques and interactive visualizations. This master-thesis presents a new approach for the visual and interactive comparison of a large set of trees, considering their elements, topology and the parameters used for their calculation. The comparison is done in several steps. In the first step, the trees are hierarchically clustered depending on their similarities. This results in a so called Superhierarchy. The next step is the identification of relevant substructures (groups of similar hierarchies) in this Superhierarchy by using an automatic threshold selection technique. The last step is the selection of a single representative hierarchy for each of the identified relevant substructures. These representatives are chosen on the basis of their similarity to all other hierarchies in the same substructure. One representative is therefore able to replace a whole group of similar hierarchies in the comparison. In this way, the comparison complexity is reduced to a small set of representatives. The comparison task on these sets of representatives is performed by using an existing technique presented by Bremm et al. in BvLH+11. By using these concepts, the user is able to compare more than 1000 trees at once. This is shown in an example comparison of 1344 different phylogenetic trees of the 16S ribosomal RNA from different bacteria, constructed with the ClustalW2 LBB+07 Multiple Alignment algorithm using different sets of parameters and the PhyML GDL+10 algorithm.

Frage zum Eintrag

Redaktionelle Details anzeigen