Notes 20100713.113215 CS 798 Presentation

From SnOwy - Ed's Wiki Notebook

General

• approximating subtree distances between phylogenies
• Robinson-Foulds distance -- compares subtrees in linear time but lacks biological motivation
• TBR, rooted SPR metrics: better biological motivation, NP-hard
• SPR: subtree prune and regraft
• TBR: tree bisection and reconnection
• when we compare two trees, we count the number of modifications required to create one tree from a different tree
  • more modifications equals greater distance

Creating the Maximum Agreement Forest (MAF)

• charge a cost to the links for each edge the algorithm cuts
• prove that this is a 5-approximation algorithm
• looks like a brute force depth first traversal on a search tree that has a space of valid phylogenies

Question: 5-approximation algorithm

• It means that an algorithm will produce an answer that is up to five times worse than the optimal solution