Broken Telephone Tree

You are the director of a secret police agency, pitted against an imaginary organization using the nefarious tactic of a phone tree. You decide how much information to share with other secret police agencies in reconstructing the structure of the network...

Message analysis from a telephone tree with noise (in the form of edit-distance paths between dictionary words).

Equivalent to certain problems in molecular evolution & phylogenetic reconstruction.

Background:

Wikipedia:Telephone_game
Examples of a "telephone tree":

Some more links:

Edit distance
UPGMA algorithm for phylogenetic reconstruction
- Distance matrix format
Other bioinformatics pseudo-cryptanalysis exercises

BioE131/231: If you have done the following labs, then you have the tools to solve this problem (and obtain extra credit):

SequenceAlignmentLab

PrimatePhylogeny

And if you have done the following homeworks, then you have built your own versions of the tools you need to solve this problem:

PairwiseAlignmentHomework

PhylogenyHomework

Source code

C++ source code (LaTeX; Makefile)

-- IanHolmes - 26 Nov 2008