61
Ingo Rechenberg PowerPoint-Folien zur 5. Vorlesung „Bionik II / Biosensorik“ Das molekulare Schlüssel-Schloss-Prinzip Die universelle Technologie des Lebens Weiterverwendung nur unter Angabe der Quelle gestattet

Ingo Rechenberg

  • Upload
    hye

  • View
    27

  • Download
    3

Embed Size (px)

DESCRIPTION

Ingo Rechenberg. PowerPoint-Folien zur 5. Vorlesung „Bionik II / Biosensorik“. Das molekulare Schlüssel-Schloss-Prinzip Die universelle Technologie des Lebens. Weiterverwendung nur unter Angabe der Quelle gestattet. Schlüssel / Schloss in der Technik. - PowerPoint PPT Presentation

Citation preview

Page 1: Ingo Rechenberg

Ingo Rechenberg

PowerPoint-Folien zur 5. Vorlesung „Bionik II / Biosensorik“

Das molekulare Schlüssel-Schloss-Prinzip

Die universelle Technologie des Lebens

Weiterverwendung nur unter Angabe der Quelle gestattet

Page 2: Ingo Rechenberg

Schlüssel / Schloss in der Technik

Page 3: Ingo Rechenberg

Schlüssel / Schloss in der BiologiePepsinPepsinogen

Komplex aus 44 Aminosäuren

pH < 5pH > 5 !

Verdauungsenzym

aktivinaktiv !

Magensäure pH = 2

Schloss Schlüssel

aufgeschlossenzugeschlossen

Page 4: Ingo Rechenberg

Wie stellt die Natur ihre

Schlüssel-Schloss-Moleküle her ?

Page 5: Ingo Rechenberg

Konstruktionszeichnung – Gestern

Page 6: Ingo Rechenberg

Realisation – Gestern

Page 7: Ingo Rechenberg

Konstruktionszeichnung – Heute

0100011011110010110010111100101011 . ..

Page 8: Ingo Rechenberg

Realisation – Heute

Page 9: Ingo Rechenberg

Konstruktionszeichnung – Realisation In der Biologie

Desoxyribonukleinsäure (DNA-Doppelhelix)

Protein (Aminosäurekette)

Page 10: Ingo Rechenberg

Nukleotidbasen

Adenin

Thymin

Guanin

Cytosin

A

T

G

C

Bausteine für die „Konstruktionszeichnung“

Aminosäuren

PhenylalaninLeucinIsoleucinMethioninValinSerinProlinThreoninAlaninTyrosinHistidinGlutaminAsparaginLysinAsparaginsäureGlutaminsäureCysteinTryptophanArgininGlycin

PheLeuIleMetValSerProThrAlaTyrHisGlnAsnLysAspGluCysTryArgGly

TTT TTCCTT CTCATT ATC ATA...

Bausteine für die Realisierung

Page 11: Ingo Rechenberg

Schlüssel-Schloss-Prinzip – Basenpaarung

Page 12: Ingo Rechenberg

TTTTTCTTATTGCTTCTCCTACTG

ATTATCATAATGGTTGTCGTAGTG

TCTTCCTCATCG

TATTACTAATAG

TGTTGCTGATGG

TCAGTCAGTCAG

TCAG

CGTCGCCGACGGAGTAGCAGAAGGGGTGGCGGAGGG

CATCACCAACAGAATAACAAAAAGGATGACGAAGAG

CCTCCCCCACCGACTACCACAACGGCTGCCGCAGCG

Phe

Leu

Gln

His

Tyr Cys

Trp

Arg

Ser

Ser

Arg

Gly

Asn

Lys

Asp

Glu

Pro

Thr

Ala

Leu

Ile

Val

Metstart

StoppStopp

C

A

T

G

T C A G

1. N

ukle

otid

base

2. Nukleotidbase

3. N

ukle

otid

base

T=Thymin

A=Adenin

G=Guanin

C=Cytosin

Der Genetische DNA-Code

Page 13: Ingo Rechenberg

Ribosom

DNA

m RNA

t RNA

Thr

Ala Gly

ValArg

Ser LeuHis

Ser Leu Thr

Ser Leu

Realisierung der genetischen Information

Thr

Aminoacyl t-RNA

Synthetase

Bei der RNA ist Thymin durch Uracyl ersetzt

Montageplattform

Page 14: Ingo Rechenberg

Phenylalanin t-RNA

AAG

Akzeptor für Aminosäure

Page 15: Ingo Rechenberg

P A

Aminosäure und ATP docken anVa l

Aminosäure

A

ATP Aminoacyl t-RNA Synthetase

ATP gibt zwei Phosphatgruppen abund verbindet sich mit der Aminosäure

ValVal

t-RNA dockt an AMP wird frei

unbeladene t-RNA

Beladene t-RNA wird freigegeben

Enzym kehrt in den Originalzustand zurück

P A

Page 16: Ingo Rechenberg

Die Form und damit die Funktion der Aminoacyl t-RNA Synthetase

entsteht durch die Aneinanderreihung der „richtigen“ Aminosäuren

Die Form und damit die Funktion eines jeden Enzyms

entsteht durch die Aneinanderreihung der „richtigen“ Aminosäuren

!

Page 17: Ingo Rechenberg

Technisches Formgebungsproblem „Zahnrad“

Durch die Aneinanderreihung der „richtigen“ Längen und Winkel eines Polygonzuges entsteht ein Zahnrad.

Page 18: Ingo Rechenberg

Man stelle sich die 20 Aminosäuren als 20 verschiedene Winkelstücke vor, die zu einer Gelenkkette aneinandergekoppelt werden können.

A20

A19

Page 19: Ingo Rechenberg

A20A19

A19

Aufbau einer Gelenkkette mit Rechteckaussparung

Signalmolekül

A8-A11-A17-A19-A19-A8-A18-A7-A15-A18-A7-A14-A16-A10-A20-A17-A9-A5-A8-A2

Page 20: Ingo Rechenberg

Proteinfaltung

Zahnradfertigung

Technisches Formgebungsproblem und biologisches Formgebungsproblem

Page 21: Ingo Rechenberg

Mit DNA Rechnen

Page 22: Ingo Rechenberg

Start Ziel

Der HAMILTON-Weg

Vom Start zum Ziel darf jeder Knoten des Graphen nur einmal durchlaufen werden.

ADLEMANs Experiment mit seinem TT-100

Lenonard M. Adleman

William Rowan Hamilton(1805 - 1865)

Page 23: Ingo Rechenberg

Start Ziel

Die Lösung

1

2

3

4

5

67

Page 24: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 25: Ingo Rechenberg

Biochemische Grundoperationen für „DNA - Computing“

Allgemein

1. Kettenverlängerung 2. Kettenverkürzung 3. Kettenverbindung 4. Kettenauftrennung 5. Kettenreplikation 6. Basen-Substitution

Speziell

1. Polymerase-Kettenreaktion 2. Gel-Elektrophorese 3. Affinitäts-Separation

Page 26: Ingo Rechenberg

Städ

te-C

ode

Verb

indu

ngsm

olek

üle

Celle

Aalen

Trier

Gotha

Basismoleküle

Ziel

Start

Page 27: Ingo Rechenberg

Trier Gotha

Gotha Aalen

Page 28: Ingo Rechenberg

Die Basis-DNA-Se-quenzen kommen in das Reaktionsgefäß

Enzym

Page 29: Ingo Rechenberg

2

1

3

5

Kettenbildungen

4!

Zur Strategie

Page 30: Ingo Rechenberg

Polymerase-Ketten-Reaktion Polymerase Chain Reaction (PCR)

DNA-Vermehrung durch ein flankierendes Oligonukleotid (Primer)

Erhitzen auf knapp 100° C

Enzym Polymerase

Zur Strategie

Page 31: Ingo Rechenberg

Polymerase-Ketten-Reaktion Polymerase Chain Reaction (PCR)

DNA-Vermehrung durch zwei flankierende Oligonukleotide (Primer)

Erhitzen auf knapp 100° C

Page 32: Ingo Rechenberg

Polymerase-Ketten-Reaktion Polymerase Chain Reaction (PCR)

Aalen

Zur Strategie

DNA-Vermehrung durch zwei flankierende Oligonukleotide (Primer)

Page 33: Ingo Rechenberg

Gel-ElektrophoreseD

NA

-Pro

be

Anode

Kathode

Langes FragmentKurzer Weg

Kurzes FragmentLanger Weg

Zur Strategie

Page 34: Ingo Rechenberg

4

5

AffinitätsselektionZur Strategie

Page 35: Ingo Rechenberg

5

Affinitätssektion

4

Eisen

Zur Strategie

Page 36: Ingo Rechenberg

ADLEMANs Experiment hat 7 Tage gedauert

Zur Strategie

Page 37: Ingo Rechenberg

• Input input(tube t) Input definiert eine Eingabe, mit der im Folgenden gearbeitet werden kann.

• Detect detect(tube t) Detect testet, ob in einer Lösung noch DNA-Moleküe vorhanden sind und liefert True bzw. False zurück. Damit entspricht Detect der kombinierten Anwendung von PCR und Elektrophorese.

• Amplify amplify(tube t) to (tube t1) and (tube t2) Die Amplify Operation erzeugt zwei Kopien einer Lösung und entspricht damit reiner Anwendung der PCR.

• Merge merge(tube t1, tube t2) Merge liefert die Vereinigung zweier Mengen zurück, entspricht damit dem Vermischen zweier Lösungen.

• Seperate +(tube t, word w) Die normale Plus-Seperate Operation liefert all die Wörter aus der Menge t zurück, die den Teilstring w enthalten. Es entspricht dem Filtern einer Lösung mittels magnetischer Partikel. −(tube t, word w) Das Minus-Seperate arbeitet analog und liefert all die Wörter, die nicht den Teilstring w enthalten. L(tube t, int n) L-Seperate liefert alle Wörter zurück, die kürzer als der Parameter n sind. Das entspricht der Auftrennung nach Länge mittels Gelelektrophorese. B(tube t, word w) Das B liefert alle Wörter zurück, die mit w beginnen. E(tube t, word w) Analog liefert E alle Wörter zurück, die auf w enden. Beiden entspricht PCR mit den jeweiligen Primern.

Programmiersprache für DNA-Computing

http://www.marinero.de/bioinformatics/dnacomputing.pdfQuelle: Ralf Eggeling DNA computing

Page 38: Ingo Rechenberg

Beispiel 1:

(1) input(N)(2) N = +(N0,A0)(3) N = +(N0,G0)(4) detect(N)

Beispiel 2:

(1) input(N)(2) amplify(N) to N1 and N2(3) NA = +(N01,A0)(4) NG = +(N02,G0)(5) N0A = −(NA,0 G0)(6) N0G = −(NG,0 A0)(7) N = merge(N0A ,N0G)

Beispiel 3:

(1) input(N)(2) N = B(N, s0)(3) N = E(N, s6)(4) N = L(N, 140)(5) for(i = 1; i < 6; i++) {N = +(N, si)}(6) detect(N)

Das einfache Beispiel 1 liefert all die Wörter aus der Eingabemenge zurück, die sowohl A als auch G enthalten.

Der Algorithmus in Beispiel 2 realisiert ein ausschließendes Oder. Er liefert alleWörter zurück, die entweder ein A oder aber ein G enthalten, aber nicht beides.Beispiel 3 ist eine formale Schreibweise von Adlemans Experiment.

http://www.marinero.de/bioinformatics/dnacomputing.pdfQuelle: Ralf Eggeling DNA computing

Programm-Beispiele

Page 39: Ingo Rechenberg

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

x y z 1 0 0

0 0 0

1 0 1

0 0 1

1 1 0

0 1 0

1 1 1

0 1 1

1 0 1

1 1 1

0 0 00 0 10 1 00 1 11 0 11 1 1

extrahiere x=0

0 0 0

1 0 11 1 1

0 0 10 1 00 1 1

0 0 00 0 1

1 0 11 1 10 0 00 0 1

1 0 10 0 00 0 1

1 1 1 0 0 0

0 0 01 1 1

extrahiere z=1

extrahiere z=0

extrahiere x=1

extrahiere y=0

extrahiere y=1

kombiniere x=0 z=1

kombiniere x=1 y=0

kombiniere y=1 z=0

Lösung

SAT-Problem

Erfüllbarkeitsproblem (Satisfiability Problem)

Für welche Werte x, y, z ist die Aussage wahr ?

1

2

31 2 3

Beispiel für eine „tube separation“

Page 40: Ingo Rechenberg

Logische Funktion

00

01

1110

a b a v b

0

11

1

00

01

1110

v

b a b

0

00

1

a

01

a ¬ a

10

„oder“ „und“ „nicht“

Für welche Werte x, y, z ist die Aussage wahr (=1) ?Erfüllbarkeitsproblem

Page 41: Ingo Rechenberg

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

x y z 1 0 0

0 0 0

1 0 1

0 0 1

1 1 0

0 1 0

1 1 1

0 1 1

1 0 1

1 1 1

0 0 00 0 10 1 00 1 11 0 11 1 1

extrahiere x=0

0 0 0

1 0 11 1 1

0 0 10 1 00 1 1

0 0 00 0 1

1 0 11 1 10 0 00 0 1

1 0 10 0 00 0 1

1 1 1 0 0 0

0 0 01 1 1

extrahiere z=1

extrahiere z=0

extrahiere x=1

extrahiere y=0

extrahiere y=1

kombiniere x=0 z=1

kombiniere x=1 y=0

kombiniere y=1 z=0

Lösung

SAT-Problem

Erfüllbarkeitsproblem (Satisfiability Problem)

Für welche Werte x, y, z ist die Aussage wahr ?

1

2

31 2 3

Beispiel für eine „tube separation“

Page 42: Ingo Rechenberg

Informations- verarbeitung

ElektrischeImpulse

ElektrischeImpulse

Informations- verarbeitung

Molekül-Strukturen

Molekül-Strukturen

ElektronischeInformationsverarbeitung

MolekulareInformationsverarbeitung

Page 43: Ingo Rechenberg

Warum DNA-C omputing ?

PC (1G Hz): 10 Operationen/sec

Super-PC : 10 Operationen/sec 12

9

DNA: 10 Operationen/sec 20

G esc hw indigkeit

E ffi zienz

7

10

10

Page 44: Ingo Rechenberg

Kilobyte (kB) 103 Byte = 1.000 Byte

Megabyte (MB) 106 Byte = 1.000.000 Byte

Gigabyte (GB) 109 Byte = 1.000.000.000 Byte

Terabyte (TB) 1012 Byte = 1.000.000.000.000 Byte

Petabyte (PB) 1015 Byte = 1.000.000.000.000.000 Byte

Exabyte (EB) 1018 Byte = 1.000.000.000.000.000.000 Byte

Zettabyte (ZB) 1021 Byte = 1.000.000.000.000.000.000.000 Byte

Yottabyte (YB) 1024 Byte = 1.000.000.000.000.000.000.000.000 Byte

Die Organisation und Komplexität aller Lebewesen basiert auf einer Codierung mit vier verschiedenen Basen im DNA-Molekül. Dadurch stellt die DNA ein Medium dar, welches für die Datenverarbeitung perfekt geeignet ist. Nach verschiedenen Berechnungen würde ein DNA-Computer mit einer Flüssigkeitsmenge von einem Liter und darin enthaltenen sechs Gramm DNA eine theoretische Speicherkapazität von 3072 Exabyte ergeben. Auch die theoretisch erreichbare Geschwindigkeit wegen der massiven Parallelität der Berechnungen wäre enorm. Pro Sekunde ergeben sich etwa 1 Million Tera-Operationen, während die leistungsfähigsten Computer heute gerade mal eine Tera-Operation pro Sekunde erreichen.

Page 45: Ingo Rechenberg

Biochip

oder Schlüssel-Schloss-Array

Bis zu 100 000 verschiedene Gruppen von Negativ-Molekülen auf Unterlage fixiert.

Markierte Positiv-Moleküle

Je 10 Mill. Moleküle

Page 46: Ingo Rechenberg

Der DNA Chip

Page 47: Ingo Rechenberg

Glas-Objektträger mit Mikroarray:

Messpunkte (Spots) mit individuellen

einzelsträngigen DNA-Stücken bekannter Sequenz

DNA-Chip auf Oligonukleotid-Basis

1

Page 48: Ingo Rechenberg

Hybridisierung:

Unbekannte DNA-Probe

Kontroll-DNA

DNA-Chip auf Oligonukleotid-Basis

2 Fluoreszenzmarkierung

Page 49: Ingo Rechenberg

Waschen:

Falsch gepaarte DNA-Stränge

werden herausgewaschen

DNA-Chip auf Oligonukleotid-Basis

3

Page 50: Ingo Rechenberg

Laserkamera: Orange Mischfarbe,

wenn Kontroll- und Probe-DNA iden-

tisch, sonst rote oder grüne Spots

DNA-Chip auf Oligonukleotid-Basis

4

Page 51: Ingo Rechenberg

Auswertung:

Auswertung der Spotfarben mit

Hilfe eines Computers

DNA-Chip auf Oligonukleotid-Basis

5

Page 52: Ingo Rechenberg

Auslesen eines DNA-Chips

Page 53: Ingo Rechenberg

Ende

www.bionik.tu-berlin.de

Page 54: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 55: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 56: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 57: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 58: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 59: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 60: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !

Page 61: Ingo Rechenberg

Strategie zur Konstruktion eines HAMILTONschen Weges

Gegeben sei ein Graph mit n Knoten:

1. Erzeuge eine Menge zufällig bestimmter Wege durch den Graphen.

2. Für alle Wege in dieser Menge:

a) Überprüfe, ob der Weg mit dem Startknoten beginnt und mit dem Zielknoten endet. Falls nicht, entferne den Weg aus der Menge.

b) Überprüfe, ob der Weg genau n Knoten enthält. Falls nicht, entferne den Weg aus der Menge.

c) Überprüfe, ob außer Start- und Zielknoten auch jeder andere Knoten des Gra- phen im Weg enthalten ist. Falls nicht, entferne den Weg aus der Menge.

3. Wenn die Menge nicht leer ist melde, dass ein HA M I LTON-Weg existiert; wenn sie leer ist melde, dass es keinen gibt !