The Library
An improved polynomial time algorithm for computing the refined Buneman tree
Tools
Berry, Vincent (1998) An improved polynomial time algorithm for computing the refined Buneman tree. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-342.pdf - Other - Requires a PDF viewer. Download (366Kb) | Preview |
Abstract
We consider the problem of inferring a tree with positive weight edges on a set X from a dissimilarity measure on X. This problem arises in classification and more precisely in evolutionary biology, where we try to estimate the evolutionary tree, or "phylogeny", of a set of species. Several studies recently put the emphasis on inferring trees containing reliable edges [Berry and Gascuel 98, Rice et al 97]. A method first proposed by Buneman [71] was recently investigated [Berry and Gascuel 98] to obtain a tree containing almost only safe edges. However, this tree is in most cases a conservative estimator of the species' phylogeny, due to strict constraints imposed on its edges. Moulton and Steel [98] proposed a variant of the Buneman construction to obtain a less conservative tree, whose edges still verify important combinatorial constraints. Bryant and Moulton recently proposed an O(n<sup>6</sup>) polynomial time algorithm for this variant of the Buneman construction. We improve this result by providing an O(n<sup>5</sup>) algorithm for this problem that relies on an interesting technique similar to a merge sort procedure on quartets.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Trees (Graph theory), Evolution (Biology) -- Mathematical models, Computational biology | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | 1998 | ||||
Dates: |
|
||||
Number: | Number 342 | ||||
Number of Pages: | 11 | ||||
DOI: | CS-RR-342 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT) | ||||
Grant number: | 20244 (ESPRIT) | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year