Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München

Hauptseminar im WS1999/2000
Algorithmen für die Bioinformatik
Themenliste

1. Sequence Alignment

• Vortrag: Dynamic Programming
  Literatur:
  1. E.W. Myers: An Overview of Sequence Comparison Algorithms in Molecular Biology, Technical Report TR91-29, Department of Computer Science, University of Arizona, 1991.
  2. W. Miller, E.W. Myers: Sequence Comparison with Concave Weighting Functions, Bulletin of Mathematical Biology 50(2):97-120, 1988.
  3. E.W. Myers, W. Miller: Optimal Alignments in Linear Space, CABIOS 4(1):11-17, 1988.
  4. S. Wu, E.W. Myers, U. Manber, W. Miller: An O(NP) Sequence Comparison Algorithm, Information Processing Letters 35(6):317-323, 1990.
• Vortrag: Multiple Sequence Alignment
  Literatur:
  1. D. Gusfield: Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds, Bulletin of Mathematical Biology 55(1):141-154, 1993.
  2. V. Bafna, E.L. Lawler, P.A. Pevzner: Approximation Algorithms for Multiple Sequence Alignment, Theoretical Computer Science, 182:233-244, 1997.
  3. P.A. Pevzner: Multiple Alignment, Communication Cost, and Graph Matching, SIAM Journal on Applied Mathematics 52:1763-1779, 1992.
• Vortrag: Suffix Trees and Common Substrings
  Literatur:
  1. D. Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Chapter 7.3, 7.4, 7.6, 124-127, Cambridge University Press, 1997.
  2. E. Ukkonen: On-Line Construction of Suffix-Trees, Algorithmica 14:249-260, 1995.

• Vortrag: Assembly Based on Suffix Trees
  Literatur:
  1. S.R. Kosaraju, A.L. Delcher: Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees, Proceedings of the 28th Symposium on Theory of Computing, 169-177, 1995.
  2. S.R. Kosaraju, A.L. Delcher: Correction: Large-Scale Assembly of DNA Strings and Space-Efficient Construction of Suffix Trees, Proceedings of the 29th Symposium on Theory of Computing, 659, 1996.
  3. E.M. McCreight: A Space-Efficient Suffix Tree Construction Algorithm, Journal of the ACM, 23(2):262-272, 1976.
• Vortrag: Shortest Superstring
  Literatur:
  1. A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis: Linear Approximation of Shortest Superstrings, Journal of the ACM 41(4):630-647, 1994.
  2. S.R. Kosaraju, J.K. Park, C. Stein: Long Tours and Short Superstrings, Proceedings of the 35th Symposium on Foundations of Computer Science, 166-177, 1994.
• Vortrag: Reconstruction
  Literatur:
  1. J.D. Kecceioglu, E.W. Myers: Combinatorial Algorithms for DNA Sequence Assembly, Algorithmica 13:7-51, 1995.

• Vortrag: Consective Ones and PQ-Trees
  Literatur:
  1. K.S. Booth, G.S. Lueker: Testing for the Consecutive Ones Property, Interval Graphs, and Planarity using PQ-Trees, Journal of Computer and System Sciences 13:335-379, 1976.
  2. J.E. Atkins, M. Middendorf: On Physical Mapping and the Consecutive Ones Property for Sparse Matrices, Discrete Applied Mathematics 71:23-40, 1996.
• Vortrag: Interval Graphs
  Literatur:
  1. H. Kaplan, R. Shamir: Bounded Degree Interval Sandwich Problems, Algorithmica 24:96-104, 1999.
  2. H. Kaplan, R. Shamir: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques, SIAM Journal on Algorithms 25(3):540-561, 1996.
• Vortrag: Double Digest Problem
  Literatur:
  1. P.A. Pevzner: DNA Physical Mapping and Alternating Eulerian Cycles in Colored Graphs, Algorithmica 13:77-105, 1995.
  2. W. Schmitt, M.S. Waterman: Multiple Solutions of DNA Restriction Mapping Problems, Advances in Applied Mathematics 12:412-427, 1991.

• Vortrag: Sorting by Reversals
  Literatur:
  1. V. Bafna, P.A. Pevzner: Genome Rearrangements and Sorting by Reversals, SIAM Journal on Computing 25(2):272-289, 1996.
  2. D. Christie: A 3/2-Approximation Algorithm for Sorting by Reversals, Proceedings of the 9th Symposium on Discrete Algorithms, 244-252, 1998.
  3. A. Caprara: Sorting by Reversals is Difficult, Proceedings of the First International Conference on Computational Molecular Biology, 75-83, 1997.
• Vortrag: Sorting Signed Permutations by Reversals
  Literatur:
  1. S. Hannenhalli, P. Pevzner: Transforming Cabbage into Turnip, Journal of the ACM 46(1):1-27, 1999.
  2. P. Berman, S. Hannenhalli: Fast Sorting by Reversals, Proceedings of the 7th Symposium on Combinatorial Pattern Matching, LNCS 1075, 168-185, 1996.
  3. H. Kaplan, R.Shamir, R. Tarjan: Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals, Proceedings of the 8th Symposium on Discrete Algorithms, 344-351, 1997.
• Vortrag: Sorting Signed Permutations by Reversals and Transpositions
  Literatur:
  1. Q.-P. Gu, S. Peng, I.H. Sudborough: A 2-Approximation Algorithm for Genome Rearrangements by Reversals and Transpositions, Theoretical Computer Science 210:327-339, 1999.
  2. G.-H. Lin, G. Xue: Signed Genome Rearrangements by Reversals and Transpositions: Models and Approximation, Proceedings of the 5th International Conference on Computing and Combinatorics, LNCS 1627, 71-80.

• Vortrag: HP-Model and Approximations
  Literatur:
  1. W.E. Hart, S. Istrail: Fast Protein Folding in the Hydrophobic-Hydrophilic Model within Three-Eights of Optimal, Proceedings of the 27th Symposium on Theory of Computing, 157-168, 1995.
  2. W.E. Hart, S. Istrail: Lattice and Off-Lattice Side Chain Model of Protein Folding: Linear Time Structure Prediction Better Than 86% of Optimal, Proceedings of the Second International Conference on Computational Molecular Biology, 137-146, 1998.
  3. R. Agarwala, S. Batzoglou, V. Dancik, S.E. Decatur, M. Farach, S. Hannenhalli, S. Skiena: Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model, Proceedings of the 8th Symposium on Discrete Algorithms, 390-399, 1997.
  4. V. Heun: Approximate Protein Folding in the HP Side Chain Model on Extended Cubic Lattices, Proceedings of the 7th European Symposium on Algorithms, LNCS 1643, 212-223, 1999.
• Vortrag: Inverse Protein Folding
  Literatur:
  1. W.E. Hart: On the Computational Complexity of Sequence Design Problems, Proceedings of the First International Conference on Computational Molecular Biology, 128-136, 1997.
  2. J.M. Kleinberg: Efficient Algorithms for Protein Sequence Design and the Analysis of Certain Evolutionary Fitness Landscapes, Proceedings of the Third International Conference on Computational Molecular Biology, 226-237, 1999.
• Vortrag: Protein Threading
  Literatur:
  1. T. Akutsu, S. Miyano: On the Approximation of Protein Threading, Theoretical Computer Science 210:261-275, 1999.
  2. R. Lathrop: The Protein Threading Problem with Sequence Amino Acid Interaction Preferences is NP-Complete, Protein Engineering 7(9):1059-1068, 1994.

• Vortrag: Construction from Additive Matrices
  Literatur:
  1. J.C. Culberson and P. Rudnicki: A Fast Algorithm for Constructing Trees from Distance Metrics, Information Processing Letters 30:215-220, 1989.
• Vortrag: Construction from Character Data
  Literatur:
  1. S. Kannan, T.J. Warnow: Inferring Evolutionary History from DNA Sequences, SIAM Journal on Computing 23(4):713-737, 1994.
• Vortrag: Comparisons of Evolutionary Trees
  Literatur:
  1. M. Farach, M. Thorup: Fast Comparisons of Evolutionary Trees, Information and Computation 123:29-37, 1995.
  2. M. Steel, T. Warnow: Kaikoura Tree Theorems: Computing the Maximum Agreement Subtree, Information Processing Letters 48:77-82, 1993.