Struktur von fastDNAml

  Zunächst wurden nun anhand des reinen Quellcodes die Programmstruktur sowie der Aufbau der Berechnungen rekonstruiert. Bei dieser Untersuchung der ANSI-C-Version des Originalcodes mußte jede einzelne implementierte Prozedur und Routine einzeln untersucht werden, um die Funktionsweise des Programms zu verstehen und die Möglichkeiten zum Ansatz für die Parallelisierung zu erkennen. Die Funktion jeder einzelnen Routine zu beschreiben, würde den Rahmen dieser Arbeit sprengen, denn schon der Ausdruck des Quellcodes umfaßt mehr als sechzig Seiten. Daher wird hier nur der interne Ablauf der Stammbaumrekonstruktion insoweit beschrieben, daß die Eingriffspunkte zur Parallelisierung und deren Folgen dargelegt werden können.

Die durchgeführte Analyse der Programmstruktur ergab folgenden Ablauf einer ,,normalen`` Stammbaumrekonstruktion:

1.

Zuerst wird vom Programm die Anzahl der Spezies und Alignmentspalten sowie alle Optionen und Parameter eingelesen. Anhand dieser Daten werden die notwendigen Speicherbereiche reserviert. Wurden die Basenfrequenzen als Parameter übergeben, werden hier die verschiedenen Frequenzen der einzelnen Basen und Basentypen initialisiert. Anschließend werden noch die Sequenzdaten eingelesen.

2.

Jetzt werden angegebene Kategorien, Gewichte und eventuell zu berechnende Bootstrap-Stichproben für jede Alignmentspalte in ein Gewicht umgerechnet und dieser zugeordnet. Sind die Frequenzen nicht explizit angegeben worden, werden sie jetzt anhand der Sequenzdaten bestimmt.

3.

Jetzt wird die Initialisierung der Baumstrukturen abgeschlossen, soweit nicht schon geschehen.

4.

Das Programm startet nun mit drei Sequenzen und konstruiert hieraus einen einfachen Stammbaum. Dann werden für diesen Stammbaum die Kantenlängen optimiert.

5.

In den im vorhergehenden Schritt gefundenen optimalen ML-Baum wird nun nacheinander an jede Kante die nächste Spezies eingefügt. Jeder so entstandene Baum wird anschließend in Bezug auf seine Kanten optimiert. Am Ende jeder Berechnung wird der neu gefundene Baum mit dem jeweils letzten optimalen Baum dieses Schrittes verglichen und der bessere der beiden gespeichert.

6.

Der gefundene optimale Baum wird in der checkpoint-Datei gespeichert. Enthält dieser Baum weniger als vier Spezies, so fährt das Programm bei Punkt 5. mit der Berechnung fort. In jedem anderen Fall fährt das Programm an Punkt 7. fort.

7.

Mit dem bisher gefundenen besten Baum wird jetzt ein Rearrangement durchgeführt. D.h. nacheinander wird jeder Teilbaum aus dem Baum ausgeschnitten und testweise in alle Nachbarkanten mit der Entfernung eingefügt, die in der Eingabedatei angegeben wurde (Standard ist 1). Für alle diese Bäume werden die Kanten optimiert. Am Ende jeder Berechnung wird der neu gefundene Baum mit dem jeweils letzten optimalen Baum dieses Schrittes verglichen und der bessere der beiden gespeichert.

8.

Wurde im letzten Schritt ein neuer optimaler Baum gefunden, wird dieser in die checkpoint-Datei geschrieben und mit diesem Baum Schritt 7. erneut ausgeführt. Wurde im letzten Schritt kein neuer optimaler Baum gefunden und sind noch nicht alle Spezies im Baum enthalten, so fährt das Programm in Punkt 5. mit den Berechnungen fort. Wurde im letzten Schritt kein neuer optimaler Baum gefunden, aber alle Spezies eingefügt, so wird im nächsten Punkt fortgefahren.

9.

Der im letzten Rearrangement gefundene optimale Baum ist nun der rekonstruierte Baum. Dieser wird, falls nicht anders gewünscht, in der Ausgabedatei und in der treefile-Datei abgespeichert.

10.

Anschließend werden alle reservierten Speicherbereiche wieder freigegeben und das Programm beendet.

Während des gesamten Ablaufs macht das Programm Ausgaben an die Standardausgabe über den Stand der Analyse, die hier nicht weiter spezifiziert wurden.