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”)
Menschen wie viele tRNA Gene?
500 tRNA-Gene
Identifikation protein-codierender Gene
- Erste Analysen des menschlichen Genoms
konzentrierten sich auf die Identifikation von
Proteinen durch
– Vorhersage von codierenden Bereichen anhand
der Triplettfrequenzen (“Leserahmen”)
– Vergleichende Genomik (Konservierung)
– Transkribierte Bereiche (detektierte RNAs) - 2001 initial draft
– 26,588 + ~12,000 Gene (Celera)
– 30,000 - 40,000 (International Consortium)
Alternatives Spleissen
Alternative splicing, or alternative RNA splicing, or differential splicing, is an alternative splicing process during gene expression that allows a single gene to code for multiple proteins. In this process, particular exons of a gene may be included within or excluded from the final, processed messenger RNA (mRNA) produced from that gene.[1] This means the exons are joined in different combinations, leading to different (alternative) mRNA strands. Consequently, the proteins translated from alternatively spliced mRNAs usually contain differences in their amino acid sequence and, often, in their biological functions
Das menschliche Genome enthält ? Gene
Das menschliche Genome enthält ~21,000 Gene
