Janne Nikkilä 27. helmikuuta 2001

1 Exercises 1

1.1 a)

• Nonprob: heuristic scoring

• Nonprob: dynamic programming

• Prob: pairwise HMMs: graph

• Prob: full model (also end and start states)

• parameters to estimate:p(x,y),p(x,-),p(-,y),transition P:s, end transition

• Prob: in parameter estimation, training seqs needed

• Prob: algorithms used in the estimation(Viterbi, B-W, forward)

• Prob: algorithms used in the search of the most probable path ie. the probability of the given seq

1.2 b)

• heuristic easy to implement and fast

• seq alignment can be presentd as FSA and this can be modified to eq. prob. model • in heur.

• probabilistic stand on the firmer ground

• possible to use a priori knowledge

• prob.model allow the analysis of reliability of the alignment

1.3 c)

• MC: state can be deduced from the outcome

• MC ex: finding structural groups (i.e. is this seq. a codon), locating CpG islands • HMM ex: find all codons in this seq., alignment

• some explanation when to use Mc and when to use HMM

1.4 d)

• can be assumed that the transition happens before emission or vice versa

• emission first: P({cola,lem})=0.025

• transition first: P({cola,lem})=0.0935

• Markov model: the state can be reasoned from the outcome

1.5 e)

• idea is to consider the probability τ of the transition to the end state, which is same for all sequencences of any length

• probability of the all seqs of length L is P = τ(1 − τ)^{L−1} and this must be summed over all lengths

1.6 f)

• FSA: deterministic, parameters by hand, only one ’best’ solution, fast, and easy • : PHMM: probabilistic, with forward-algorithm knowledge of the goodness of all the

possible solutions, Viterbi may be inferior or the same as FSA:s, parameters from the data, complicated

1.7 g)

• used in multiple alignment

• PSSM: length predetermined, simple HMM(transition prob 1), no gaps or insertions, defines a prob.distribution for each symbol, symbols are assumed to be independent of each other

• PHMM: can be derived from the PSSM by adding the silent and insert states, pair HMM conditioned to emit certain seq, differs from HMM by having no backward transitions, can be used to model position specific information

1.8 h)

• minimizing the rounding errors (taking the logs separately of all factors) yields 9 seqs, otherwise result is 10 seqs

• both american and english billions are accepted

1.9 i)

• Feng-Doolittle, CLUSTALW, Barton-Stenberg, Profile-HMM

• ideas of all, some relevant points from each one

• zero tolerance for too long answers

1.10 j)

• it is possible to sequence only hundreds of base pairs at time, while the lengths of the gene sequences are from thousands to millions of base pairs -> fragment assembly

• this is because gel phosporese-method

• it is also important to know the location of the sequenced fragment in the chromosome -> physical mapping by markers (examples of these)

1.11 k)

• for example: length 56, with one error; length 50,51, no errors

• if a algorithm implemented, higher grade

1.12 l)

• trivial answer: restriction sites are sequences of certain order, restriction enzymes are sensitive to certain sites and it can be assumed that there is one to one correspondence between enzymes and sites;thus, if two different enzymes are used in the DDP, sites cannot coincide exactly

• if some relevant discussion presented, higher grade

1.13 m)

• binary matrices admit the perfect phylogeny iff for each pair (mark P) of columns the sets of 1’s are disjoint (mark Pd) or another is a subset of another (mark Ps)

• C1P for columns means that all 1’s in each column are consequtive

• task: show that, if the former, the latter follows

• when perfect phylogeny, rows having 1’s in a set of Ps-columns can be ordered without changing the order of 1’s in any other columns

• thus, every set of columns with the property Ps can be ordered resulting in the matrix with consequtive 1’s in each column, that is with C1P for columns

• algorithm could for example be to first take those rows with 1’s in the first column, move them to the top of the matrix. Then take the rows having the 1’s in the first column which is not in the previous group, move below the previous group, and so on until there are no unordered rows

1.14 n)

• For every term in the sum P (a(s+t)|b(t), c(0))P (b(t)|c(0))=\frac{P (a(s+t),b(t),c(0))}{P (b(t),c(0))}∗\frac{P (b(t),c(0))}{P (c(0))} = P (a(s + t), b(0)|c(0))

• Summing over all b(t) ∑_{b(t)} P (a(s + t), b(t)|c(0)) = P (a(s + t)|c(0))

1.15 o)

•

2 Exercises 2

2.1 a)

•

2.2 b)

•

2.3 c)

•

2.4 d)

•

2.5 e)

•

2.6 f)

•

2.7 g)

•

2.8 h)

•