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.

• Fall 2008 handout for BioE131 (64-page PDF, double-sided)
  • Fall 2008 student page with 32 sentences summarized

Background:

• Telephone game (Wikipedia)
• Examples of a "telephone tree":
  • "What is a phone tree?" -- article @wisegeek.com
  • http://www.ehow.com/how_4325_set-emergency-phone.html
  • http://www.aauw.org/advocacy/issue_advocacy/phonetree.cfm
  • http://www.state.nj.us/military//familysupport/family_readiness/telephone_tree.html

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):

• Sequence Alignment Lab
• Primate Phylogeny

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

• Pairwise Alignment Homework
• Phylogeny Homework

Source code

• C++ source code (LaTeX; Makefile)

-- IanHolmes - 26 Nov 2008