LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Berry, Vincent
Publisher: University of Warwick. Department of Computer Science
Languages: English
Types: Other
Subjects: QA
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(n6) polynomial time algorithm for this variant of the Buneman construction. We improve this result by providing an O(n5) algorithm for this problem that relies on an interesting technique similar to a merge sort procedure on quartets.

Share - Bookmark

Cite this article