Kombinatorische Herausforderungen der Algorithmischen Biologie |
Dieses Seminar richtet sich nicht nur an Bioinformatik-Studierende, sondern auch an Studierende der Informatik und Mathematik mit Interesse an algorithmischen, durch die Biologie motivierten Fragestellungen.
| Termin | Thema (und Quellen) | Referent/in | |
|---|---|---|---|
| Phylogenetic trees/Comparative Genomics/Genome Rearrangements | |||
| Fr, 11.01.02, 15-16 Uhr |
Building phylogenetic trees from quartets V. Berry, O. Gascuel: Inferring Evolutionary Trees with Strong Combinatorial Evidence. Theoretical Computer Science, 240(2), p. 271-298. 2000. B. Chor. From Quartets to Phylogenetic Trees. SOFSEM 1998, p. 36-53. K. Strimmer, A. von Haeseler. Quartet puzzling: a quartet maximum likelihood method for reconstructing tree topologies. Mol. Biol. Evol. 13: 964-969. 1996. | Andreas Bernauer (JG) | |
| Fr, 11.01.02, 16-17 Uhr |
Sorting by reversals A. Bergeron. A Very Elementary Presentation of the Hannenhalli-Pevzner Theory. CPM 2001. S. Hannenhalli and P. Pevzner. Transforming Cabbage into Turnip (polynomial algorithm for sorting signed permutations by reversals). Journal of the ACM, 46(1):1-27, 1999. H. Kaplan, R. Shamir, R. E. Tarjan. Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals. SIAM Journal on Computing 29 (3) 880--892. 1999. | Daniel Richter (JA) | |
| Do, 17.01.02, 11-12 Uhr |
Evolutionary Puzzles M. Blanchette. Evolutionary Puzzles: An introduction to genome rearrangement. Computational Science, LNCS 2074, p. 1003-1011. 2001 D. Sankoff, M. Blanchette. Multiple genome rearrangement and breakpoint phylogeny. Journal of Computational Biology 5, 555-570. 1998. D. Sankoff et al. Chloroplast Gene Order and the Divergence of Plants and Algae, from Normalized Number of Induced Breakpoints. In Sankoff/Nadeau (Eds.): Comparative Genomics, p. 89-98. Kluwer 2000. | Jan Brücker (RN) | |
| Do, 17.01.02, 12-13 Uhr |
Syntenic Distance D. Liben-Nowell. On the Structure of Syntenic Distance. Journal of Computational Biology, Vol. 8(1), p. 53-67, 2001. J. Kleinberg, D. Liben-Nowell. The Syntenic Diameter of the Space of N-Chromosome Genomes. In Sankoff/Nadeau (Eds.): Comparative Genomics, p. 185-198. Kluwer 2000. DasGupta et al. On the complexity and approximation of syntenic distance. Discrete Applied Mathematics 88(1-3), p. 59-82, 1998. | Joffrey Fitz (RN) | |
| Sequence analysis | |||
| Mo, 21.01.02, 14-15 Uhr |
Searching for motifs I M. Blanchette: Algorithms for phylogenetic footprinting. RECOMB 2001, p. 49-58. M. Blanchette, B. Schwikowski, M. Tompa: An Exact Algorithm to Identify Motifs in Orthologous Sequences from Multiple Species. ISMB 2000, p. 37-45. | Christiane Nerz (RN) | |
| --- |
Searching for motifs II M.-F. Sagot, Y. Wakabayashi: Pattern inference under many guises. Fortaleza Summer School on Algorithms and Combinatorics, LNCS, 2001. | entfallen | |
| Physical Mapping | |||
| Fr, 25.01.02, 15-16 Uhr |
Interval graphs H. Kaplan, R. Shamir. Bounded Degree Interval Sandwich Problems. Algorithmica 24 (2) 96--104. 1999. H. Kaplan, R. Shamir, R.E. Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing, Vol. 28, No. 5, p. 1906-1922. 1999. A. Natazon, R. Shamir, R. Sharan. A polynomial approximation algorithm for the minimum fill-in problem. SIAM Journal on Computing, Vol. 30, No. 4, p. 1067-1079. 2000. | Frederic Dorn (JA) | |
| Fr, 25.01.02, 16-17 Uhr |
Physical Mapping Problems T. Jiang, R.M. Karp. Mapping Clones with a given ordering or interleaving. Algorithmica, Vol. 21, p. 262-284. 1998. J. Redstone, W.L. Ruzzo. Algorithms for a simple point placement problem. CIAC 2000, p. 32-43. | Christian Müller (JG) | |
| Protein and RNA Structure | |||
| Do, 31.01.02, 11-12 Uhr |
Similarity of protein structures D. Goldman, S. Istrail, C. H. Papadimitriou. Algorithmic Aspects of Protein Structure Similarity. FOCS 1999, p. 512-521. G. Lancia, B. Carr, B. Walenz and S. Istrail. 101 Optimal PDB Structure Alignments: A Branch-and-Cut Algorithm for the Maximum Contact Map Overlap Problem. RECOMB 2001, p. 193-202. I. Eidhammer, I. Jonassen, W. R. Taylor. Structure Comparison and Structure Patterns. Journal of Computational Biology 7, 685-716 (2000). | Volker Mosthaf (RN) | |
| Do, 31.01.02, 12-13 Uhr |
Similarity of RNA structures P. A. Evans. Finding common subsequences with arcs and pseudoknots. CPM 1999, p. 271-280. P.A. Evans, H.T. Wareham. Exact Algorithms for Computing Pairwise Alignments and 3-Medians from Structure-Annotated Sequences. PSB 2001, p. 559-570. 2001. G.-H. Lin, Z.-Z. Chen, T. Jiang, J. Wen. The longest common subsequence problem for sequences with nested arc annotations. ICALP 2001, p. 444-455. | Alexander Breit (JA) | |
| Sequence Assembly | |||
| Mo, 4.02.02, 13-14 Uhr |
Assembly in sequencing the human genome I - The Human Gemone Project W.J. Kent, D. Haussler. GigAssembler: An Algorithm for the Initial Assembly of the Human Genome Working Draft. Technical Report, UCSC-CRL-00-17, December 27, 2000. | Kristina Hug (JG) | |
| Mo, 4.02.02, 14-15 Uhr |
Assembly in sequencing the human genome II - Celera D.H. Huson, K. Reinert, G. Myers. The Greedy Path-Merging Algorithm for Sequence Assembly. RECOMB 2001. G. Myers. Comparing sequence scaffolds. RECOMB 2001. | Bernd Hofmann (JG) | |