Wochenberichte

Woche 1

• naiven (brute force) Algorithmus zum finden von Palindromen implementiert
• externe inverteted suffix array Struktur implementiert
• isa-Struktur so templatisiert, dass sie für beliebige ESA-Indices funktioniert
• Gusfield-Algorithmus unter Verwendung der LCP-Tabelle implementiert
• Gussfield-Algorithmus unter Verwendung des Top-Down-Ansatzes implementiert

Woche 2

• dritter Ansatz implementiert
• ist wesentlich komplizierter
• Warum sollte hier für ein Bottom-Up-Iterator verwendet werden?
  • scheint nicht sinnvoll, macht aber auch keine Probleme, darum bei behalten
• erster Laufzeittest zeigt, dass die ersten beiden Ansätze für das humane Albumin-Gen doppelt so schnell sind wie der dritte
• Versuche den dritten Ansatz laufzeittechnisch zu optimieren zeigen: Kopieren der Iteratoren verbraucht viel Zeit
• Versuch das Kopieren von Iteratoren zu vermeiden

Woche 3

• Umbau des Out-Parameters auf einen String von "Palindrom-Strukts"
• Optimierung der verwendeten Iteratoren um zu verhindern, dass die "history" des Bottom-Up-Iterators kopiert wird
• Literaturrecherche über Palindrome und ihre biologische Bedeutung

Woche 4

• Implementierung eines Palindrom-Iterators als Spezialisierung des Bottom-Up-Iterators
  • es müssen alle zwischen Variablen (wie weit wurde die Leaf-List schon abgearbeitet, welche Gaplängen wurden schon ausprobiert usw.) im Iterator gespeichert werden
  • goNext setzt den Iterator auf das nächste Palindrom. Es wäre auch möglich goNext nur auf die Knoten zu beziehen und für die einzelnen Palindrome eines Knotens eine andere Funktion zu implementieren
  • die Informationen über das aktuelle Palindrom werden mit verschieden Funktionen vom Iterator erfragt
• Versuch das Finden von Palindromen an gleicher Position mit verschiedenen Gaplängen (zB abccba und ab--ba mit gleich Startposition) zu verhindern

Woche 5

• Problem mit Palindromen an gleicher Position mit verschiedenen Gaplängen lässt sich nicht auf die Schnelle lösen, da die verschiedenen Treffer an verschiedenen Knoten im Suffixtree gefunden werden
• testen der Auswirkungen von maximaler gap-Länge und minimaler Palindromlänge auf die Laufzeit → drei dimensionaler Datensatz
• Suche nach geeigneter graphischer Darstellung für den Datensatz gestaltete sich schwierig

Woche 6

• angefangen die Arbeit zu schreiben
• bemerkt, das ich den Bottom-Up Algorithmus falsch verstanden habe und er deshalb in meiner Implementierung quasi das Gleiche macht wieder Top-Down Ansatz des Gusfield Algorithmus → Neu geschrieben
• Laufzeit verändert sich dadurch nicht signifikant

Comments