archives

Reconciling Gene Trees with Apparent Polytomies


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Chang, Wen-Chieh and Eulenstein, Oliver (2005) Reconciling Gene Trees with Apparent Polytomies. Technical Report, Computer Science, Iowa State University.

Full text available as:Adobe PDF

Abstract

We consider the problem of reconciling gene trees with a species tree based on the widely accepted Gene Duplication model from Goodman et al. Current algorithms that solve this problem handle only binary gene trees or interpret polytomies in the gene tree as true. While in practice polytomies occur frequently, they are typically not true. Most polytomies represent unresolved evolutionary relationships. In this case a polytomy is called apparent. In this work, we modify the problem of reconciling gene and species trees by interpreting polytomies to be apparent, based on a natural extension of the Gene Duplication model. We further provide polynomial time algorithms to solve this modified problem.

Keywords:Algorithm, computational biology, gene duplication, gene/species tree reconciliation.
Subjects:Theory of Computation: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3): Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
Computer Applications: LIFE AND MEDICAL SCIENCES
ID code:00000418
Deposited by:Wen-Chieh Chang on 10 May 2006



Contact site administrator at: ssg@cs.iastate.edu