Tutorial 6 - Parsimony - Fitch and Sankoff algorithms

Problem 1 - Fitch's algorithm

Based on the given structure of the phylogenetic tree, compute the total parsimony score using Hamming distance and determine internal nodes.

How many different trees can be obtained?

Problem 2 - Sankoff's algorithm (weighted parsimony)

As in the previous problem, the structure of the phylogenetic tree is already defined. Compute the total parsimony score using scoring matrix S and determine the internal nodes.

The scoring matrix is defined as:

S	A	C	G	T
A	0	2.5	1.0	2.5
C	2.5	0	2.5	1.0
G	1.0	1.5	0	2.5
T	2.5	1	2.5	0

and the structure of the tree is following:

How many different trees can be obtained?

What is a relationship between Fitch and Sankoff algorithm?

Table of Contents

Tutorial 6 - Parsimony - Fitch and Sankoff algorithms

Problem 1 - Fitch's algorithm

Problem 2 - Sankoff's algorithm (weighted parsimony)