Übung 4 - Universität des Saarlandes

I
Universität des Saarlandes
FR 6.2 Informatik
Prof. Dr. Hans-Peter Lenhof
M. Sc. Tim Kehl
M. Sc. Lara Schneider
M. Sc. Daniel Stöckel
4. Übung zur Bioinformatik I, WS 2015/16
Aufgabe 1: Sequencing by Hybridization (3 + 5 + 2 = 10 Punkte)
Sie haben in der Vorlesung k-Spektren kennengelernt.
(a) Erstellen Sie das 4-Spektrum zu den Fragmenten
F = {GAATTCACG, GTAGAAT, CACGGT, ACGGTTT, ACTGTG, GTGTAGA}.
(b) Zeichnen Sie den De-Bruijn-Graphen zu diesem 4-Spektrum.
Hinweis: Der De-Bruijn-Graphen zu einem k -Spektrum enthält Fragmente der Länge k-1.
(c) Geben Sie einen Euler-Pfad durch den De-Bruijn-Graphen und den daraus resultierenden Text T an.
Aufgabe 2: Hamiltonkreis, Hamiltonpfad (3+7=10 Punkte)
Ein Graph ist Hamiltonian, wenn er einen Hamilton-Kreis enthält. Ein Hamilton-Pfad ist
definiert als ein Pfad, der jeden Knoten im Graphen genau einmal besucht.
(a) Ist der folgende Graph Hamiltonian? Bitte begründen Sie Ihre Antwort.
Bitte geben Sie einen Hamilton-Pfad an.
(a) Petersen
(b) Herschel
2
(c) theta-7
Figure 1.1: Famous graphs with Hamiltonian paths and no Hamiltonian cycles
nian path, and the converse is not true. Figure 1.1 shows three examples of famous
graphs that have Hamiltonian paths but no Hamiltonian cycles.
The rest of this chapter provides a short graph theory background that will be
(b) Ein Turnier-Graph ist ein gerichteter Graph G = (V, E), für den gilt: ∀u, v ∈ V :
(u, v) ∈ E ⊗ (v, u) ∈ E, d.h. zwischen jeden zwei Knoten gibt es genau eine Kante.
Zeigen Sie, dass jeder Turnier-Graph einen Hamilton-Pfad enthält.
Hinweis: Verwenden Sie vollständige Induktion über die Anzahl der Knoten. Wählen Sie im Induktionsschritt zufällig einen Knoten y und betrachten Sie den Restgraphen ohne y und dessen Kanten. Um einen Hamilton-Pfad für den gesamten
Graphen zu konstruieren, muss y unter Verwendung seiner ein- und ausgehenden
Kanten wieder in den Hamilton-Pfad eingefügt werden. Betrachten Sie eine Fallunterscheidung über die möglichen Einfügepositionen.
Aufgabe 3: Needleman-Wunsch-Algorithmus (10 Punkte)
Gegeben sei folgendes Sequenz-Alignment-Problem:
Σ = {A, C, G, T}
s = AT GGC
p = ACGC
Die Bewertungsfunktion D basiert auf folgender Spaltenbewertung d(, ):
A
C
T
G
-
A
3
-1
-1
-1
-2
C
-1
3
-1
-1
-2
T
-1
-1
3
-1
-2
G
-1
-1
-1
3
-2
-2
-2
-2
-2
0
(a) Um welche Art von Bewertungsfunktion handelt es sich bei Verwendung der obigen
Matrix? Begründen Sie Ihre Antwort.
(b) Berechnen Sie unter Verwendung der gegebenen Spaltenbewertungsfunktion die folgende Tabelle mit Hilfe des aus der Vorlesung bekannten Dynamischen–Programmierungs–
Ansatzes:
A
A
C
C
G
G
C C
A
(c) Führen Sie das Backtracking durch die Matrix durch und geben Sie ein mögliches
optimales globales Alignment an.
Hinweis: Geben Sie nicht nur die Ergebnisse, sondern auch die ausgefüllte Matrix mit
eingezeichnetem Backtracking-Pfad an!
Aufgabe 4: Hamiltonkreis und Euler-Rundgang (10 Punkte)
Ein n-dimensionaler, binärer Hyperwürfel Qn ist ein Graph G = (V, E) mit
• V = Vn = {0, 1}n , mit |V | = 2n
• E = {{u, v} ∈ Vn2 | Hamming-Distanz(u, v) = 1}
(a) Für welche n ∈ N besitzt Qn einen Euler-Rundgang? Begründen Sie Ihre Antwort.
(b) Beweisen Sie per vollständiger Induktion:
(i) |E| = n · 2n−1
(ii) Qn besitzt einen Hamiltonkreis für alle n ≥ 2.
Abgabe: Donnerstag, 19.11.2015, 23:59 Uhr

Download Report