Language

Usage notes

We are given the following headlines in four different languages:

English: Introduction of a pilot project for the 4 day week
French: Lancement d'un projet-pilote de semaine de 4 jours
German: Einfuehrung eines Pilot-Projekts fuer die 4-Tage-Woche
Spanish: Lanzamiento de un proyecto piloto para la semana de 4 dias

a) Dynamic Programming

Align the English and the Spanish headline word by word using dynamic programming (you'll only have to solve a few subproblems, actually). Since we want to find out some kind of distance between the two sentences, we define the cost as follows:

  +1	match (both words have the same meaning)
  -1	insertion/deletion of a word
  -1	mismatch

For example, the word "week" and "semana" have the same meaning and would count as a match.

`

		Introd.	of	a	pilot	project	for	the	4	day	week
	0	-1	-2	-3	-4	-5	-6	-7	-8	-9	-10
Lanzam.	-1	?
de	-2
uno	-3
proyecto	-4
piloto	-5
para	-6
la	-7
semana	-8
de	-9
4	-10
dias	-11

Enter the value to be assigned to the marked table element. This value corresponds to the maximal score for the subproblem of aligning the following sequences: "Introd." "Lanzam." Score = ___________________

b) Distances

We define the distance between two phrases as the number of insertions/deletions and mismatches in an optimal alignment (i.e. an alignment which maximizes the previously defined score). Example: The alignment of the English and Spanish headlines computed in the previous section consists of 5 insertions/deletions and 0 mismatches. Therefore, these two languages have a distance of 5.
For each pair of sequences, compute the score as well the distance. Note that for our purposes, we consider apostrophs and dashes as blanks. For example, "d'un" is the same as "de un" and "projet-pilote" is the same as "projet pilote".

English/French:distance = ___________________ score = ___________________
English/German:distance = ___________________ score = ___________________
English/Spanish:distance = ___________________ score = ___________________
French/German:distance = ___________________ score = ___________________
French/Spanish:distance = ___________________ score = ___________________
German/Spanish:distance = ___________________ score = ___________________

c) Nearest Neighbour Joining Algorithm

Given these pairwise distances, build the non-rooted phylogenetic tree using the nearest neighbour joining algorithm.

Enter the two headlines which you want to join and the distance between them. Use the red-coloured shortcuts to refer to languages or groups of languages. "E" stands for English, "G" for German, "F" for French and "S" for Spanish. Groups are identified by combinations of these letters. Example: "Join E and S whose distance is 5"

Join ___________________ and ___________________ whose distance is ___________________

d) Phylogenetic Trees

How many non-rooted phylogenetic trees are there for four phrases?

___________________

And how many rooted phylogenetic trees can you construct for four phrases?

___________________

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.