Spring 1998, Question 5: Phylogenetic Trees

Usage notes

Given the two sequences:

	s:   CLPCTC
	t:   TLCLTWTC

and the following scoring matrix formed over the alphabet C, L, P, T and W:

		scoring matrix

Construct the pairwise alignment between (s,t) using dynamic programming.
Gaps are to be charged a score of 0.
Remember that you have to maximize the score!

You can use the following applet to calculate the best alignment and the alignment score.
But be aware: Should this kind of exercise appear in the final exam, you would have to calculate the alignment and score by hand. Hence you should exercise this too.

a)

Give one possible optimal alignment using the underscore mark "_" to describe a gap.

optimal alignment:

s = ___________________
t = ___________________

and the optimal alignment score:

optimal alignment score: ___________________

b)

Given the distance matrix below, construct the topology for the five sequences according to the Nearest Neighbour Joining algorithm given in class.

		Distance matrix

Make use of the notation employed in the following example to give a description of the topology.

Example:
(a,(b,(c,d))) describes the topology

Topology for the five sequences: ___________________

c)

With the topology from part (b), write down the least squares problem for finding optimal distances for the edges.

Make use of the weights w1, ..., w7 already assigned to the tree shown above and the matrix notation

to solve the least squares problem:

Write down the matrix A row per row, e.g. : 1,2,3,4,5,6 as the first row and the vectors x and b element per element.

A =	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________

x =	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________

b =	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________
	___________________

d)

The distance can be matched exactly?

yes

No

Home

Feedback to quiz developers, problem reports...please use it!!!

Name:
	Restore previous session, if applicable Start blank quiz
Note:	If you wish to ask for a hint or a solution, or if you want your answers checked, you have to log in. Your answers, or the fact that you asked for a hint or solution, may be recorded.