Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Approximation algorithms for the fixed-topology phylogenetic number problem

Tools
- Tools
+ Tools

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

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP__cs-rr-327.pdf - Other - Requires a PDF viewer.

Download (1827Kb) | Preview

Request Changes to record.

Abstract

In the L-phylogeny 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 fixed-topology version of this problem for fixed-topologies of arbitrary degree. This version of the problem is known to be NP-complete when L is at least 3, even for degree-3 trees in which no state labels more than L+1 leaves (and therefore there is a trivial L + 1 phylogeny). We give a 2-approximation algorithm for all L for arbitrary input topologies and we give an optimal approximation algorithm that constructs a 4-phylogeny when a 3-phylogeny exists. Dynamic programming techniques, which are typically used in fixed-topology problems, cannot be applied to L-phylogeny problems. Our 2-approximation 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:
DateEvent
June 1997Completion
Number: Number 327
Number of Pages: 17
DOI: CS-RR-327
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Reuse Statement (publisher, data, author rights): M.&nbsp;Cryan, L.A.&nbsp;Goldberg and C.A.&nbsp;Phillips, &ldquo;Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem&rdquo;, <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), DE-AC04-76AL85000 (DOE)
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us