The Library
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. In: Apostolico, A. and Hein, J., (eds.) Combinatorial Pattern Matching. Lecture Notes in Computer Science, Volume 1264 . Springer Berlin Heidelberg, pp. 130-149. ISBN 9783540632207
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/3-540-63220-4_56
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 for l greater than or equal to 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 greater than or equal to 3 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-toplogy 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: | Book Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer Berlin Heidelberg | ||||
| ISBN: | 9783540632207 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Combinatorial Pattern Matching | ||||
| Editor: | Apostolico, A. and Hein, J. | ||||
| Official Date: | 1997 | ||||
| Dates: |
|
||||
| Volume: | Volume 1264 | ||||
| Number of Pages: | 20 | ||||
| Page Range: | pp. 130-149 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Title of Event: | 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97) | ||||
| Location of Event: | Univ Aarhus, Aarhus, Denmark | ||||
| Date(s) of Event: | 30 Jun - 02 Jul 1997 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
