Interactive Comparison of Multiple Trees

Karin Pfattner, Andrea Diwald

Bäume sind eine viel verwendete Darstellungsform in verschiedenen Bereichen, wie zum Beispiel die stammesgeschichtliche Entwicklung in der Biologie. Diese Darstellungsform hat jedoch den Nachteil, dass man nicht mehrere Bäume miteinander vergleichen kann. Bisherige Ansätze ermöglichen nur einen paarweisen Vergleich. Daher ist die Idee einer neuen interaktiven Visualisierung mehrerer Bäume nahe liegend. Wir gehen von einem Baum aus, dessen Kanten ungerichtet sind. Dieser Baum besitzt einen Knoten als Wurzel. Kanten verbinden zwei Knoten und sind immer eindeutig. Knoten, die keine Kindknoten besitzen, werden als Blätter bezeichnet. Um die Ähnlichkeit zwischen mehreren Bäumen zu analysieren, betrachten wir dessen Elemente:
Element-Basierte Auswertung:
Die innere Struktur des Baumes wird berücksichtigt.

Zur Visualisierung der Ähnlichkeit wird zum einen eine Farbmatrix hergenommen, auf derer beiden Achsen jeweils die Bäume eingetragen sind. Der Farbwert codiert jeweils die Ähnlichkeit. Die Bäume werden hier paarweise verglichen. Weiters kann die Verteilung der Messwerte als Histogrammmatrix dargestellt werden.
Unsere Farbcodierung ist farbenblindgerecht. Blau steht für einen hohen Score (Hohe Ähnlichkeit), Gelb für einen niedriegen Score.
Zudem stehen noch zwei weitere Ansichten zur Verfügung: Die Baumübereinstimmungsansicht liefert einen 1:n Vergleich, bei dem der Benutzter auch Unterbäume selektieren kann. Als letzte Ansicht ist es möglich zwei bestimmte Bäume verglichen mit dem Consensus Baum in einem Vergleichsbaum zu betrachten.

Implementierung: Unsere GUI Elemente sind mit SWT aufgebaut. Gezeichnet werden die Elemente mit Canvas. Bäume werden aus Textdateien eingelesen und müssen die folgende Form haben: 
[node1][node2][node3][node1; node2][node1; node2; node3]
Ein Baum besteht aus Elementen, die mit [] gekennzeichnet werden. Strichpunkte trennen die einzelnen Knoten, die durch Zeichen dargestellt werden.
Bäume und deren Elemente werden in mehreren verschachtelten ArrayLists gespeichert.

Quickstart
  1. exetree.jar starten
  2. Klicken auf Datei-> Lade Daten Binärer Bäume (STRG+O)
  3. Matrix wurde geladen, ein Feld auf der Matrix auswählen
  4. Histogramme und ConsensusBaum sind geladen. Histogramm auswählen für Vergleichsbaumansicht.
  5. Vergleichsbaumansicht ist geladen. Um Knoten zu markieren, einfach länger mit der Maus drüber fahren. Zum Demarkieren einfach aus dem Sub-Fenster hinaus fahren.


Downloads
Visualiserung 2 2012