Thomas Plehn online

  • Increase font size
  • Default font size
  • Decrease font size

B.Sc.

E-mail Print PDF

(Diese Arbeit darf hier nicht mehr angeboten werden)

(Bachelor of Science)

In meiner Bachelorarbeit ging es um das Thema "longest common subsequence", auch abgekürzt als LCS. Dabei geht es darum, in zwei Zeichenstrings die längste Übereinstimmung zu finden, d.h. die längste übereinstimmende Teilsequenz. Diese Teilsequenz muss allerdings nicht zusammenhängend auftauchen. Dabei können Buchstaben in den beiden Zeichenketten, die eine gemeinsame Teilsequenz haben sollen, ausgelassen werden. Die Reihenfolge muss allerdings eingehalten werden. Man nennt das auch optimal Alignment. Nun sind allerdings die betrachteten Strings der Einfachheit halber nicht aus Buchstaben zusammengesetzt, sondern nur aus den Ziffern 0 und 1, also binär. Man interessiert sich nun dafür, welche Eigenschaften Strings haben, die einer bestimmten Klasse angehören. Diese Klassen werden bestimmt durch die Wahrscheinlichkeit, dass in einem zusammenhängenden Block gleicher Zeichen beim Alignment-Prozess eine Anzahl Zeichen ausgelassen wird. Diese Wahrscheinlichkeiten bilden eine Matrix mit den Einträgen p_i,j wobei i die Anzahl der ausgelassenen Zeichen in einem Block der Länge j darstellt. In einem langen String kann man nun einen Erwartungswert angeben, welcher Anteil der Zeichen insgesamt ausgelassen werden. Dieser Erwartungswert ist abhängig von der Matrix p. Außerdem kann man p als Wahrscheinlichkeitsverteilung deuten und die Entropie berechnen. Man kann auch die Anzahl der Blöcke berechnen, die überhaupt mindestens eine Auslassung besitzen. All dies ist abhängig von der Matrix p. Da p die Struktur der Teilsequenz mehr oder weniger festlegt, kann man nun zahlreiche Rechnungen anstellen, welche Struktur bestimmte Eigenschaften maximiert, unter bestimmten Nebenbedingungen, wie einer festen Anzahl von Auslassungen insgesamt und natürlich immer der Nebenbedingung, dass die Matrix p stochastisch ist. Alle diese Rechnungen benötigen die Lagrange-Multiplikator Regel. Es bleiben jedoch immer bestimmte Parameter im Lagrange-Ansatz offen, die noch zu bestimmen sind. Dies erledigte ich durch selbst erstellte Matlab-Programme und fertigte umfangreiche Zahlentabellen für verschiedenste Fragestellungen an.

Last Updated on Sunday, 03 March 2013 13:23  

Stats

OS : Linux s
PHP : 5.3.3
MySQL : 5.5.54-38.6-log
Time : 14:57
Caching : Disabled
GZIP : Disabled
Members : 2
Content : 10
Web Links : 6
Content View Hits : 12003

Feedback

was ist auf dieser Seite am nützlichsten?