Algorithmen für die Molekulare Biologie
Haupt-/Oberseminar, WS 1998/99
Martin Middendorf
Termin:
Do. 10.00 - 12.00 Uhr, GB IV/318
Beginn: 15.10.98
Viele Fragestellungen im Bereich der Molekularen Biologie lassen sich nur mit Hilfe von Rechnern erfolgreich bearbeiten. Die Komplexität der dabei zu lösenden Probleme erfordert den Einsatz effizienter Algorithmen. In diesem Seminar werden Algorithmen aus mehreren aktuellen Problemfeldern vorgestellt. Dabei geht es um Fragen des Ablaufs der Evolution, der Aufklärung von Verwandtschaftsbeziehungen, der Analyse der Erbinformation und der Ermittlung der Struktur von Eiweißstoffen. Zu Beginn des Seminars wird eine Einführung in das Themengebiet gegeben.

Folgende Themen stehen zur Auswahl (kann noch ergänzt werden):

Phylogenetic Trees:

  1. M.-Y. Kao: Tree contractions and evolutionary trees. SIAM J. Comput., 6 (1998) 1592-1616
  2. A. Amir, D. Keselmann: Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms. SIAM J. Comput., 26 (1997) 1656-1669
  3. L. A. Goldberg, P. W. Goldberg, C. A. Phillips, G. B. Sorkin: Constructing Computer Virus Phylogenies. J. Alg., 26 (1998) 188-208
  4. S. Kannan, T. Warnow: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM J. Comput., 26 (1997) 1749-1763

Tree Alignment:

  1. B. Schwikowsky, M. Vingron: The deferred path heuristic for the generalized tree alignment problem. J. Comp. Biol., 4 (1997) 415-
  2. L. Wang, T. Jiang, E. L. Lawler: Approximation algorithms for tree alignment with a given phylogeny. Algorithmica, 16 (1996) 302-315 (s. auch L. Wang, D. Gusfield: Improved algorithms for tree alignment. J. Alg., 25 (1997) 255-273)

Genome Rearrangement:

  1. V. Bafna, P. A. Pevzner: Sorting by transpositions. SIAM J. Disc. Math., 11 (1998) 224-240

Physical Mapping:

  1. P. A. Pevzner: DNA Physical mapping and alternating eulerian cycles in colored graphs. Algorithmica, 13 91995) 77-105
  2. T. Jiang, R. M. Karp: Mapping clones with a given ordering or interleaving. Algorithmica, 21 (1998) 262-284

Protein Folding:

  1. W. E. Hart, S. Istrail: Fast protein folding in the hydrophobic-hydrophylic model within three-eights of optimal. Erscheint in J. Comp. Biol.