Study Guide for Bioinformatics I, Fall 2009

First, I promised I would ask you to use the dynamic programming algorithm to find an optimal global alignment of two short sequences (say, both of length 4) given particular scores for all possible alignment columns, and show your work. Second, the exam may well ask for short and not overly formal definitions of some terms, such as "computational problem", "instance of a computational problem", "greedy algorithm", "dynamic programming", "NP-complete problem", "performance guarantee", "alignment", "global alignment", "local alignment" and "progressive multiple alignment". Finally, you will be asked to write essays on two problems from a list of topics discussed in class, probably including the following. Thus, it might be a good idea to pick two of the following subjects and prepare answers. (Writing about the easiest topic may not be the best approach.)

  • Consider the following informal problem: find a motif that appears in each member of a given set of DNA sequences. Give two distinct formalizations of the problem in terms of optimizing a specified score over a set of specified objects. Compare the computational efficiencies of a brute-force optimization for the two formalizations. Finally, sketch a greedy method for the same problem.
  • Sketch how blast and psi-blast work, describe the conditions under which psi-blast outperforms blastp, and explain the reasons for this difference.
  • Explain in detail how to compute an optimal alignment of two sequences using space that is proportional to the length of the shorter sequence. Show that your procedure works as advertized.
  • Define the problem of sorting by reversals, and discuss at least two heuristics for its solution, including one with an instance-independent performance guarantee that you verify. Also, show that the other heuristic has no such performance guarantee.
  • Discuss how statistical models provide a framework for developing methods to discriminate between two sets of sequences, based on training data. Explain how this works in a few cases, such as recognizing transcription-factor binding sites or promoters. Bonus points will be given for discussions of how statistical models can be used to determine appropriate parameters for scoring pairwise alignments and/or recognizing donor splice site allowing for dependencies among positions (as done by GenScan).
  • Discuss Hidden Markov Models, how they are analysed, and how they have been used in bioinformatics.
  • Explain how NP-completeness results and graph algorithms lead to a formalization of the Sequencing by Hybridization Problem (i.e., reconstructing a sequence from the set of all its k-mers for some k) that can be solved efficiently.

    I'll have time Wednesday and before class on Thursday to answer questions.