Notes 20100708 CS 798 Quartet Phylogeny Reconstruction, Set Programming, Fathiyeh

From SnOwy - Ed's Wiki Notebook

Contents 1 Quartet-Based Phylogeny 2 Maximum Quartet Consistency 3 Inputs, Constraints, Goals 4 Biologist's Questions 5 Optimizations 6 What's the point?

Quartet-Based Phylogeny

• Leaves and subtrees are considered as quartets linked such that there is either one or two nodes between any two nodes.
• We ask: what if the quartet topologies conflict with one another?

Maximum Quartet Consistency

• Exact algorithms
• Near-optimal solutions
• general approach
• translate the problem of searching for best quartet phylogeny into an ultrametric phylogeny problem
• each node is labelled with a positive value such that deeper nodes (closer to leaves) are smaller
  • how do we perform this transformation?
• two theorems together show that we can perform this transformation under some circumstances AND that the runtime is O(n²)
  • new form of logic programming; solving the problem in a declarative way: what, not how.

Inputs, Constraints, Goals

• Constraints:
  • Symmetry, Ultrametricity, Quartet Consistency

Biologist's Questions

• Does this method of mapping the best quartet phylogeny onto an ultrametric matrix problem actually fare against existing methods?
• In the big picture, do we actually put each quartet back into a big phylogenetic where quartet nodes may be complete subtrees?
  • Yes

Optimizations

• Hypercleaning: considers each edge and recovers the edges that have the best probability of being correct?
• Exponential time :(
  • behaves better than existing algorithms: dynamic programming, etc.

What's the point?

• maximum quartet consistency is a reasonable way to look at phylogenetic reconstruction:
  • because we aren't likely to find a phylogeny that will describe all of the relationships between taxa, we aim to find one that describes the most in a reasonable amount of time.