Seminar

Themen

• 05.4.2006
  Vorstellung der Seminarthemen. Themenvergabe und Organisatorisches.

I. Fundamental Sequence Analysis Algorithms Revisited

• 12.4.2006
  Needleman Wunsch algorithm:
  A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins. J. Mol. Biol., 48 443-453, (1970).
  Smith Waterman algorithm:
  Identification of Common Molecular Subsequences J. Mol. Biol., 147, 195-197, (1981).
  


• 19.4.2006
  Gotohs' algorithm:
  An Improved Algorithm for Matching Biological Sequences. J. Mol. Biol. 162, 705-708, (1982).
  Alignments in linear space:
  Optimal alignments in linear space. E. Myers and W. Miller, Comp. Appl. Biosciences, 4:11-17, (1988).
  





II. Advanced Algorithms for Sequence Analysis

• 26.4.2006
  The FASTA algorithm:
  Rapid and Sensitive Protein Similarity Searches. David J. Lipman, William R. Pearson, Science 227, 1435-1441 (1985).
  Protein Sequence Comparison and Protein Evolution. William R. Pearson, Tutorial presented on ISMB 2000.


• 03.5.2006 BLAST I
  Basic Local Alignment Search Tool. J. Mol. Biol. 215, 403-410, (1990).


• 10.5.2006 BLAST II
  Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. Sep 1;25(17):3389-402, (1997).
  
  

  III. Full Text Index Structures and their Applications in Computational Biology

• 17.5.2006 Motivation: Suffix Trees and their Applications
  Book: Algorithms on Strings Trees and Sequences. Dan Gusfield, Cambridge University Press, 1997.


• 24.5.2006 Linear time suffix tree construction algorithms
  From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction. R. Giegerich and S. Kurtz. Algorithmica, 19:331-353, (1997).


• 07.6.2006 Suffix Arrays
  Suffix Arrays: A New Method for On-Line String Searches. Udi Manber and Gene Myers, SIAM J. Comput., 22(5):935--948, Oct. (1993).


• 14.6.2006 Enhanced Suffix Arrays
  Replacing suffix trees with enhanced suffix arrays. M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch. Journal of Discrete Algorithms, (2004).


• 21.6.2006 Whole genome alignment:
  Alignment of whole genomes. Nucleic Acids Research, 27, 11, 2369-2376, (1999).
  Fast algorithms for large-scale genome alignment and comparison. Nucleic Acids Research 30, 11, 2478-2483, (2002).



IV. Consensus Models

• 28.6.2006 Profile analysis
  Profile Analysis: Detection of distantly related proteins. Proceedings of the National Academy of Sciences 84, 4355-4358, (1987)
  Motifs and Profile Analysis. Mona Singh and Dawn Brooks Topics in Computational Molecular Biology (1999). Lecture Note.
  EMATRIX:
  Fast probabilistic analysis of sequence function using scoring matrices. Bioinformatics 16: 233-244, (2000).
  


• 05.7.2006 PoSSuMsearch:
  Possumsearch: Fast and Sensitive Matching of Position specific Scoring Matrices using enhanced suffix arrays. In Proceedings of the German Conference of Bioinformatics (2004).


• 12.7.2006 Profile Hidden Markov Models:
  Book: Durbin et. al. Biological sequence analysis. Probabilistic models of proteins and nucleic acids.Cambridge University Press, 1998.
  Chapter V: Profile HMMs for sequence families




Literatur zum Seminar

• Dan Gusfield: Algorithms On Strings, Trees and Sequences. Cambridge University Press, 1997.
• Durbin, Eddy, Krogh, Mitchell: Biological Sequence Analysis. Probabilistic models of proteins and nucleic acids. Cambridge University Press, 1998.
• David W. Mount. Bioinformatics. Sequence and Genome Analysis. Second Edition. Cold spring Harbor Labratory Press, 2004.
• Benjamin Lewin. Genes VIII. Pearson Prentice Hall, 2004




Vortragsfolien