Computational Biology - Lecture 12

Topics:

• Elimination theory
• invariants of algebraic statistical models
• Jukes-Cantor model and phylogenetic invariants.

Computational Biology - Lecture 11

Topics:

• Fully observed tree model
• hidden tree model
• parameter estimation
• Felsenstein algorithm.

Computational Biology - Lecture 9

Topics:

• Gröbner bases: existence, minimal and reduced bases
• Hilbert's Basis Theorem.

Computational Biology - Lecture 8

Topics:

• Monomial orders
• division algorithm in polynomial rings
• Dickson's Lemma
• Gröbner bases.

Computational Biology - Lecture 7

Topics:

• EM algorithm for HMM 
• Polynomial rings and term orders.

Computational Biology - Lecture 6

• Hidden Markov model

• Example: CpG islands.

Computational Biology - Lecture 5

Topics:

• General algebraic statistical models, DiaNA
• maximum likelihood estimation (MLE)
• fully observed toric Markov model
• fully observed Markov model, MLE.

Computational Biology - Lecture 4

Topics:

• Normal cones and normal fans
• pollytope algebra
• Newton polytopes
• polytope propagation 
• finding the optimal alignments for all scores - example

Computational Biology - Lecture 3

Topics - Combinatorial Geometry:

• convex sets and polytopes, affine sets, cones, dimension
• hyperplanes, supporting hyperplanes
• faces, normal cones, and normal fan of polytope.

Computational Biology - Lecture 2

Topics:

• Sum-product decomposition of marginal probability
• Tropicalization of sum-product decomposition
• Needleman-Wunsch algorithm, example.

Computational Biology - Lecture 1

Topics:

• Representation of alignment
• scoring schemes,
• pair hidden Markov model,
• tropicalization of scoring function.

Vorlesung: Computational Biology

Algebraische Methoden

Zeit und Ort:

Donnerstag, 16:00 - 17:30,

Beginn:

27. Oktober 2011 - 2. Vorlesungswoche.

Sprache:

Englisch

Empfohlene Vorkenntnisse:

Grundkenntnisse aus Diskreter Mathematik, Linearer Algebra und Analysis.

Inhalt:

• Algebraische Geometrie (Gröbnerbasen, algebraische Varietäten, Eliminationstheorie)
• Algebro-statistische Modelle (lineare und torische Modelle, Markov-Modelle, Invarianz, statistische Inferenz)
• Anwendungen: Alignment biologischer Sequenzen, Hidden-Markov-Modell.
  

Qualifikationsziele:

• Kenntnisse: Vertiefte Kenntnisse auf einem neuen Gebiet zwischen algebraischer Geometrie und Statistik.
• Fertigkeiten. Theorie geleitetes Anwenden algebro-statistischer Methoden.
• Kompetenzen: Formalisieren von Problemstellungen, Bewerten unterschiedlicher Lösungsansätze, Einsatz von Computeralgebrasystemen.
  

Literatur:

• L. Pachter, B. Sturmfels: Algebraic Statistics for Computational Biology. Cambridge Univ Press, 2004.
  

Studien/Prüfungsleistungen:

Mündliche Prüfung.

ccAlign - Softwarepaket für Sequenzalignment (Studienarbeit)

In der Biologie sind Sequenzalignments von großer Bedeutung. Sie ermöglichen die Untersuchung von Proteinen auf strukturelle, evolutionäre und funktionelle Verwandtschaft und liefern Erkenntnisse, die in verschiedenen Bereichen der Molekularbiologie wie etwa der Klassifizierung von Proteinen oder der Behandlung von auf Proteindefekten basierenden Krankheiten Anwendung finden.

Die Komplexität von Proteinen und die daraus resultierenden Datenmengen motivieren die Verwendung von computergestützten Lösungsverfahren. Die Analyse von Sequenzen ist somit auch eine Disziplin der Bioinformatik, die sich mit der informationstechnischen Verarbeitung von auf Lebenswissenschaften basierenden Daten beschäftigt und für viele der in diesen Bereichen auftretenden Probleme algorithmische Lösungsstrategien formuliert.

Einige dieser Lösungsverfahren sind grundlegende Techniken in der Sequenzanalyse und werden nicht nur in den Grundlagen der Bioinformatik behandelt, sonder auch in der Praxis angewandt: Online-Dienste wie ClustalW oder BLAST sind gängige Plattformen, auf denen diese Alignment-Algorithmen eingesetzt und Anwendern zur Verfügung gestellt werden. Diese Dienste genügen professionellen Ansprüchen und richten sich an versierte Anwender, während sie für die Anwendung im Rahmen des Studiums weniger geeignet sind. Ohne nötige Vorkenntnisse ist eine im biologischen Sinne sachgemäße Bedienung oder die Beurteilung eines Ergebnisses kaum möglich.

Das Ziel der Studienarbeit ist die Entwicklung einer grafischen Benutzeroberfläche für die gegebene Sequenzalignment-Software ccalign. Diese implementiert einige Alignment-Verfahren, die zu den Grundlagen der Bioinformatik gehören. Im Vordergrund der Aufgabenstellung steht die Verbesserung und Erleichterung der Programmbedienung. Ferner soll das als Vorlage dienende Programm um zusätzliche Funktionen ergänzt werden, so dass es für Lehrzwecke geeignet ist und autodidaktischen Ansprüchen gerecht wird. Hilfsfunktionen, die über den Standardumfang von GUI-Funktionen hinausgehen, sollen hinzugefügt werden um Zusammenhänge und Funktionsweisen der einzelnen im Programm implementierten Verfahren zu beschreiben, so dass Anwender das Programm begleitend für Übungen und Klausurvorbereitungen verwenden können.

cand. ing. Mark Schlüter

Computational Biology - Lecture 13

Today, the following topics were on the roster:

• Closure theorem,
• parametric representation,
• implicitization theorem,
• model invariants for algebraic statistical models.

Computational Biology - Lecture 12

Yesterday, we resumed with the introduction into algebraic geometry:

• ideal-variety correspondence,
• elimination theorem,
• extension theorem.

Computational Biology - Lecture 11

Today, we will give an introduction to affine algebraic sets:

• Hilbert's Nullstellensatz (weak and strong version),
• correspondence between affine algebraic sets and ideals.

Computational Biology - Lecture 10

Today, we will finish the topic on Groebner bases:

• Minimal Groebner bases,
• Reduced Groebner bases,
• Buchberger's S-criterion,
• Buchberger's algorithm.

Computational Biology - Lecture 9

Today, the basics of Groebner bases were presented including test of ideal membership, uniqueness of division, existence of Groebner bases, and Hilbert's basis theorem.

Computational Biology - Lecture 8

Today, we will present basics of computational commutative algebra:

• polynomial rings in several unknowns,
• term orders (plex, grlex, grevlex),
• Dickson's Lemma,
• division algorithm.

Computational Biology - Lecture 7

Today, we will consider the expectation-maximization (EM)  algorithm which can be used to provide maximum-likelihood estimates of the parameters in a statistical model with hidden variables, like the hidden Markov model (HMM). As an example, the EM algorithm is going to be applied to the casino model.

Finally, an HMM for CpG islands in human genomes will be discussed.