A pdf version of our Final Document may be found here.
A species (respectively, gene) tree is a leaf labeled acyclic graph used in biology to express the evolutionary relationship between species (respectively, genes). Typically, a gene tree is inferred from the DNA sequence alignment of a gene family; gene trees are then summarized to infer the species tree. Accurate gene tree construction is a fundamental problem in building evolutionary trees. TreeFix (http://compbio.mit.edu/treefix/) is an existing framework which combines the DNA sequence alignment, species tree, and gene tree to return a statistically improved gene tree. The optimization criterion in TreeFix is duplication and loss cost between gene tree and the species tree. When applied on biological data sets (such as fungal genomes) TreeFix produced dramatically improved gene tree trees. This project is about extending TreeFix in two directions: 1) Changing the reconciliation cost between gene tree and species tree to MulRF cost (defined at http://www.almob.org/content/8/1/28). 2) Allowing non-binary species trees, i.e., species trees in which the degree of internal nodes can be more than three. Technical Approaches: 1) Propose an algorithm that solves the problem 2) Design and implement the algorithm