Part of Exam for Bioinformatics I
Answer precisely 4 of the following (10 pts. each)
Define
computational problem,
instance of a computational problem, and
algorithm for a computational problem.
Informally, what is meant by an NP-complete problem?
Informally, what is a greedy method, what is a
branch-and-bound method, and what is a dynamic programming
method?
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.
Sketch a greedy method for the same problem.
What is an alignment between two sequences?
Apply (by hand) the dyamic programming algorithm for determing
an optimal sequence alignment to the sequences ACCT and AGCTT
with the scores: match = 1, mismatch = -1, gap = -1.5.
What is the problem of sorting by reversals?
Give a simple greedy algorithm for sorting by reversals and show that
it has no instance-independent performance guarantee.
Outline a more complex algorithm that has an instance-independent performance
guarantee.
Sketch how blast works. Under what conditions will
psi-blast outperform blastp? Explain.
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.
What is a Hidden Markov Model, and what is the
decoding problem for HMMs?
Discuss two examples of bioinformatics problems where HMMs provide a good
approach.