In den Unterkapiteln 6.1 und 6.2 werden zwei bioinformatische Anwendungenerklärt, welche sich an [GUS97] orientieren. Anschließend wird in 6.3 das LCA-Problem auf gerichtete azyklische Graphen verallgemeinert und Lösungsansätze sowie weitere Anwendungen skizziert. Die in 6.3 vorgestellten Verfahren basieren auf [BPSS01].

Dieses Unterkapitel beschreibt das Vorgehen zur Ermittlung maximaler Palindrome in einer Zeichenkette T.

Sei Σ ein endliches Alphabet und T = σ₀σ₁...σ_n-1 ∈ Σ⁺ ein Eingabestring. SeiS = T[i,j] = σ_iσ_i+1...σ_j ein Teilstring mit der Länge |S| = j - i + 1. Der umgekehrte Teilstring S^rev ist folglich σ_jσ_j-1...σ_i.

Eine Zeichenkette w ∈ Σ⁺ ist ein Präfix eines Strings T, wenn T = wy für einen String y ∈ Σ^* gilt. Analog ist eine Zeichenkette w ein Suffix eines Strings T, wenn T = yw für einen String y ∈ Σ^* gilt [CLRS01]. Den Suffix T[i,…,n] eines Strings T bezeichnet man als i - ten Suffix von T.

Als wichtige Teilfrage zur Lösung einiger Probleme für Zeichenketten hat sich die Bestimmung von längsten gemeinsamen Ausdehnungen (LCE - longest commonextension) erwiesen.

Das LCE-Problem kann wie folgt definiert werden: Zwei Zeichenketten S₁ und S₂ ∈ Σ⁺ sollen so effizient vorverarbeitet werden, dass LCE(i,j)-Anfragen möglichst schnell beantwortet werden können.

Hinweis: Zu beachten ist hier, dass nicht eine einzelne LCE-Anfrage beantwortet werden soll, sondern viele und diese möglichst effektiv. Eine einzelne LCE-Anfrage könnte durch den trivialen Vergleich, Zeichen für Zeichen, beantwortet werden.

Gegeben seien folgende zwei Strings:

Der LCE(0,2) = 3, da die Zeichen cab übereinstimmen, jedoch nicht die darauf folgenden Zeichen, was in S₁ b und in S₂ dem Ende des Strings entspricht. Weitere Beispiele sind LCE(0,0) = 0, da sich keine gleichen Zeichen an den gegebenen Indexpositionen befinden und der LCE(1,1) = 1.

Der Schlüssel zur effizienten Lösung des LCE-Problems liegt in der Verwendung eines Suffixbaumes als Datenstruktur.

Hinweis: Die Kantenmarkierungen sind durch Verweise auf die Indexpositionen i und j für den Teilstring T[i,j] realisiert.

Dies lässt sich auf den Fall mehrerer Eingabestrings verallgemeinern. In diesem Fall werden die beiden Strings S₁ und S₂ in einen generalisierten Suffixbaum überführt. Ein generalisierter Suffixbaum ist ein gemeinsamer Suffixbaum von mehreren unterschiedlichen Zeichenketten. In den Blättern stehen Tupel der Form (S_x,i), die angeben zu welchem String(S_x) der Suffix gehört und an welcher Stelle i er beginnt.

Satz 3.
Ein generalisierter Suffixbaum für zwei Strings S₁ und S₂ kann in (|S₁| + |S₂|) konstruiert werden. [GUS97]

Zusätzlich werden in jedem Knoten v des Suffixbaumes die Länge der Konkatenation der Kantenlabel von der Wurzel bis v gespeichert. Der gemeinsam generalisierte Suffixbaum wird in der Vorbereitungsphase des Algorithmus erstellt.

Die Grafik 6.1 zeigt ein Beispiel eines gemeinsamen Suffixbaumes für die StringsS₁ = cabbabc und S₂ = aacab.

Abbildung 6.1: Generalisierter Suffixbaum für S₁ und S₂

Nach der linearen Vorverarbeitung des Suffixbaumes für LCA-Anfragen können LCA-Anfragen mit allen Kombinationen aus den Indizes von S₁ und S₂ gestellt werden.

Beobachtung: Der Knoten u, welcher der letzte gemeinsame Vorfahre der beiden Indizes i und j ist, hat den Wert der längsten gemeinsamen Ausdehnung als Markierung gespeichert.

Betrachten wir den Suffix aus S₁ beginnend bei i = 4 und den Suffix aus S₂ beginnend bei j = 3, so speichert der letzte gemeinsame Vorfahre der beiden Blätter den Wert 2, was bedeutet, dass die längste gemeinsame Ausdehnung die Länge 2 hat.

Das Palindrom S = T[i,j] hat die Länge j - i + 1 und den Radius r = ⌊⌋.

Bei Palindromen unterscheiden wir zwischen Palindromen gerader Länge und Palindromen ungerader Länge. Bei einem Palindrom gerader Länge befindet sich die Mitte zwischen zwei Zeichen und bei Palindromen ungerader Länge ist ein Zeichen selbst die Mitte. Den Index vor der Mitte bezeichnen wir mit q.

Betrachten wir den String abaacca so ist der Teilstring aba ein maximales Palindrom genauso wie der String aa, beide haben den Radius r = 1. Der Teilstring cc ist ein Palindrom, jedoch ist dieses nicht maximal, da es um die beiden Zeichen rechts und links davon erweitert werden kann. Wir erhalten dann acca als maximales Palindrom mitr = 2.

Beobachtung: Wir unterscheiden zwischen Palindromen und maximalen Palindromen. Ein String T der Länge n und der Form aa…a hat Palindrome ungerader Länge und Palindrome gerader Länge.

Ein String T der Länge n hat genau n maximale Palindrome ungerader Länge und höchstens n-1 maximale Palindrome gerader Länge, da zwei benachbarte Zeichen nicht zwingend die gleichen sein müssen.

Ein String T hat dem nach (n²) Palindrome, jedoch nur (n) maximale Palindrome.

Das Palindrom-Problem kann wie folgt definiert werden: Sei T ein String der Länge n, gesucht sind alle maximalen Palindrome in T.

Betrachten wir zunächst den Pseudocode für die naive Bestimmung maximaler Palindrome gerader und ungerader Länge.

In diesem Pseudocode wird jedes maximale Palindrom in T mit der Indexposition q, unmittelbar links von der Palindrommitte bei Palindromen gerader Länge und der Mitte bei Palindromen ungerader Länge, und dem Radius r abgespeichert. Die Lösungen werden jeweils in den zwei Arrays Pal_odd und Pal_even gespeichert. Pal_even hat die Größe n - 1 und speichert die Werte für gefundene Palindrome gerader Länge. Gibt es keine Lösung, so wird an dieser Stelle der Wert 0 gespeichert, da es keine Palindrome gerader Länge mit r = 0 gibt. Das Array Pal_odd hat die Größe n und speichert die Werte für gefundene Palindrome ungerader Länge. Der Radius r = 0 bedeutet hier, dass das Palindrom nur aus einem Zeichen besteht. Die Größen der Arrays ergeben sich jeweils aus der oben bestimmten maximalen Anzahl für maximale Palindrome gerader und ungerader Länge.

Eingabe: T 
 int r 
 Array Pal_even [n-1] 
 Array Pal_odd [n] 
 for q = 0 to n - 1 do 
 
   \\Palindrome gerader Länge 
   r=0 
   while ((q-r)=0) and ((q+r+1)<=n-1) do 
     if not (T[q-r]==T[q+r+1]) then 
	   Pal_even[q]=r 
	   break 
	 \\Zeichenvergleich mit ersten bzw. letzten Zeichen von T 
	 if ((q-r)==0 || (q+r)==n-1) then 
	   Pal_even[q]=r+1 
       break 
    r++ 
 
  \\Palindrome ungerader Länge 
  r=0 
  while ((q-r)= 0) and ((q+r+2)<=n-1) do 
    if not (T[q-r]==T[q+r+2]) then 
      Pal_odd[q+1]=r 
	  break 
    \\Zeichenvergleich mit ersten bzw. letzten Zeichen von T 
	if ((q-r)==0 || (q+r+2)==n-1) then 
	  Pal_odd[q+1]=r+1 
	  break 
	r++ 

Die naive Methode hat (n) Anfragen und pro Anfrage maximal Vergleiche, was eine Laufzeit von (n²) ergibt. Die Gesamtlaufzeit zur naiven Bestimmung maximaler Palindrome gerader und ungerader Länge in T beträgt folglich (n²).

Wenden wir uns nun der Bestimmung maximaler Palindrome mittels LCA-Anfragen zu. Die Mitte eines Palindroms gerader Länge befindet sich zwischen den Indizes q und q + 1, sodass die r Zeichen nach links, beziehungsweise nach rechts, gelesen die gleichen sind. Betrachtet man nun S und S^rev, so beginnen die gesuchten r Zeichen in S an der Position q + 1 und in S^rev bei n - q - 2.

In der Vorbereitungsphase des Algorithmus wird in linearer Zeit ein gemeinsamer Suffixbaum für den String S und seine Umkehrung S^rev erstellt. In diesem Suffixbaum kann für jedes q von 0 bis n- 2 eine LCE-Anfrage für das Indexpaar (q + 1,n-q - 2) in S, beziehungsweise S^rev, in konstanter Zeit beantwortet werden. Die LCE-Anfrage gibt für jedes q den Radius des maximalen Palindroms zurück. Mit Hilfe des Radius und q kann auch das Palindrom ermittelt werden.

Palindrome ungerader Länge haben beim Index q + 1 die Mitte und können durch eine leichte Abänderung des Indexpaares ermittelt werden. Das Indexpaar der LCE-Anfrage ist (q + 2,n - q - 2).

Der folgende Pseudocode zeigt die Berechnung maximaler Palindrome mittels LCE-Anfragen. Zur Erstellung und Vorverarbeitung des Suffixbaumes für S und S_rev dient die Methode build_tree(S,S_rev).

Max-Palindrom-LCE: 1:

Eingabe: T 
  int r_gerade=0 
  int r_ungerade=0 
  Array Pal_even [n-1] 
  Array Pal_odd [n] 
 
  build_tree(S,Srev) 
 
  for q = 0 to n - 2 do 
    \\Palindrome gerader Länge 
	r_gerade=LCE(q+1,n-q-2) 
	Pal_even [q+1]=r_gerade 
 
	\\Palindrome ungerader Länge 
	r_ungerade=LCE(q+2,n-q-2) 
	Pal_odd [q+1]=r_ungerade 

Die Laufzeit des gesamten Algorithmus setzt sich aus zwei Teilen zusammen. Das Erstellen des Suffixbaumes für LCA-Anfragen nimmt (n) Zeit in Anspruch. Die Anfragen, welche in konstanter Zeit beantwortet werden können, haben insgesamt eine Laufzeit von (n). Aus den beiden Laufzeiten ergibt sich eine Gesamtlaufzeit von (n). Damit ist der folgende Satz bewiesen:

Satz 5.
Alle maximalen Palindrome in einem String T der Länge n können in (n)ermittelt werden.

• Zusammenfassung
• Einführung
• Grundlagen
• Lösungsansatz RMQ-Problem
• Algorithmus RMQ
• schnellerer Algorithmus
• Anwendungsbeispiele

• Page:
•  1 
•  2 
•  3