The Library
Approximation algorithms for the fixedtopology phylogenetic number problem
Tools
Cryan, Mary, Goldberg, Leslie Ann and Phillips, Cynthia A. (1997) Approximation algorithms for the fixedtopology phylogenetic number problem. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

PDF (Department of Computer Science Research Report)
WRAP__csrr327.pdf  Other  Requires a PDF viewer. Download (1827Kb)  Preview 
Abstract
In the Lphylogeny problem, one wishes to construct an evolutionary tree for a set of species represented by characters, in which each state of each character induces no more than L connected components. We consider the fixedtopology version of this problem for fixedtopologies of arbitrary degree. This version of the problem is known to be NPcomplete when L is at least 3, even for degree3 trees in which no state labels more than L+1 leaves (and therefore there is a trivial L + 1 phylogeny). We give a 2approximation algorithm for all L for arbitrary input topologies and we give an optimal approximation algorithm that constructs a 4phylogeny when a 3phylogeny exists. Dynamic programming techniques, which are typically used in fixedtopology problems, cannot be applied to Lphylogeny problems. Our 2approximation algorithm is the first application of linear programming to approximation algorithms for phylogeny problems. We extend our results to a related problem in which characters are polymorphic.
Item Type:  Report  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science, Engineering and Medicine > Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Phylogeny  Mathematical models, Trees (Graph theory)  
Series Name:  Department of Computer Science research report  
Publisher:  University of Warwick. Department of Computer Science  
Official Date:  June 1997  
Dates: 


Number:  Number 327  
Number of Pages:  17  
DOI:  CSRR327  
Institution:  University of Warwick  
Theses Department:  Department of Computer Science  
Status:  Not Peer Reviewed  
Publication Status:  Unpublished  
Reuse Statement:  M. Cryan, L.A. Goldberg and C.A. Phillips, “Approximation Algorithms for the FixedTopology Phylogenetic Number Problem”, <i>Proceedings of Combinatorial Pattern Matching</i> <b>8</b>, (1997)  
Funder:  European Strategic Programme of Research and Development in Information Technology (ESPRIT), University of Warwick, United States. Department of Energy  
Grant number:  20244 (ESPRIT), 0951CSA (UoW), DEAC0476AL85000 (DOE)  
Related URLs: 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 