s
Hauptstudium Vorlesung: Bioinformatik I (WS99/00)
Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität München
Hauptstudium Vorlesung: Bioinformatik I (WS99/00)
- Vorlesung:
- Dr. Rolf Backofen:
Hauptstudium Vorlesung: Bioinformatik, 4-stündig
- Zeit und Ort: Mo 9 - 11, Di 11 - 13, Raum 1.14, Oettingenstr. 67
- Übung:
-
Sebastian Will
- Zeit und Ort der Übung: Mi 17 - 19 Uhr,
Raum 1.27, Oettingenstr. 67
- Vorkenntnisse:
- Gute Erfahrung mit C/C++ oder Java
(Datenstrukturen), Wahrscheinlichkeitslehre.
Grundkenntnisse der Biologie sind hilfreich,
aber nicht unentbehrlich, da biologische Aspekte
in der Vorlesung behandelt werden. Skriptum in englisch.
- Hörerkreis: :
- Studierende im Hauptstudium der Informatik
- Studierende mit Nebenfach Informatik
- Schein:
- Ausreichende Mitarbeit in der
Übung und
Prüfung.
zurück zum Inhaltsverzeichnis dieser Seite
Kurzbeschreibung
Unter dem Begriff Bioinformatik versteht man die Anwendung von
Informatik auf biologischen Fragestellungen. Was uns in
dieser Vorlesung hauptsächlich interessiert ist
die Entwicklung von Algorithmen für die Behandlung
von ungenauen Daten (biologische Daten enthalten immer
Fehler).
Nach einem Überblick über
biologische/chemische Grundlagen der Bioinformatik
werden wir in der Vorlesung zwei Problembreiche der Bioinformatik
näher behandeln. Zum einen handelt es sich um die Datenverarbeitung
genetischer Information mit den dazugehörigen
mathematischen/informatischen Konzepten (dynamisches Programmieren und
Sequenzalignment, physikalische Karte des Genoms und PQ-Bäume,
Wahrscheinlichkeitslehre, Markovprozesse,
mathematische Modellierung der Polymerasekettenreaktion (PCR),
stochastische kontextfreie Grammatiken und Faltung von RNA,
Suffixbäume, Mustererkennung in Nuklein- und Aminosäuresequenzen
mit hidden Markov Models.) Zum zweiten behandeln wir die Problematik
der Vorhersage der dreidimenisionalen Struktur eines Proteins aus
seiner Aminosäurensequenz. Für diese Aufgabe werden Verfahren wie
genetische Algorithmen, Monte Carlo Verfahren und Constraint
Programming eingesetzt. Wir werden einen Überblick über
Proteinstruktureigenschaften geben und verschiedene Algorithmen zur
Bestimmung der Proteinfaltung vorstellen.
zurück zum Inhaltsverzeichnis dieser Seite
In the past, biologists generally grouped
living organisms into two distinct life forms or domains:
-
prokaryotes,
represented by cyanobacteria (blue-green algae)
and common bacteria such as Escherichia coli,
not having a nuclear membrane to separate genomic
DNA from the cytoplasm, and
-
eukaryotes,
represented by unicellular organisms such as the flagellum
Trypanosoma, common brewer's yeast,
and multicellular organisms, all of which have a nuclear membrane.
Methanococcus jannaschii is a
methanogenic archaebacterium, first collected in 1982 by the
Woods Hole submersible Alvin near
white smokers from a hot spot of the sea floor of the Pacific Ocean
at a depth of 2600 meters.
In August 1996, the 1.66 megabase pair genome of
M. jannaschii was published by Bult et al. in Science,
where it was asserted that
more than 56% of its 1738 genes are completely new, unlike any
genes in existent databases.
A small initial portion of the DNA sequence,
consisting of over 1.6 million characters, is given as follows.
TACATTAGTGTTTATTACATTGAGAAACTTTATAATTAAAAAAGATTCATGTAAATTTCT
TATTTGTTTATTTAGAGGTTTTAAATTTAATTTCTAAGGGTTTGCTGGTTTGATTGTTTA
GAATATTTAACTTAATCAAATTATTTGAATTTTTGAAAATTAGGATTAATTAGGTAAGTA
AATAAAATTTCTCTAACAAATAAGTTAAATTTTTAAATTTAAGGAGATAAAAATACTCTG
TTTTATTATGGAAAGAAAGATTTAAATACTAAAGGGTTTATATTATGAAGTAGTTACTTA
CCCTTAGAAAAATATGGTATAGAAAAGCTTAAATATTAAGAGTGATGAAGTATATTATGT
Analysis of the DNA sequence of M. jannaschii
provided solid evidence for a startling hypothesis advanced
two decades earlier by Carl Woese: there is a third domain of life called
Archaea, which is distinct from Prokarya and Eukarya.
How can one determine the (hypothetical)
genes of M. jannaschii
from its 1.66 megabase pair genome? Obviously this must be
done by a computer program, but if the majority of the (hypothetical)
genes in this new life form have no homology to known genes, then how
does the program work?
The TIGR group of Bult et al. used the commercial software
GenMark, which implements a 5-th order Markov model.
We'll study the theory and then implement
Hidden Markov Models (HMM),
currently used in determining genes, intron/exon splice sites,
parts of the genome wrapped around nucleosomes, etc.
Sequence similarity between the new genes
of M. jannaschii and those in existent databases were determined
by programs. How do these programs work?
Computational biology is a new field, rapidly expanding, and concerns
itself with the development of algorithms for
-
sequence analysis and comparison,
-
construction of phylogeny trees,
-
machine learning,
-
simulation,
-
mathematical and statistical analysis.
zurück zum Inhaltsverzeichnis dieser Seite
-
Overview of molecular biology for non-biologists:
nucleic acids, proteins, shotgun sequencing, PCR,
physical maps, double digest problem
-
Some probability theory, Markov chains, Shannon entropy
-
Sequence alignment: Smith-Waterman, global and
local alignment
-
All about Eve, the mitochondrial Eve hypothesis and phylogeny
trees, synteny, clustering methods, maximum likelihood
-
Hidden Markov models and their applications, Baum-Welch (EM)
reparametrization and Baldi-Chauvin gradient descent
-
Combinatorial optimization using Monte Carlo with simulated
annealing, application to the study of optimality of the genetic
code
-
Genetic algorithms, application to protein folding in lattice
models (Unger-Moult)
-
How to compute RNA secondary structure, "neutral networks"
and mathematical evolution theory
-
Computing with biomolecules: Adleman's solution of an NP-complete
problem using oligonucleotides, further results
zurück zum Inhaltsverzeichnis dieser Seite
Bioinformatik Links
Hier sind einige Links für Bioinformatik.
Bioinformatik Bücher
-
Michael Waterman,
Introduction to Computational Biology
,
Chapman & Hall, London, (1995).
Ausgezeichnete Einführung in die Bioinformatik
von einem der Begründer dieses
Forschungsbereich.
Viel Mathematik (Statistik, und Kombinatorik).
Die WWW-Seite für Fehlerkorrekturen ist
Introduction to Computational Biology
.
-
J. Setubal and J. Meidanis,
Introduction to Computational Molecular Biology
,
PWS Publishing Co, (1997).
Wesentlich einfacher als Waterman zu lesen (daher
weniger Stoff). Gesichtspunkt ist (theoretische)
Informatik eher als Statistik.
-
M. Nei,
Molecular Evolutionary Genetics
,
Columbia University Press (1987).
Einführung in Population Genetics, aber
gute Behandlung der statistischen Modellen
für punktweise Mutation im Genom, sowie
der elementaren Methoden für Sequence Alignment
und Stammbaumkonstruktion.
-
J.D. Watson et al.,
Molecular Biology of the Gene
,
3-rd edition, Benjamin/Cummings Publishing Co, (1987).
Einführung in Biologie.
-
J. Brandon und C.Tooze,
Introduction to Protein Structure
,
Garland Pub, NY, (1991).
Ein Forschungsbereich der Bioinformatik
besteht in der 3-dimensionalen Strukturvorhersage
eines Proteins von der Aminosäurenkette.
Informatiker finden die biologische
Grundlagen in diesem Buch.
-
Lewin,
Genes V ,
(oder eine spätere Ausgabe).
Klassisches Text für die Genetik.
zurück zum Inhaltsverzeichnis dieser Seite
Hier sind die Übungsblätter elektronisch
verfügbar.
- Blatt 1:
Wird in der Übung am 17.11.99 besprochen.
- Blatt 2:
Wird in der Übung am 24.11.99 besprochen.
- Blatt 3:
Wird in der Übung am 1.12.99 und 8.12.99 besprochen.
Bitte bis zur Uebung am Mi 8.12.99 abgeben (d.h. bitte bis Di
18.00 per eMail.)
- Lösung: local Alignment a la Needleman-Wunsch in C
- Blatt 4:
Wird in der Übung am 15.12.99 besprochen.
Bitte bis Di vor er Übung 18.00 abgeben. (Abgabe freiwillig)
- Blatt 5:
Wird noch in der Übung am 19.1.2000 besprochen.
Wer will kann das auch noch bis Dienstag 18.1.2000 abgeben.
- Blatt 6:
(Leicht geändert am 20.1.) Wird jetzt in der Übung am
26.1.2000 besprochen. Es gibt
bis dahin KEIN neues Übungsblatt.
- Zur Lösung kann man das Programm phy.c verwenden.
Lösungs-Programme in C++:
- Blatt 7: Wird in der
Übung am 9.2.00 besprochen. Die Abgabe einzelner Aufgaben ist
immer willkommen :-).
zurück zum Inhaltsverzeichnis dieser Seite
Lehr- und Forschungseinheit
Institut
Universität
Rolf Backofen
Last modified: Thu Feb 3 17:36:10 CET 2000