Einfuehrung Flashcards
Definition of an algorithm (general)
An algorithm is a precise and finite description of a process consisting of elementary steps
Usually we also want: “and (c) solves a given problem”
– But algorithms can be wrong …
Definition of an algorithm (computer science)
An algorithm is a precise and finite description of a
computational process that is (a) given in a formal
language and (b) consists of elementary and machineexecutable steps
Euclidean Algorithm
Recipe: Given two integers a, b. As long as neither a nor b is 0, take the smaller of both and subtract it from the greater. If this yields 0, return the other number
Euclidean Algorithm - proof ?
- Assume our function “euclid” returns x
- We write “b|a” if (a mod b)=0
– We say: “b teilt a” - We define x|0 for any x
- Note: if c|a and c|b and a>b ⇒ c|(a-b)
- We prove the claim in two steps
– We show that x is a common divisor
– We prove that no greater common divisor
can exis
Algorithm properties
terminating?
An algorithm is called terminating if it stops after a finite number of steps for every finite input.
– We so-far required that the algorithm (specification) is finite; here we require that the time for execution is finit
Algorithm properties
deterministic?
deterministic if it always performs the same series of steps given the same input
Exemplary questions
- Give a definition of the concept “algorithm”
Exemplary questions
- What different types of complexity exist?
Exemplary questions
- Given the following algorithm …, analyze its worst-case
time complexity
Exemplary questions
- The following algorithm … uses a double-linked list as basic
set data structure. Replace this with an arra
Exemplary questions
- When do we say an algorithm is optimal for a given
problem?
Exemplary questions
- How does the complexity of an algorithm depend on (a) the data structures it uses and (b) the complexity of the problem it solves?
What is a data structure
- Algorithms work on input data, generate intermediate data,
and finally produce result data - A data structure is the way how “data” is represented
inside the machine
– In memory or on disc (see Database course) - Data structures determine what algs may do at what cost
– More precisely: … what a specific step of an algorithm costs - Complexity of algorithms is tightly bound to the data
structures they use
– So tightly that one often subsumes both concepts under the term
“algorithm”
Wie wurde die Doppelhelix gefunden?
Biophysikalische Daten
Biophysikalische Daten (Linus Pauling) –
es gibt mehrere Stränge (erste Vermutungen: 3)
Wie wurde die Doppelhelix gefunden?
Roentgenkristallografie
Roentgenkristallografie – helikale Struktur
(Rosalind Franklin)
Wie wurde die Doppelhelix gefunden?
Relative Häufigkeit der Basen
Relative Häufigkeit der Basen: %A=%T, %C=%G
(Erwin Chargaff)
Wie wurde die Doppelhelix gefunden?
Biochemische Modelle
(Watson & Crick 1953)
Das menschliche Genomprojekt
- Erste Vorschläge 1985/6, gestartet 1990
- 1,000 Wissenschaftler in 6 Ländern (inkl Teams in Berlin, Braunschweig, Jena)
– 3 Milliarden US$ - 1999: Chromosom 22, 2000: Chromosom 21
- Erste “Arbeitskopie” aller Chromosome wurde 2001 veröffentlicht
- Gleichzeitig: Sequenzierung durch private Firma (Celera Genomics)
- 2006: letztes Chromosom (1)
Kartierung & Sequenzierung
* Clone-Contig
– Benötigt eine genetische oder physikalische Karte
– Kleinere Bereiche zwischen Markern werden kloniert und sequenziert, dann auf den Chromosomen platziert
Kartierung & Sequenzierung
* “shotgun” sequencing
– Gesamtsequenz wird direkt aus kurzen,
überlapppenden Sequenzen erstellt
– Komplexität wächst quadratisch
– Probleme bei sehr ähnlichen Sequenzen
(repeats)
DNA-Sequenzierung
* Entwickelt in den
70er Jahren
(Sanger/Maxam-Gilbert)
Sanger: Prinzip
Kettentermination
– Prinizip: Länge eines einzelsträngigen DNA-Molekuels lässt sich durch GelElektrophorese ablesen (von ca 10-1500 Basen)
– Eine einzelsträngige DNA wird komplementär synthetisiert
– Ein Teil der verfügbaren einzelnen Basen ist mit Farben markiert (d.h. A,C,G,T mit unterschiedlichen Farben)
– Nach Einbau eines farbigen Nukleotids wird die Reaktion abgebrochen
Einzelzellsequenzierung
Standardsequenziermethoden benötigen große Mengen an DNA (z.T. mehrere Millionen Zellen)
– Problem: begrenztes (Patienten-)Material; Heterogenität
– Zusätzliches Problem: uniforme Amplifizierung des Materials
* Mikrofluidik-Plattformen separieren einzelne Zellen für DNA/RNA-Sequenzierung
– Fluidigm:https://www.youtube.com/watch?v=Yg8yEeKoB2Q
* Erlauben neue Forschungsfragen
– Tumor-Heterogeneität
– Zelltypspezifikation in der Entwicklung Neues internationales Konsortium: Human Cell Atlas
Aktueller Stand: Drop-seq
* Tausende von Zellen, aber:
je mehr Zellen, desto weniger Sequenzen pro Zelle
Das zentrale Dogma der Molekularbiologie
Hauptaussage: Information kann nicht von Protein zu Protein oder zurück zu
DNA/RNA übertragen werden
Führte oft zu einer engen Sichtweise:
– DNA als Informationsträger,
– RNA als Botenstoff,
– Protein als Funktionsträger (“ein Gen, ein Protein”)
