The format of the tech reports ID number is TR-CS-YYYY-NN, where YYYY is the four digit year and NN is the number, including leading zeroes. For the first tech report of 2004, the search would be "TR-CS-2004-01".
This searches only by ID. If you'd like, you can also search by researcher or search by keyword
Found 1 result.
Listing from newest to oldest
TR-CS-2004-04
The Relationship Between Maximum Parsimony Scores and
Phylogenetic Tree Topologies
Tiffani L. Williams, Tanya Berger-Wolf, Bernard M.E. Moret, Usman
Roshan, and Tandy Warnow
Heuristics for the NP-hard maximum parsimony (MP) problem constitute the principle mechanism for estimating phylogenies on large datasets (> 100 sequences). Unfortunately, MP heuristics spend an enormous amount of computational time searching for the optimal solution; on large datasets, MP searches may require months or even years to solve optimally. On the other hand, near-optimal phylogenies require less computational time to reach---possibly providing a good approximation of the tree topology (branching order) of the optimal solution.
In this paper, we investigate whether it is necessary to solve MP optimally. Our experiments explore the relationship between solving MP to various degrees of accuracy and the implied improvement in the estimation of the topology of the optimal tree. We show that near-optimal solutions to MP (within a fraction of one percent of optimal) give highly accurate estimations of optimal tree topologies, and can be obtained in a fraction of the time needed to solve to optimality. Moreover, we propose a preliminary stopping rule that halts a phylogenetic search early with a good of approximation of the optimal solution. Large-scale estimations of phylogenetic trees do not require exact solutions to MP. Our results demonstrate that finding good near-optimal solutions quickly is a more fruitful objective for MP heuristics.
News & Events | People | Academics | Research | Jobs | Companies | Visitors | Computer Facilities | Home
