CS 590AB: Advanced Algorithms in Bioinformatics

Instructor: Dr. Chengpeng "Charlie" Bi, Ph.D.
Professor of Bioinformatics and Computer Science
Homepage: cbi 
Office hours: by appointment

Course Information:

• course outline [ PDF ] and lecture notes distributed in class


• announcement

  *) Final project is due on Nov. 29
  0) HW#5 is due on Nov. 15
  1) project#2 is due Nov. 1
  2) homework# 3 is due Oct. 11, hw#4 is due Oct 25.
  3) project#1 has two-day extension (report maximum pages: 15)
  4) choose your topic of final project by the end of October
  

• reading assignment:

  (1) A Tutorial on Hidden Markov Model by Lawrence R. Rabiner [ PDF ]
  (2) Lawrence, C.E., Altschul, S.F., Boguski, M.S., Liu, J.S., Neuwald, A.F., 
      and Wootton, J.C. 1993. Detecting subtle sequence signals: A Gibbs 
      sampling strategy for multiple alignment. Science, 262, 208-14. [ PDF ]
  (3) Optimization by simulated annealing ( PDF )
  (4) Random Projection ( PDF )
  (5) algorithm papers: k-means and fuzzy k-means ( PDF )
  (6) A tutorial on SVM ( PDF )
  

• lab/project assignment:

  (1) A "pattern-driven" motif algorithm implementation: data [FASTA format] for project 1
  (2) Performance evaluation of PWM motif algorithms: project 2
  

• homework (most distributed in class)

Homework 2:

Q1: in handout
Q2: in handout 
Q3: Given the following sequence (297 bps upstream of a gene),
atacccacaaacccacacacccacacattcacttgctcacctggactttgatatctctacc
actgtatccctgccaatatctacagagtgggtaaagggataggcatcaggtcactgggttg
cccaagcaggaagtctgggttccctaacaactttttctaagctaatgctcctggatgatga
tgaaaaaggaggtggggaatggatgaaattttataacagggtgcagaggcagggtcaggat
aaaaggcccagttggaggctgcagcagggtgcagggcagtcagaccaggacca
(1) Estimate the parameters for M0, M1 and M2 respectively;
(2) Using M0 Markov chains as the null hypothesis to calculate 
the chi-square values for M1 and M2 respectively and test which 
model is the best fit.

Further Reading List w/ Scheduling

• A primer on molecular biology: chapter 1 in book by Waterman (1995); chapter 3 in Jones and Pevzner (2004) and their course web at http://www.bioalgorithms.info where some best presentations are made in ppt slides; For more details read the books: Genes VIII (2003) or Molecular Biology of the Cell (2002) An interesting DNA linguistics paper that we discussed in class can be found:
  Ji,SC (1999) The linguistics of DNA: words, sentences, grammar, phonetics and semantics. Ann NY Acad Sci. 870: 411-417
• A short movie about human genome at National DNA Day (http://www.genome.gov/14514276)
• Primer on Molecular Genetics (DOE 1992) [ PDF ]
• Karn M, Blake WJ and Collins JJ (2003) The engineering of gene regulatory networks. Ann. Rev. Biomed. Eng., 5:179-206.
• Searls DB (2002) The Language of Genes Nature, 420(6912):211-7
• Collins FS et al. (2003) A vision for the future of genomics research: A blueprint for the genomic era Nature, 422:835-847

• Basics of probability theory: read Appendix in the books suggested in course outline.
• Markov chains and hidden Markov models, read book chapter 11 by Jones and Pevzner (2004); chapters 3-5 of Durbin et al. 1998 and the tutorial paper by Rabiner 1989 ( PDF ). A book chapter by Dr. Krogh is also introductive but not detail in techniques, it focuses on HMM biological applications [ PDF ]. Nice HMM algorithms are given in the book by Duda et al (2001)
• Krogh A et al. (1994) Hidden Markov models in computational biology: applications to protein modeling. J. Mol. Biol., 235:1501-31
• Gene Structure Prediction: there is a huge volume of research papers in this area that we may not cover in this class. A comprehensive bibliography on this topic can be found via this link: Computational Gene Recognition

• There is a lot of references on this topic.
• Further reading list (under construction):
  (1) Wartell RM, Benight AS (1985) Thermal denaturation of DNA molecules: A comparison of theory with experiment. Physics Report (Review part of Physics Letters), 126(2):67-107.
  (2) Bi C-P, Benham CJ. (2004) WebSIDD: Server for Prediction of the Stress-induced Duplex Destabilized (SIDD) Sites in Superhelical DNA. Bioinformatics, 20:1477-1479. [ PDF ]
  web server: WebSIDD
  (3) Benham CJ, Bi C-P (2004) The analysis of stress-induced duplex destabilization in long genomic DNA sequences. Journal of Computational Biology, 11:519-543. [ PDF ]
  Fye FM, Benham CJ (1999) Exact method for numerically analyzing a model of local denaturation in superhelically stressed DNA. Physical Review E, 59:2408-3426. [ PDF ]

• For Suffix tree methods refer to the book: Gusfield D (1997) Algorithms on Strings, Trees and Sequences

• Book chapters in Timo Koski (2001), Durbin et al (1998), Jones and Pevzner (2004) and JS Liu (2001).
• Further reading list (under construction):
  (1) BIPAD Algorithm: Bi C-P, Rogan PK (2004) Bipartite pattern discovery by entropy minimization-based multiple local alignment. Nucleic Acids Research, 32(17):4979-4991. [ PDF ]
  (2) Bipad web server: Bipartite sequence element discovery
  (3) CONSENSUS Algorithm: Stormo GD, Hartzell GW (1989) Identifying protein-binding sites from unaligned DNA fragments. Proc. Natl. Acad. Sci. USA, 86:1183-1187. [ PDF ]
  (4) CONSENSUS Algorithm: Hertz GZ, Stormo GD (1999) Identifying DNA and protein patterns with statistically significant alignment of multiple sequences. Bioinformatics, 15:563-577. [ PDF ]
  (5) Lawrence, C.E., and Reilly, A.A. 1990. An expectation maximization (EM) algorithm for the identi. cation and characterization of common sites in unaligned biopolymer sequences. Proteins: Struct., Funct., Genet. 7, 41-51.
  (6) Bailey, T. L. And Elkan, C. 1994. Fitting a mixture model by expectation maximization to discover motifs in biopolymers. In Proc. Second International Conference on Intelligent Systems for Molecular Biology 28-36. AAAI Press, Menlo Park, CA.
  (7) MEME Algorithm: Bailey, T.L., and Elkan, C. 1995. Unsupervised learning of multiple motifs in biopolymers using expectation maximization. Machine Learning 21, 51-80.
  (8) Orginal EM Algorithm: Dempster, A.P., Laird, N.M. and Rubin, D.B.. 1977. Maximum-likelihood from incomplete data via the em algorithm. J. Royal Statist. Soc. Ser. B., 39.

• For review, refer to the book by JS Liu (2001) and "Monte Carlo Statistical Methods" by C.P. Robert and G. Casella (2005). Seminal papers on simulated annealing and MCMC methods are as follows:
  (1) Metropolis Algorithm: Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21, 1087-1092.
  (2) Metropolis-Hasting Algorithm: Hastings, W. K. (1970), Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57, 97-109.
  (3) Simulated Annealing Algorithm: Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983) Optimization by simulated annealing. Science, 220, 671-680. [ PDF ]
  (4) Gibbs Sampling Algorithm: Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Pat. Anal. Mach. Intel., 6, 721-741.

• The further reading for Bayesian and Gibbs sampler in Bioinformatics:
  (1) Lawrence, C.E., Altschul, S.F., Boguski, M.S., Liu, J.S., Neuwald, A.F., and Wootton, J.C. 1993. Detecting subtle sequence signals: A Gibbs sampling strategy for multiple alignment. Science, 262, 208-14. [ PDF ]
  (2) Liu, J. S. 1994. The collapsed Gibbs sampler in Bayesian computations with applications to a gene regulation problem. J. Amer. Statist. Assoc., 89, 958-966. [ PDF ]
  (3) Liu, J. S., Neuwald, A. F. and Lawrence, C. E. 1995. Bayesian models for multiple local sequence alignment and Gibbs sampling strategies. J. Amer. Statist. Assoc., 90, 1156-1170.
  (4) BioProspector: Liu, X., Brutlag, D.L. and Liu, J.S. (2001) BioProspector: Discovering conserved DNA motif in upstream regulatory regions of co-expressed genes. Proc. Pacific Symposium on Biocomputing, vol. 6, 127-138. [ PDF ]
  

• Refer to the book by M Mitchell (1998).
• The further reading list (under construction):
  

• Read Chapter 10 in the book by Jones and Pevzner (2004).
• SVM. A Tutorial on Support Vector Machine (SVM) (by Christopher Burges, PDF), A very good introductive book on SVM by Nello Cristianini and John Shawe-Taylor
• Some Clustering algorithms: applications to microarray analysis:
  (1) Hierarchical clustering: Eisen et al. (1998) Cluster analysis and display of genome-wide expression patterns. PNAS USA, 95, 14863-14868. [ PDF ]
  (2) k-means: Tavazoie et al. (1999) Systematic determination of genetic network architecture. Nature Genet., 22, 281-285. [ PDF ]
  (3) SOM: Tamayo et al. (1999) Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation. Proc. Natl Acad. Sci. USA, 96, 2907-2912. [ PDF ]
  (4) principal component analysis: Raychaudhuri et al. (2000) Principal components analysis to summarize microarray experiments: application to sporulation time series. Pac. Symp. Biocomput., pp. 455-466.
  (5) SVM: Brown et al. (2000) Knowledge-based analysis of microarray gene expression data by using support vector machines. Proc. Natl. Acad. Sci. USA, 97, 262-267. [ PDF ]
  (6) fuzzy k-means: Gasch and Eisen (2002) Exploring the conditional coregulation of yeast gene expression through fuzzy k-means clustering. Genome Biol., 3(11):research0059.1-0059.22.
  

• The reading list:
  (1) Sinha et al. (2004) PhyME: a probabilistic algorithm for finding motifs in sets of orthologous sequences. BMC Bioinformatics, 5:170.
  (2) Xie et al. (2005) Systemic discovery of regulatory motifs in human promoters and 3' UTRs by comparison of several mammals. Nature
  (3) Kellis et al. (2003) Sequencing and comparison of yeast species to identify genes and regulatory elements. Nature, 423, 241-254.
  

• Some review papers are:
  (1) Gusfield D, Orzack SH, (2005) Haplotype Inference In: CRC Handbook [ PDF ]

  (2) Gusfield D (2004) An Overview of Combinatorial Methods for Haplotype Inference. In: Computational Methods for SNPs and Haplotype Inference, S. Istrail, M. W aterman, and A. Clark (eds). Lecture Notes in Computer Science, vol. 2983, Springer, p. 9-25, 2004. [ PDF ]

  (3) Bonizzoni P et al. (2003) The haplotyping problems: An overview of computational models and solutions. J. Comput. Sci. & Technol., 18(6):675-688. [ PDF ]